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.
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.
Going from breaking a key in a month to breaking a key in 1 second seems trivial compared to the effort of going from where we are now to being able to break a key in a month.
I dont know what the quantum future holds, but if quantum actually happens then i have low faith in your plan.
Sounds like overkill. Quantum is a premature concern, but if there’s really that much paranoia why not use PQC like ML-KEM instead of rolling this strange thing?
This will probably not help enough for asymmetric keys, and is unnecessary for symmetric keys. https://arxiv.org/abs/2603.28846 claims an attack runtime of a few minutes.
There are enough order-of-magnitude breakthroughs between today and scalable quantum error correction, that it makes no sense to try to to guess exactly the order of magnitude of the attacks that will be feasible.
Either you believe they won't happen, in which case you can keep using long-term ECDSA keys, or you believe they will happen, in which case they are likely to overshoot your rotation period.
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?
The calculated DW cost of the quantum attack is 2^104 (with conservative/optimistic assumptions and ignoring the physical cost of a single logical gate), which is "much more realistic than a brute force attack" in the same sense that a 128-bit brute force attack is much more realistic than a 256-bit brute force attack.
None of those are remotely practical, even imagining quantum computers that become as fast (and small! and long-term coherent!) as classical computers.
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.
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
> encryption is not ever to be considered impossible to break
One-time pads [0] are actually impossible to break, but they're pretty tricky to use: you must never ever reuse them, they must be truely random, and you need some way to share them between both parties (which isn't that easy since they need to be at least as large as all the data that you ever want to transmit).
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?
> 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?
That's correct. The quantum computer needs to be "sufficiently larger" than your RSA key.
> Basically: for RSA and ECC, is there anything preventing us from using keys 10x bigger?
For RSA things get very unwieldy (but not technically infeasible) beyond 8192 bits. For ECC there are different challenges, some of which have nothing to do with the underlying cryptography itself: one good example is how the OpenSSH team still haven't bothered supporting Ed448, because they consider it unnecessary.
Many implementations limit the RSA key size to 8,192 or 16,384 bits (because the maximum bit length determines indirectly how much stack space is required).
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.
This article, "Factoring is not a good benchmark to track Q-day", was posted this month by one of Cloudflare's lead post-quantum researchers specifically addressing the factoring issue.
It doesn't say much by itself, but it has four very good links on the subject. One of these has a picture of the smallest known factor-21 circuit, which is vastly larger than that of the factor-15 circuit, and comparable to much larger numbers. Another is Scott Aaronson's article making the analogy of asking factoring small numbers as asking for a "small nuclear explosion" - if you're in 1940 and not able to make a small nuclear explosion, that doesn't mean you're much farther away from a big nuclear explosion.
From what i understand the 15 factor was just a stunt and didnt use the actual error corrected algorithm that needs to be used in general.
I think an analogy would be, imagine you are driving across north america in a car, but your engine is broken. The mechanic is near by so you put it in neutral and push it.
If someone said, well it took you half an hour to push it to the mechanic, it will take the rest of your life to get it across north america - that would be the wrong take away. If the mechanic actually fixes the engine, you'll go quite fast quite quickly. On the other hand maybe its just broke and can't be fixed. Either way how fast you can push it has no bearing on how fast the mechanic can fix it or how fast it will work after its fixed.
Maybe people will figure out quantum computers maybe they won't, but the timeline of "factoring" 15 is pretty unrelated.
In the context of cryptography, keep in mind its hard to change algorithms and cryptographers have to plan for the future. They are interested in questions like: is there a > 1% change that a quantum computer will break real crypto in the next 15 years. I think the vibe has shifted to that sounding plausible. Doesn't necessarily mean it will happen, its just become prudent to plan for that eventuality, and now is when you would have to start.
The idea seems to be that there will some sort of cascading effect if we can somehow create physical qubits with sufficient noise performance. It's this "threshold" we keep hearing about. Once we exceed threshold there is a possibility that we can use error correction to expand everything without limit.
This assumes that there will not be other problems that arise. I suspect that "error correcting" thousands of qubits entangled with one another will be one of those problems.
The quantum circuit to factor 15 is a weird special case that can be factored with just a handful of logic gates [0]. Factoring 21 will require quantum error correction, which adds a huge amount of overhead.
It's LK99 all over again. A bunch of software engineers working themselves into a tizzy on X and adjacent circles despite not really knowing the physics. Combined with a lot of financial incentives for people working in the space to play things up...
> The bet is not “are you 100% sure a CRQC [cryptographically-relevant quantum computer] will exist in 2030?”, the bet is “are you 100% sure a CRQC will NOT exist in 2030?”
Yes today's quantum computers cannot factor 21, but enough progress is happening fast enough that now there's a >1% chance they will go much further in (say) five years.
More broadly (outside of relevance to cryptography), quantum computers already can (almost certainly) beat classical computers on certain contrived (useless) problems: see https://arxiv.org/abs/2603.09901 "Has quantum advantage been achieved?" for a summary of the current state.
1) It takes a long time to change cryptography standards, and cryptography also generally needs to provide some forward secrecy: i.e. you would like that something you encrypt today is safe for some time afterwards. This means the timelines cryptographers care about when advocating for a change are long, often more than a decade.
2) By most accounts, quantum computing scaling is limited by various physical effects causing noise in the circuits that prevent making larger circuits from the smaller ones that exist. If this was the end of it, then you would expect scaling to be very slow and probably infeasible. But there is also a process of quantum error correction, which means that once you can build a large enough and reliable circuit to implement it, you can scale very easily. This makes quantum computing scaling very nonlinear: it is expected that scaling will suddenly become a lot easier once this threshold is reached, and it sounds like the state of the art is getting close to that threshold (you can of course find people who are skeptical of this claim: from believing that the timelines are optimistic to doubt that the physics works at all).
3) cryptographers are also likely to err on the side of caution: the effects of widely-used encryption being broken are very bad, so it's best to assume that QC will accelerate quickly and that adoption of post-QC cryptography will be slow.
I'm not familiar with their stance, but bear in mind the costs of introducing new key type on the ecosystem, and on maintenance of SSH implementations.
The simplified answer is, larger keys that demand a far larger effort to break, in a way similar to RSA-4096 vs RSA-2048.
The predicted timelines for quantum computer advances (and the requirements for practical applications) have shrunk dramatically in the past 15 years. What used to be a no-later-than-2035 recommendation for getting off e.g. RSA-2048 in good time, is today no-later-than-2030. The admission of 256-bit curves for ECDSA/ECDH has been supplanted by 384-bit curves already years ago.
In the absolutely ground shaking event that a future application of quantum computation somehow manages to cut Ed448's equivalent security of ~224 bits in half, exploring even a small portion of a 112-bit space will still cost more electrical energy than we can possibly provide.
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?
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?
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.
> I generally believe that 256-bit “security levels” are somewhere between a comfort blanket and numerology [...] AES-256 was unfortunately defined to perform more rounds than AES-128, making it needlessly slower.
Obviously if you benchmark it in RAM you'll see it... but with LUKS disk encryption, for example, disk throughput is completely unaffected by the key size on my newer machines with AES-NI.
In cases like that, it seems silly to me to use the smaller keysize: why would I sacrifice even a tenuous theoretical security benefit for absolutely nothing in return? But granted, the larger keysize will have a measurable cost in most applications, FDE is a rarer case.
I don't know why i experience so much hate against spidermonkey and goanna while surfing the web? it appears they are keeping up to date with security features...?
I get what he’s saying, but, doesn’t he compare classical speed up of parallelizing 64 bit key space on 2^16 cpus with parallelizing 128 bits key space on QCs? It’s true that sqrt (2^128/2^16) = 2^56 and that 56 >> 48, but in one case you are attacking a 64 bits key space and in the other a 128! If you parallelize 2^128 on 2^16 CPUs you get 128-16=112 bits of key space per cpu which is much bigger than 56! No?
Edit: I mean, I get the point is to prove that 2^128 on QC is not the same as 2^64 on CC but it’s still a lot less to search. If a paper came out with that big of a key space reduction AES would be considered broken IMO
44 comments
[ 2.7 ms ] story [ 55.4 ms ] threadWPA3 moved from symmetric AES to ECDH which is vulnerable to Quantum. Gonna be a tonne of IOT inverters waste.
I dont know what the quantum future holds, but if quantum actually happens then i have low faith in your plan.
There are enough order-of-magnitude breakthroughs between today and scalable quantum error correction, that it makes no sense to try to to guess exactly the order of magnitude of the attacks that will be feasible.
Either you believe they won't happen, in which case you can keep using long-term ECDSA keys, or you believe they will happen, in which case they are likely to overshoot your rotation period.
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?
None of those are remotely practical, even imagining quantum computers that become as fast (and small! and long-term coherent!) as classical computers.
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.
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
One-time pads [0] are actually impossible to break, but they're pretty tricky to use: you must never ever reuse them, they must be truely random, and you need some way to share them between both parties (which isn't that easy since they need to be at least as large as all the data that you ever want to transmit).
[0]: https://en.wikipedia.org/wiki/One-time_pad
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?
That's correct. The quantum computer needs to be "sufficiently larger" than your RSA key.
> Basically: for RSA and ECC, is there anything preventing us from using keys 10x bigger?
For RSA things get very unwieldy (but not technically infeasible) beyond 8192 bits. For ECC there are different challenges, some of which have nothing to do with the underlying cryptography itself: one good example is how the OpenSSH team still haven't bothered supporting Ed448, because they consider it unnecessary.
What is going on?
https://bas.westerbaan.name/notes/2026/04/02/factoring.html
It doesn't say much by itself, but it has four very good links on the subject. One of these has a picture of the smallest known factor-21 circuit, which is vastly larger than that of the factor-15 circuit, and comparable to much larger numbers. Another is Scott Aaronson's article making the analogy of asking factoring small numbers as asking for a "small nuclear explosion" - if you're in 1940 and not able to make a small nuclear explosion, that doesn't mean you're much farther away from a big nuclear explosion.
I think an analogy would be, imagine you are driving across north america in a car, but your engine is broken. The mechanic is near by so you put it in neutral and push it.
If someone said, well it took you half an hour to push it to the mechanic, it will take the rest of your life to get it across north america - that would be the wrong take away. If the mechanic actually fixes the engine, you'll go quite fast quite quickly. On the other hand maybe its just broke and can't be fixed. Either way how fast you can push it has no bearing on how fast the mechanic can fix it or how fast it will work after its fixed.
Maybe people will figure out quantum computers maybe they won't, but the timeline of "factoring" 15 is pretty unrelated.
In the context of cryptography, keep in mind its hard to change algorithms and cryptographers have to plan for the future. They are interested in questions like: is there a > 1% change that a quantum computer will break real crypto in the next 15 years. I think the vibe has shifted to that sounding plausible. Doesn't necessarily mean it will happen, its just become prudent to plan for that eventuality, and now is when you would have to start.
This assumes that there will not be other problems that arise. I suspect that "error correcting" thousands of qubits entangled with one another will be one of those problems.
[0] https://algassert.com/post/2500
— from https://words.filippo.io/crqc-timeline/ "A Cryptography Engineer’s Perspective on Quantum Computing Timelines", the OP's blog post from two weeks ago, and the first link in this one. [HN discussion: https://news.ycombinator.com/item?id=47662234]
Yes today's quantum computers cannot factor 21, but enough progress is happening fast enough that now there's a >1% chance they will go much further in (say) five years.
More broadly (outside of relevance to cryptography), quantum computers already can (almost certainly) beat classical computers on certain contrived (useless) problems: see https://arxiv.org/abs/2603.09901 "Has quantum advantage been achieved?" for a summary of the current state.
2) By most accounts, quantum computing scaling is limited by various physical effects causing noise in the circuits that prevent making larger circuits from the smaller ones that exist. If this was the end of it, then you would expect scaling to be very slow and probably infeasible. But there is also a process of quantum error correction, which means that once you can build a large enough and reliable circuit to implement it, you can scale very easily. This makes quantum computing scaling very nonlinear: it is expected that scaling will suddenly become a lot easier once this threshold is reached, and it sounds like the state of the art is getting close to that threshold (you can of course find people who are skeptical of this claim: from believing that the timelines are optimistic to doubt that the physics works at all).
3) cryptographers are also likely to err on the side of caution: the effects of widely-used encryption being broken are very bad, so it's best to assume that QC will accelerate quickly and that adoption of post-QC cryptography will be slow.
The predicted timelines for quantum computer advances (and the requirements for practical applications) have shrunk dramatically in the past 15 years. What used to be a no-later-than-2035 recommendation for getting off e.g. RSA-2048 in good time, is today no-later-than-2030. The admission of 256-bit curves for ECDSA/ECDH has been supplanted by 384-bit curves already years ago.
In the absolutely ground shaking event that a future application of quantum computation somehow manages to cut Ed448's equivalent security of ~224 bits in half, exploring even a small portion of a 112-bit space will still cost more electrical energy than we can possibly provide.
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!
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.
Obviously if you benchmark it in RAM you'll see it... but with LUKS disk encryption, for example, disk throughput is completely unaffected by the key size on my newer machines with AES-NI.
In cases like that, it seems silly to me to use the smaller keysize: why would I sacrifice even a tenuous theoretical security benefit for absolutely nothing in return? But granted, the larger keysize will have a measurable cost in most applications, FDE is a rarer case.
I guess there is genuine cause for concern and a reason why i keep seeing these error pages telling me to update my browser.
note, firefox 78(esr) still gets a 32/32 in security on https://html5test.co/
basilisk 2025: 26/32(-6 experimental features) pale moon 33.5: 26/32(-6 exp. feat.) seamonkey 2.53.23: 24/32(-6 exp. -2 prop.)
I don't know why i experience so much hate against spidermonkey and goanna while surfing the web? it appears they are keeping up to date with security features...?
Edit: I mean, I get the point is to prove that 2^128 on QC is not the same as 2^64 on CC but it’s still a lot less to search. If a paper came out with that big of a key space reduction AES would be considered broken IMO