Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

words.filippo.io

Post reply on HN
Print view View original

41–50 of 116 posts

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

#41

Post by [deleted] »

tptacek wrote: post #26
rugina wrote: post #20

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?

In the last month there has been a sharp vibe shift among cryptography engineers based on rumors that we may have demonstrations of CRQCs much sooner than anticipated, perhaps within 5 years. You're not going to get satisfactory answers beyond that; everybody understands the "factored 15" thing, the people for whom the vibe has shifted have priced that in.

[deleted]

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

#43

Post by purplehat_ »

rugina wrote: post #20

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?

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.

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.

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

#44

Post by kasey_junk »

tptacek wrote: post #26
rugina wrote: post #20

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?

In the last month there has been a sharp vibe shift among cryptography engineers based on rumors that we may have demonstrations of CRQCs much sooner than anticipated, perhaps within 5 years. You're not going to get satisfactory answers beyond that; everybody understands the "factored 15" thing, the people for whom the vibe has shifted have priced that in.

It’s coming from everywhere all at once. Is there a prediction market on timing yet (literally one of the only useful things I can think of for the damnable casinos).

I’ve seen so much change so fast my assumption is someone did it already and preprints are making the rounds.

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

#46

Post by FiloSottile »

ninjahawk1 wrote: post #10

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…

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.

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

#47

Post by FiloSottile »

bob1029 wrote: post #8

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 pract…

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.

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

#48

Post by bawolff »

rugina wrote: post #20

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?

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.

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

#49

Post by avadodin »

cedws wrote: post #37
bob1029 wrote: post #8

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 pract…

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?

I'm not sure what you mean by "this strange thing" as the article promotes AES128 for symmetric encryption and explains why it is dumb to move to "post-quantum" for that use case.

I think there are too many unknowns to bet it all on one horse.

So, if we have to change all of our infrastructure due to a supposed quantum computing threat, I'd go with HybridPQ for asymmetric encryption.

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

#50

Post by cortesoft »

bob1029 wrote: post #23
cortesoft wrote: post #21

Earlier quoted context omitted.

This wouldn’t help symmetric key encryption, which is what this is talking about. The keys you are rotating are asymmetric keys, which are only used to exchange symmetric keys for the actual encryption. In good setups, those symmetric keys are changed every session anyway. If an attacker can break the symmetric encryption in a reasonable amount of time, they can capture the output and break it later. In addition, how…

> This wouldn’t help symmetric key encryption, which is what this is talking about. I agree. The point I am trying to make is that even for asymmetric encryption (which is far more vulnerable), there are still plausible ways to make a quantum break more difficult. The only thing that could compromise this scheme, aside from breaking the signing keys, would be to have TLS broken to the extent that viewing real-time tr…

The problem with key rotation as a defense is it is going to have to happen at EVERY level. You will have to rotate root CA keys at the same rate, or those could just be hacked, and your rotation won’t matter anymore.
Post reply on HN