Date: Fri, 22 Sep 2006 19:55:39 -0400

From: Joseph S D Yao <jsdy@center.osis.gov>

To: Fergie <fergdawg@netzero.net>

Cc: nanog@merit.edu

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

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

Regards,

GRegory hicks

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