> -----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
