On Fri, 2010-03-26 at 19:48 -0700, Scott Fluhrer (sfluhrer) wrote: > > > -----Original Message----- > > From: ipsec-boun...@ietf.org [mailto:ipsec-boun...@ietf.org] On Behalf > > Of Joy Latten > > Sent: Friday, March 26, 2010 5:25 PM > > To: mlepin...@bbn.com; k...@bbn.com > > Cc: ipsec@ietf.org; avaga...@redhat.com > > Subject: [IPsec] Question about RFC 5114 > > > > Hi, > > > > I am looking to implement modp groups 22, 23, and 24 into IKE but have > > a > > question. > > > > RFC 5114 gives the prime, p, the generator, g and a subgroup, q, with a > > specific size... > > > > Because prior rfcs for modp groups did not specify a "q", I was not > > sure > > if this was a new constant or just stating a size requirement? > > q is the order of the generator. For the previous (traditional) MODP groups > (1,2,5,14-18), we have q=(p-1)/2 > > > So I took a look at NIST 800-56A. In particular, > > > > 5.6.1 Private/Public Key Pair Generation > > > > 5.6.1.1 FFC Key Pair Generation > > For the FFC schemes, each static and ephemeral private key and public > > key shall be generated using an Approved method and the selected valid > > domain parameters (p, q, g{, SEED,pgenCounter}) (see Appendix B of FIPS > > 186-3). > > ... > > > > I then took a look at FIPS 186-3, Appendix B, which documents 2 methods > > for finite field cryptography (FFC) key pair generation. > > For example, one method is "Key Pair Generation Using Extra Random > > Bits". It actually states that "q" is an input and it is used to do an > > additional computation to compute "x". > > > > I am somewhat confused, are the modp groups 22, 23 & 24 suppose to use > > one of these new methods and that is why "q" is given in rfc 5114? > > Or am I to ignore this and just continue with existing way > > where "q" is not used and there aren't any additional computations > > to compute x. > > Short answer: it doesn't really matter; the old way is safe (for DH). > > Longer answer: FIPS 186-3 was written about generating values for DSA, not > DH. Now, for DSA, there is a known weakness if the exponents you use are > biased; these algorithms used in FIPS 186-3 were designed to make sure that > the exponents are unbiased (or close enough not to matter). DH doesn't have > similar issues, and so these steps aren't required (although they wouldn't > hurt either). > > Now, you don’t need to use the same exponent size that you would use for the > same size traditional groups; for example, RFC3526 suggests an exponent of > between 220-320 bits for group 14; for group 24, there's no point in an > exponent greater than 256 bits. This is because the exponent is essentially > taken "mod q" by the algorithm, and so making it larger than q gives you more > work without giving any benefit. Note that when FIPS 186-3 talks about using > "extra random bits", they reduce the larger value so that it is <q (step 6 of > B.1.1). > > > On the other hand, NIST SP 800-56A also asks you to validate the peer public > value (section 5.6.2.4), and this also uses q as an input. Here's why that > really does matter for groups 22-24 (and not so much for groups 1,2,5,14-18): > > - If you reuse DH exponents, and you don't validate the peer's public value, > then there is a way for an attacker to determine the value of your exponent > modulo r, where r is a small factor of (p-1)/q. > - This attack involves sending illegal peer public values as a part of the > IKE exchange, and seeing what keying material the unit comes up with. > Because these values are illegal, validating the values foils the attack. > - This takes O(r) time on the attacker's part, which is why r can't be too > large. > > For the traditional groups, (p-1)/q == 2, and so r=2 is the only one the > attacker can use (hence the attacker would be able to determine the lsbit of > your exponent via this attack, but nothing else). It turns out that there's > a short cut to test on the peer public value in this case (compute the > Legendre symbol), but even if you don't, the attacker gets minimal > information. > > For these new groups, (p-1)/q is quite large, and in all three cases, has a > number of small factors (now, NIST could have defined groups where (p-1)/q > has 2 as the only small factor; they declined to do so). For example, for > group 23 (which is the worse of the three), (p-1)/q == 2 * 3 * 3 * 5 * 43 * > 73 * 157 * 387493 * 605921 * 5213881177 * 3528910760717 * > 83501807020473429349 * C489 (where C489 is a 489 digit composite number with > no small factors). The attacker could use this (again, if you don't validate > the peer value) to effective cut your exponent size by about 137 bits with > using only O(2**42) time); if you used 224 bit exponents, then the attacker > would cut the work used to find the rest of the exponent to about O(2**44) > time. Obviously, this is not acceptable. >
Thanks so much for the detail. It has helped greatly. I did take a look at NIST SP 800-56A section 5.6.2.4 for validating the public value. I am in learning mode, so I found the 2nd step confusing... 1. Verify that 2 <= y <= p - 2 2. Verify that y^q = 1 (mod p) Are the parenthesis around "mod p" correct? This is how it is in the NIST doc. Thanks!! regards, Joy _______________________________________________ IPsec mailing list IPsec@ietf.org https://www.ietf.org/mailman/listinfo/ipsec
