fyi-- [dns-operations] early key rollover for dlv.isc.org
Steven M. Bellovin
smb at cs.columbia.edu
Thu Sep 21 17:37:40 UTC 2006
On 21 Sep 2006 17:01:45 +0000, Paul Vixie <vixie at vix.com> wrote:
> > Paul, what exponent does the new key use? (I clicked on the public key
> > link, but I can't decode the base64 that easily...)
> it was made with bind9's "dnssec-keygen" utility, using the -e option, so...
> -e use large exponent (RSAMD5/RSASHA1 only)
> ...hopefully it's a good exponent. (every few years someone tries to explain
> to me what a key exponent is, i think you steve have tried, but it just doesn't
It's pretty simple, if you don't want to understand why it works...
An RSA public key is the pair <e,n>; the private key is <d,n>. 'n' is the
famous product of two primes; e and d have a particular mathematical
relationship relative to those two primes. Broadly speaking, to generate
an RSA key, you find two large random primes, pick a more-or-less
arbitrary number for e, then use e and the two primes to calculate d. You
encrypt (or verify a signature) by calculating m^e mod n; you decrypt or
sign by calculating m^d mod n. The question is how arbitrary e can be.
>From a mathematical perspective -- that is, making the equations work,
but not necessarily being secure -- e can be any odd number greater
than 1 that isn't a multiple of either prime, i.e., from 30,000 feet it
doesn't matter too much what you pick as long as it's odd. For years,
people have used 3, because it makes calculations that use e -- in
particular, signature verification -- much more efficient. RFC 3110, for
example, recommends 3 for DNSSEC. (Demonstration of that is left as an
exercise for the programmer.)
The problem, from my perspective, is that there have been a fair number of
attacks over the last several years that work only for low exponents such
as 3. All of them are special-case attacks; they rely on something else
being true. This latest one relies on an implementation bug and (roughly
speaking) the fact that many more numbers are cube roots than are, say,
65537th roots. Again, without going into details, it turns out that the
bug was easy to commit, arguably because of glitches in the standard, and
OpenSSL had it.
>From my perspective, the deeper issue is that exponent 3 seems to be
fragile -- there have been so many different attacks on it that I suspect
we'll see many more. The only solution is to avoid the fragility. For
reasons I don't understand, 65537 is a frequently-recommended larger
exponent. NIST, in fact, requires that exponents be at least that large.
(Their suggested upper bound is more mysterious to me.) Anyway, 65537 is
reasonably efficient, though not nearly as good as 3. However, its
density of 0 bits helps a lot.
I tried figuring out just what -e does, but I ended up in a maze of twisty
little indirect function calls. But almost anything is going to be better
than 3. (I'm probably going to write a BCP on that.)
--Steven M. Bellovin, http://www.cs.columbia.edu/~smb
More information about the NANOG