fyi-- [dns-operations] early key rollover for dlv.isc.org

Mon Sep 25 18:28:21 UTC 2006

On Fri, 22 Sep 2006 17:01:31 -0700 (PDT), Gregory Hicks
<ghicks at cadence.com> 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/hash-firewalls/kaliski-hash-firewalls-ct-rsa-2002.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 near-problems 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 FIPS-186-3 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 AES-128.)  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