### Very large RSA public exponents (17 Mar 2012)

After yesterday's post that advocated using RSA public exponents of 3 or 2^{16}+1 in DNSSEC for performance, Dan Kaminsky asked me whether there was a potential DoS vector by using *really* big public exponents.

Recall that the RSA signature verification core is *m ^{e}* mod

*n*. By making

*e*and

*n*larger, we can make the operation slower. But there are limits, at least in OpenSSL:

/* for large moduli, enforce exponent limit */ if (BN_num_bits(rsa->n) > OPENSSL_RSA_SMALL_MODULUS_BITS) { if (BN_num_bits(rsa->e) > OPENSSL_RSA_MAX_PUBEXP_BITS) { RSAerr(RSA_F_RSA_EAY_PUBLIC_ENCRYPT, RSA_R_BAD_E_VALUE); return -1; } }

So, if *n* is large, we enforce a limit on *e*. The values of the #defines are such that for *n>*3072 bits, *e* must be less than or equal to 64 bits. So the slowest operations happen with an *n* and *e* of 3072 bits. (The fact that *e<n* is enforced earlier in the code.)

So I setup `*.bige.imperialviolet.org`. This is a perfectly valid and well signed zone which happens to use a 3072-bit key with a 3072-bit public exponent. (I could probably have slowed things down more by picking a public exponent with lots of 1s in its binary representation, but it's just a random number in this case.) One can resolve records `1.bige.imperialviolet.org`, `2.bige.imperialviolet.org`, … and the server doesn't have to sign anything because it's a wildcard: a single signature covers all of the names. However, the resolver validates the signature every time.

On my 2.66GHz, Core 2 laptop, 15 requests per second causes unbound to take 95% of a core. A couple hundred queries per second would probably put most DNSSEC resolvers in serious trouble.

So I'd recommend limiting the public exponent size in DNSSEC to 2^{16}+1, except that people are already mistakenly using 2^{32}+1, so I guess that needs to be the limit. The DNSSEC spec limits the modulus size to 4096-bits, and 4096-bit signatures are about 13 times slower to verify than the typical 1024-bit signatures used in DNSSEC. But that's a lot less of a DoS vector than `bige.imperialviolet.org`, which is 2230 times slower than normal.