> -----Original Message-----
> From: ipsec-boun...@ietf.org [mailto:ipsec-boun...@ietf.org] 
> On Behalf Of Ricky Charlet
> Sent: Wednesday, May 27, 2009 1:02 PM
> To: ipsec@ietf.org; kivi...@ssh.fi; mika.k...@helsinki.fi; 
> hila...@purplestreak.com; paul.hoff...@vpnc.org
> Subject: [IPsec] Question on exponent size as discussed in RFC 3526
> 
> Hi folks,
> 
>       I'm having difficulty interpreting RFC3526, "More 
> Modular Exponential (MODP) Diffie-Hellman groups" section 1, 
> "Introduction".
> Quoting from the RFC
> 
> ---------cut------------
> The exponent size used in the Diffie-Hellman must be selected so that
>    it matches other parts of the system.  It should not be the weakest
>    link in the security system.  It should have double the entropy of
>    the strength of the entire system, i.e., if you use a group whose
>    strength is 128 bits, you must use more than 256 bits of randomness
>    in the exponent used in the Diffie-Hellman calculation.
> ----------paste---------
> 
> Alright here... I'm trying to interpret what is meant, in 
> very pragmatic terms, by "exponent size".  I take the 
> exponent to be the 'a' or 'b' in the Diffie-Hellman 
> calculations... That is the random number chosen by each peer 
> in an implementation specific way. 

I don't know what you mean by 'a' or 'b'; there's no standard naming
convention for the various parts of the operation.  For phase 1, the
operation is:

  g ** e mod p

where:
  g is the generator listed in the RFC (for all groups listed in this RFC,
it is 2)
  p is the prime listed in the RFC
  e is a random exponent
  ** is the (modular) exponentiation operation

When you chose a random value e, you need to pick a value out of a range.
The "exponent size" is the number of random bits you use; that is, if you
pick a 200 bit exponent size, you would pick a random number between 1 and
2**200.

> 
> What confuses me is the juxtaposition of the statement that 
> it must be double the size of the group but with examples 
> given which are *far* below sizes of even the weakest groups. 
> In fact, the examples seem to indicate a corilation with key 
> sizes of symetric key ciphers/hmacs. 

The reason that the examples seem to indicate a correlation with the
symmetric key sizes is because there is a correlation with the symmetric key
sizes.  When attacking a system that uses DH to generate keys, the attacker
has three possible strategies to employ:

- Attack the generated symmetric keys directly
  For example, if the symmetric keys are 128 bit AES keys, the attacker can
brute force that with O(2**128) effort.

- Use a generic group attack based on the exponent length to recover the
private exponent
  If the attacker knows that one side picks N bit exponents, then the
attacker can recover that exponent in about O(2**(N/2)) work (see Pollard
Rho or Big Step/Little Step methods)

- Use a NFS-based attack to recover the exponent
  This attack recovers the private exponent with time dependant only on the
modulus

For the last one, well, we don't have any really good models on how long it
would take; the 'Strength Estimates' in section 8 reflect two different
guesses by various experts.

On the other hand, for picking exponent length, what we want to do is make
sure that it isn't the weakest part of the system; if we pick a length
that's double the symmetric key size, then we know that the attack based on
exponent length will take about as long as attacking the symmetric key
directly.  



> 
> So should a exponent size be double the size of the 
> Diffie-Hellman "p", or double the size of the symetric key?

Double the size of the symmetric key.  BTW: double the size of p would be
silly; it turns out that:

  x ** e mod p == x ** (e mod p-1) mod p

(This is known as "Fermat's Little Theorem", and is true for any x, e and
prime p).  So, if you pick an exponent larger than p, there's an equivilant
exponent smaller than p that does exactly the same thing, and would probably
work a lot faster.
 
> Or is there a formula for "strength of group in bits" that I 
> am missing?
> 
> 
> In RFC 3766, "Determining Strengths for Public Keys", I found this:
> ---------cut--------------
>  Because of
>    Pollard's rho method, the search space in a DH key exchange for the
>    key (the exponent in a g^a term), must be twice as large as the
>    symmetric key.  Therefore, to securely derive a key of K bits, an
>    implementation must use an exponent with at least 2*K bits.  See
>    [ODL99] for more detail.
> --------paste----------------
> 
> So I think I'm very close to answering my own question... The 
> exponent must be twice the size of the symentric key in use. 
> I hesitate because that is not quite what RFC3526 says ( 
> "twice the size of the group" ).

Actually, it's closer to "twice the size of the strength of the group".  The
"strength of the group" is its resistance to the attack #3 I have listed
(NFS).
 
> 
> 
> Any illumination would be appreciated.
> 
> 
> --
> Ricky Charlet
> rchar...@nortel.com
> USA 408-495-5726
> _______________________________________________
> IPsec mailing list
> IPsec@ietf.org
> https://www.ietf.org/mailman/listinfo/ipsec
> 

_______________________________________________
IPsec mailing list
IPsec@ietf.org
https://www.ietf.org/mailman/listinfo/ipsec

Reply via email to