|
North American Network Operators Group Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical Re: fyi-- [dns-operations] early key rollover for dlv.isc.org
On 21 Sep 2006 17:01:45 +0000, Paul Vixie <[email protected]> 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 > stick.) 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
|