fyi-- [dns-operations] early key rollover for

Date: Fri, 22 Sep 2006 19:55:39 -0400
From: Joseph S D Yao <>
To: Fergie <>
Subject: Re: fyi-- [dns-operations] early key rollover for

> Hmmm. It wouldn't have anything to do with prime numbers, now would
> it? :slight_smile:

Well, yes, but there are an infinite number of them.

Of course, 17 is the most prime of them all. 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:

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.


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.

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,

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,

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

    --Steven M. Bellovin,