4096 bit SSL keys

[John Newman]

> On Sep 3, 2016, at 8:29 PM, Riad S. Wahby <rsw at jfet.org> wrote:
> 
> John <jnn at synfin.org> wrote:
>> The reason I asked: updating a few certs at office recently I nuked
>> an older F5 LTM device by installing a 4096 bit key/cert pair - the
>> load on the appliance (Linux based) shot up from less than 1 to about
>> 30 and became so excruciatingly slow it was nearly impossible to back
>> the change out (web GUI and ssh were both nearly non-responsive)..
> 
> Multiplying two n-bit numbers naively costs O(n^2) operations (one
> can do better with Karatsuba and related tricks), and exponentiation
> costs O(n) multiplications (so O(n^3) in total). So assuming the device
> is using something like Montgomery multiplication you'd expect about
> 8x increased load. 30x sounds like there *could* be some other issue
> with the implementation, but a significant slowdown is not unexpected.
> 

I /think/ the explanation to why the load went SO fucking crazy with the
new cert/key combo is this particularly old F5 (a 3400) has some sort of 
silicon dedicated to 2048 decrypts, where-as the 4096 is done 
completely in software… but I’m not sure. It was Friday, and I
didn’t (and haven’t) dug back into it at all since getting it fixed.

Also, while the load did peak around 30, the actual jump was from about
0.8 to a range between 10 and 30.  It probably stayed closer to 20 until
I got everything reverted (updated the client ssl profiles, removed the
4096 bit cert/key, restored the two VIPs I had updated to using the
2048 bit certs..) Regardless, this particular machine did not handle 
high load well … I was lucky I had an established ssh session in, the
web gui just became completely fucked, and even my ssh session
was barely usable. The newer models work much better, and in fact
I had installed about a dozen 4096-bit certs for some VIPs on a 3600,
and the load didn’t jump at all.

Thanks for the response… great info!

—
John


>> On modern hardware, including modern F5s, this problem doesn't
>> exist... but from what reading I've done it seems 4096 buys you
>> very little anyway ?
> 
> Depends who you ask.
>    https://www.keylength.com/
> 
> - NSA Suite B recommends at least 3072 bits.
> 
> - BSI says 2048 bits for now, but 3072 bits for 2017 and beyond.
> 
> - ANSSI and NIST both say 2048 bits should be fine through 2030.
> 
> All of the above recommendations seem to assume the adversary is
> classical rather than quantum.
> 
>> With a theoretical quantum computer attacking is there any
>> significant gain with the bigger key size?
> 
> Shor's algorithm runs in time O(n^2) and requires O(n) qubits to
> factor an n-bit number. The first doesn't offer much help: you're
> only increasing the time by 4x going from 2048 to 4096 bits. I'm not
> qualified to comment on how much the second helps because it's not
> at all clear to me how the expense/difficulty of building a quantum
> computer scales with the number of qubits.
> 
> But if you're worried about defending against general-purpose quantum
> computers, there are other weak points you should be shoring up (no pun
> intended): 256-bit symmetric ciphers, preferably with 256-bit blocks
> (so Rijndael-256 rather than AES-256); and ephemeral key exchanges
> that don't rely on Diffie-Hellman (Google is deploying RLWE and LWE
> schemes in the next coupld years; supersingular isogeny D-H also
> looks promising, but there's a recent attack that suggests caution).
> 
> In sum: it's a strange and scary new world once general-purpose quantum
> computers arrive. In the next few years we're going to see the rollout
> of new post-quantum ciphersuites. For now, maybe we should learn to
> stop worrying and love the qubit :)
> 
> -=rsw