4096 bit SSL keys

Riad S. Wahby rsw at jfet.org
Sat Sep 3 17:29:07 PDT 2016


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.

> 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


More information about the cypherpunks mailing list