On Sep 3, 2016, at 8:29 PM, Riad S. Wahby wrote:

John 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