Large public exponents in DNSSEC keys

[Adam Langley]

It seems that several DNSSEC zones are using RSA keys with a public
exponent of 2**32+1, probably because that's the value that the -e
option to dnssec-keygen uses.

While 3 is a perfectly good RSA public exponent, several bugs in
signature verification have been found over the years where a value of
65537 saved the buggy code. (Most notably, Bleichenbacher's CRYPTO
2006 rump session talk [1]).

However, there's no cryptographic reason to believe that an even
larger value is better. None the less, .us and .cz are both using
DNSKEYs with a public exponent of 2**32+1 (in .cz's case, their keys
actually vary too).

Just to confirm that there's no reason to use a larger value, I asked
Bleichenbacher, who confirmed it.

On the other hand, there's a clear cost to using the larger exponents:
signature verification is significantly slower. If these keys end up
in wide spread use, we'll be wasting huge amounts of resolver CPU time
for no benefit.

Here are the verification times in microseconds for 1024-bit
signatures with the two exponent sizes (three runs per test):

e=65537 23.79 23.94 23.90
e=2*32+1 42.55 42.84 42.79

(Times taken with OpenSSL 1.0.1-beta3. The source code, keys and
signatures are attached. Just symlink key-xxx.pem to key.pem and
sig-xxx to sig for each test.)

So, by mistakenly using -e, the signature verification times are nearly doubled.

I've attached a patch to BIND 9.8.1-P1 to remove this option from
dnssec-keygen. (The patch should apply pretty cleanly to any recent
BIND version.) It would be good if this could get caught up in future
patch releases of BIND.

[1] http://www.imc.org/ietf-openpgp/mail-archive/msg06063.html


Cheers

AGL

-- 
Adam Langley agl at imperialviolet.org http://www.imperialviolet.org
-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.gz
Type: application/x-gzip
Size: 1525 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind-users/attachments/20120307/8c20c1fe/attachment.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: largepublic.tar.gz
Type: application/x-gzip
Size: 4927 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind-users/attachments/20120307/8c20c1fe/attachment-0001.bin>