North American Network Operators Group Date Prev  Date Next  Date Index  Thread Index  Author Index  Historical Re: fyi [dnsoperations] early key rollover for dlv.isc.org
On Fri, 22 Sep 2006 17:01:31 0700 (PDT), Gregory Hicks <[email protected]> wrote: > > > > > > On Fri, Sep 22, 2006 at 11:39:51PM +0000, Fergie wrote: > > > Hmmm. It wouldn't have anything to do with prime numbers, now would > > > it? :) > > > > > > Well, yes, but there are an infinite number of them. > > > > Of course, 17 is the most prime of them all. > > isc.org announced the early key rollover just as a discussion about > "exponent 3 damage spreads" on the cryptography list was heating up. > > This discussion started with a statement that: > > > I've just noticed that BIND is vulnerable to: > > > > http://www.openssl.org/news/secadv_20060905.txt > > > > Executive summary: > > > > RRSIGs can be forged if your RSA key has exponent 3, which is BIND's > > default. Note that the issue is in the resolver, not the server. > > > > Fix: > > > > Upgrade OpenSSL. > > So I thought that the early key rollover was due to this. Yet it seems > to me that this discussion is still recommending that "e 3" be used. > There are no known attacks on e=3 *if* everything else is done properly. There have, however, been many different attacks if mistakes are made, such as the implementation attacks here or various problems with the padding scheme. See, for example, http://www.rsasecurity.com/rsalabs/staff/bios/bkaliski/publications/hashfirewalls/kaliskihashfirewallsctrsa2002.pdf http://citeseer.ist.psu.edu/746101.html http://citeseer.ist.psu.edu/coppersmith96lowexponent.html Poking through the cryptanalytic literature shows many other problems and nearproblems with small exponents and RSA. My conclusion is that e=3 is too fragile  it's too easy to make mistakes (or do things that are later determined to be mistakes by mathematicians). NIST's latest draft of FIPS1863 says: (b) The exponent e shall be an odd positive integer such that 65,537 <= e < 2**(nlen  2*security_strength) where nlen is the length of the modulus n in bits. ("security_strength" appears to be the symmetric system attack work factor, i.e., 128 for AES128.) They don't give a reason; we can assume, though, that their friends in Ft. Meade specified it. (Why the upper bound? It turns out that you don't want the decryption exponent to be too small, either...) So  my very strong recommendation is that e=3 be avoided. For efficiency in implementation, numbers of the form 2^2^n+1 are good for e. Numbers of that form are known as "Fermat Numbers"; see http://en.wikipedia.org/wiki/Fermat_prime . e=5 is almost as vulnerable as e=3, especially for larger RSA moduli. e=17 might be at risk for really large moduli to match large AES keys (see RFC 3766). I don't know why F3 (257) isn't a good choice, but 65537 has been a popular alternative for years. Steven M. Bellovin, http://www.cs.columbia.edu/~smb
