Quantum Computers Are Not a Threat to 128-Bit Symmetric Keys

I just want to comment on how clear I find Filippo Valsorda's writing on this kind of thing. Even for an old dunderhead like me, his mathematics and examples were easy to follow. I really appreciate that kind of clarity in technical writing.

Is there any reason to believe that Grover's is as good as it gets? I'm on board here, and I think the article caveats that it's a matter of cost, priority, and assumptions. Cool, cool, I'm already using xaes-256-gcm. But I'm just curious if quantum could have new applications for algorithmic analysis, or take advantage of other weaknesses?

On the symmetric side, I think "AI finds some new classical attack" is the main thing to worry about at the moment. Small probability of p(doom) in the sense of AES falling, but nonzero nonetheless.

As far as I know, the current state of AES-256 is something like "this attack breaks AES in 2**254 instead of 2**256 if we have something like 2**80 bits of ciphertext to work with in the first place". That's nice for getting papers in crypto conferences but not something to lose sleep over yet, but an AI trained on the entirety of LNCS and ePrint might be a different matter.

That and side-channels, but we've known about those for a while.

Whether AES or ChaCha holds up better in the face of AI is an interesting open question for which I can't offer anything better than a coin flip.

On one hand I hear that quantum computers will crack factorisation and discrete logarithms, on the other that the max number factorised is 15 and that 21 might not even be feasible.

What is going on?

I think quantum may be practically mitigated with aggressive key rotation in some cases. I've been prototyping an oauth machine-to-machine integration with a banking vendor that has our ecdsa keys rotate every 5 minutes. The keys are scheduled for deletion after 10 minutes. I see no reason I couldn't reduce this to something like 30s/60s. Our counterparty frequently scans our JWKS endpoint for revocation, so in practice an attacker with a quantum computer would need to be very fast if they wanted to break this particular wire agreement the scary way.

Very good breakdown, if I’m understanding Grover’s algorithm correctly, are you saying essentially that it would require either too much compute or too much time to be feasible but is still much more realistic than a brute force attack?

If that’s the case, would the time eventually be basically irrelevant with enough compute? For instance, if what’s now a data center is able to fit in the palm of your hand (comparing early computers that took up rooms to phones nowadays). So if compute is (somehow) eventually able to be incredibly well optimized or if we use something new, like how microprocessors were the next big thing, would that then be a quantum threat to 128-bit symmetric keys?

Quantum computers are mainly a threat to naive investors.

Rotation protects one threat model, not both. A broken signing key five minutes old is one forged-window. Harvested ciphertext in someone's archive does not care when you deleted the session key. Rotate the signer, but put xaes-256-gcm on the payload if you want the bytes safe ten years out.

If this is true, I feel teh wifi alliance have a tonne to answer for the ewaste they generate.

WPA3 moved from symmetric AES to ECDH which is vulnerable to Quantum. Gonna be a tonne of IOT inverters waste.

Good post. Entirely correct, and well known amongst quantum researchers, but under appreciated in general.

Grover attacks are very blatantly impractical. When someone describes Grover-type attacks in the same breath as Shor-type attacks, without caveats, that's a red flag.

Certainty is a wonderful thing

One frustrating thing about the forefront of crypto is that certainty is missing. Responsible cryptographers have to hedge their advice.

One wonderful thing about Filippo is that when it is possible for him to give concrete advice, he gives it, and brings receipts.

Thanks Filippo!

He mentions "non-existing AES-512" but why not? Why not AES-1024 or AES-4096? Is it too much processing power needed to encrypt and decrypt? I am guessing perhaps also the algo needs work - you can't just take AES-128 and add bits, if you could it would have been done?

I wonder when the OpenSSH developers will change their stance on Ed448.

Tangentially related but regarding RSA and ECC... With RSA can't we just say: "Let's use 16 384 bit keys" and be safe for a long while?

And for ECC, I know many are using the "2 exp 255 - 19" / 25519 for it's unlikely to be backdoored but it's only 256 bits but... Can't we find, say, "2 exp 2047 - 19" (just making that one up) and be safe for a while too?

Basically: for RSA and ECC, is there anything preventing us from using keys 10x bigger?

[flagged]

[dead]

Disconcerting opening. If you want to put hash algorithms in the same category as symmetric keys in this particular case then say so without referring to them as if they are symmetric keys.

Interesting approach — curious how this scales under real load.

encryption is not ever to be considered impossible to break.

every encryption scheme has at least one way to be decrypted.

fidelity of information is one use of encryption, if you apply the solution and get garbage, something is wrong, somewhere.

occultation of information is another use, that is commonly abused by extending undue trust. under the proviso that encryption will eventually be broken, you cant trust encryption to keep a secret forever, but you can keep it secret, for long enough that it is no longer applicible to an attack,or slightly askew usecase, thus aggressive rotation of keys becomes desirable