[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: DH Group strengths [math]


On Wed, 19 Nov 1997 svakil@usr.com wrote:

>      From the Oakley draft,
>      
>      Wellknown group                    Group Strength (bits)
>      ---------------                    ---------------------
>      
>      1                                          66
>      2                                          77
>      3                                          76
>      4                                          91
>      
>      Am I correct in assuming that these are the maximum possible strengths 
>      of the groups, i.e. no matter what the size of the exponent, the group 
>      cannot provide better strength? 

  It is my understanding that "strength" is log2 of the expected number of
  steps required by the best known discrete logarithm algorithms. 

  It would be silly to use an exponent that is strictly in the range 
  [2, 2^strength]. That would make brute force search the fastest method
  for solving the Diffie-Hellman problem.

  Brute force search would take about the same number of steps as the DL
  algorithms, but the constant factor would be MUCH smaller:

	  /* brute force DL for MODP groups with generator 2 */
	  a = 1;
	  for (i = 0; a != x; i++) 
	    {
	       a = a << 1;
	       if (a >= p) a -= p;
	    } 
	  printf("The discrete log of %d is %d!\n", x, i);

  (Even faster algorithms exist, but you should get the general idea
  from there. This problem is well suited for certain types of SIMD
  arrays.)

  The oakley draft recommends 180 bits of entropy (section 2.3.1.1,
  Exponent Advice). The exponent could be 180 bits long, or you might want
  to use longer exponents that are '0'-biased (zeros are 2-3 times cheaper
  than ones in classical modular exponentiation). 
  
  In the secure shell drafts (SecSh WG) we recommend choosing a completely
  random exponent in the range [2, Ord(G)-1]. This is not quite as fast,
  but gives me a warm & fuzzy feeling.

>      If this is the case, then which one 
>      of the above groups can be used to derive a key for 3DES? 

  All of them. 
      
>      Also, if keys are to be generated for an authentication algorithm, and 
>      an encryption algorithm, is the key length for the authentication 
>      algorithm also a factor in selecting a DH group?  If yes, (..)

  No, I don't think so.

- mj

Markku-Juhani O. Saarinen <mjos@ssh.fi>, SSH Communications Security Ltd
Follow-Ups: References: