Speaking within the context of https SSL certs, is there any real value to a key/cert above 2048 bits? 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).. 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 ? With a theoretical quantum computer attacking is there any significant gain with the bigger key size? Curious what others think.... John -- Sent from my Android device with K-9 Mail. Please excuse my brevity.
John <jnn@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.
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
On Sat, Sep 03, 2016 at 05:29:07PM -0700, Riad S. Wahby wrote:
John <jnn@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)..
I think this could be some crypto/SSL issue, consider asking them.
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.
This applies to straightforward implementation. openssl is protecting against timing attacks, which additionally slows, but unless there is bug, the load shouldn't jump so much. A 2010 thread discusses timings with sign/verify with 100K bit RSA keys, pycrypt (python + some libraries) is significantly faster than openssl. The keys/certs are somewhere on the interwebs: http://openssl-dev.openssl.narkive.com/Y60Bau1J/inconsistent-timings-for-rsa... ===== inconsistent timings for rsa sign/verify with 100K bit rsa keys sign verify key1 5min <1sec key2 48min 21min (tested on patched openssl1.0.0a) ===== Besides quantum computers, another threat is private factoring algorithm, sufficiently faster than the public ones. Say one more square root in the subexponential stuff or the constants significantly lower.
On Sep 3, 2016, at 8:29 PM, Riad S. Wahby <rsw@jfet.org> wrote:
John <jnn@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
participants (4)
-
Georgi Guninski -
John -
John Newman
-
Riad S. Wahby