7 ms·

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

307 points by hasheddan 6mo ago

jeremie_strand 6mo ago
[dead]
occamofsandwich 6mo ago
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.
- FiloSottile 6mo ago
  Hashes are symmetric cryptography primitives, and it's even proper to talk about key sizes for e.g. HMAC and HKDF hash-based constructions, to which Grover's algorithm applies analogously to how it applies to cipher keys.
  - occamofsandwich 6mo ago
    Assuming a member of the target audience sees the connection between HMAC and symmetric keys AFA usage, would you like them to be making leaps like this in their regular usage of cryptography? (I really couldn't tell you if an algorithm that involves being able to look into the box in the middle might not have characteristics that means part or all the primitives involved are less quantum safe than an algorithm that lacks that possibility yet I'd suspect I have a lot more experience than the average reader drawn in by the title.)
kd913 6mo ago
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.
- supernetworks_ 6mo ago
  WPA3 moved from PBKDF to ECDH. AES CCMP and GCMP are still the underlying block ciphers in WPA3 with some other extensions for China
- evil-olive 6mo ago
  WPA3 was announced in 2018 [0]. I don't think it's reasonable to blame them for not anticipating the next decade of cryptographic research. ...but even if they had, what realistically could they have done about it? ML-KEM was only standardized in 2024 [1]. also, the addition of ECDH in WPA3 was to address an existing, very real, not-theoretical attack [2]: > WPA and WPA2 do not provide forward secrecy, meaning that once an adverse person discovers the pre-shared key, they can potentially decrypt all packets encrypted using that PSK transmitted in the future and even past, which could be passively and silently collected by the attacker. This also means an attacker can silently capture and decrypt others' packets if a WPA-protected access point is provided free of charge at a public place, because its password is usually shared to anyone in that place. 0: https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#WPA3 https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#WPA3 1: https://en.wikipedia.org/wiki/ML-KEM https://en.wikipedia.org/wiki/ML-KEM 2: https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#Lack_of_forward_secrecy https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#Lack_of...
  - ndriscoll 6mo ago
    Does it matter if an attacker can decrypt public wifi traffic? You already have to assume the most likely adversary (e.g. the most likely to sell your information) is the entity running the free wifi, and they can already see everything.
    - bdamm 6mo ago
      It is precisely because the operator of the wifi is not necessarily the adversary a user may be most concerned about. They may be, but they are not the only one. They are the one you know can be, but they aren't the only one.
    - 6mo ago
bob1029 6mo ago
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.
- glitchc 6mo ago
  You're clearly not using these keys in certificates, which would need to be signed by a root or interim CA on every update.
  - bob1029 6mo ago
    Correct. The keys are only used for signing JWTs. Trust was established with the vendor out of band from this wire protocol (the URL they scan for public keys).
    - SahAssar 6mo ago
      I'm not sure I understand, but haven't you just moved the problem to the out of band layer? And is that layer not secured using the same normal (somewhat) long-lived TLS as most sites? I don't think I understand the threat model you are using here?
      - bob1029 6mo ago
        Think of the out of band layer as two human executives exchanging URLs and GUIDs in person. You still need a secure transport, but in this model the thing that is being secured on the wire expires within 15 minutes. The only way to break the model is to defeat a transport or protocol key and only before rotation, revocation and expiration can catch up each time.
ninjahawk1 6mo ago
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?
- cortesoft 6mo ago
  I am not an expert, but while you are correct that a fast enough traditional computer (or a parallel enough computer) could brute force a 128 bit key, the amount of improvement required would dwarf what we have already experienced over the last 40 years, and is likely physically impossible without some major fundamental change in how computers work. Compute has seen in the ballpark of a 5-10 orders of magnitude increase over the last 40 years in terms of instructions per second. We would need an additional 20-30 orders of magnitude increase to make it even close to achievable with brute force in a reasonable time frame. That isn’t happening with how we make computers today.
  - semi-extrinsic 6mo ago
    > That isn’t happening with how we make computers today. Keep here in mind that computers today have features approaching the size of a single atom, switching frequencies where the time to cross a single chip from one end to the other is becoming multiple cycles, and power densities that require us to operate at the physical limits of heat transfer for matter that exists at ambient conditions. We can squeeze it quite a bit further, sure. But anything like 20-30 orders of magnitude is just laughable even with an infinite supply of unobtanium and fairy dust.
    - f33d5173 6mo ago
      You don't need to keep shrinking features. Brute forcing is highly parallel; to break a key within a certain time frame all you need is a large enough quantity of chips. While it's in the realm of science fiction today, in a few centuries we might have nanorobots that can tile the entire surface of mars with processors. That would get you enough orders of magnitude of additional compute to break a 128 bit key. 256 bit would probably still be out though.
Strilanc 6mo ago
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.
rolph 6mo ago
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
- gucci-on-fleek 6mo ago
  > 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). [0]: https://en.wikipedia.org/wiki/One-time_pad https://en.wikipedia.org/wiki/One-time_pad
  - rolph 6mo ago
    not trying to be obtuse, but there is at least one solution, the one used to decrypt. if you know something about the content e.g. it is for russians, or americans. you can use a frequency analysis to identify vowels. that goes for a simple substitution cypher that is relying on low frequency of usage[one time use] and does not keep it brief. when you further substitute numbers for words, you gain more room for verbosity. if you have high stakes, your message in the clear, should only be useful for a limited time, at the point that it is no longer actionable. im very familiar with one time pads random, and keyed. they are a little simple, you can use a triaxial scheme, or a tensor like scheme, for more leg room and more complexity. depending on what you are doing it may be necessary, to not carry any pads, but to have access at some point, to agreed upon keys, in order to generate a pad on the spot. or even work in your head, if you have skill. e.g. jackdwlovemybigsphnxfqurtz as a weak example.
    - 6mo ago
TacticalCoder 6mo ago
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?
- quinnjh 6mo ago
  > for RSA and ECC, is there anything preventing us from using keys 10x bigger? you can run benchmarks yourself: openssl speed rsa1024 rsa2048 also this (slightly dated) java ex writeup covers this well: https://www.javamex.com/tutorials/cryptography/rsa_key_length.shtml https://www.javamex.com/tutorials/cryptography/rsa_key_lengt... tldr trade off is found between better performance and how many years the data needs to be assumed confidential
- dist-epoch 6mo ago
  for a 10x bigger key the quantum computer needs to be 10x bigger - linear scaling. the time to run the algorithm has cubic scaling - 1000x more time required. but it remains exponentially faster, just 1 minute becomes 1 day, 1 day becomes 3 years. still "easily" broken
- daneel_w 6mo ago
  > 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.
- briansmith 6mo ago
  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).
rugina 6mo ago
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?
- tptacek 6mo ago
  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 6mo ago
    [deleted]
  - kasey_junk 6mo ago
    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.
- dlcarrier 6mo ago
  Coherency To get useful results, a quantum computer needs all of its qbits to stay entangled with each other, until the entire group collapses into the result. With current technology, it is very difficult for a reasonable sized group of qbits to stay coherently entangled, so it can only solve problems that are also relatively easy to solve on classical computers. If someone today were to figure out how to keep large numbers of bits entangled, then quantum computing would instantly be able to break any encryption that isn't quantum safe. It's not something that we are slowly working toward; it's a breakthrough that we can't predict when, or even if, it will happen.
  - Mithriil 6mo ago
daneel_w 6mo ago
I wonder when the OpenSSH developers will change their stance on Ed448.
- farfatched 6mo ago
  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.
  - daneel_w 6mo ago
    Imagine if we would've had the same hesitant cost-first reasoning about Ed25519, and then again about ML-KEM and SNTRUP.
    - farfatched 6mo ago
      I didn't suggest cost-first. You suppose what happens if the OpenSSH maintainers considered the cost when implementing those algorithms? Perhaps they did, but decided the benefits were worth it.
- mkj 6mo ago
  What does ed448 mitigate against vs ed25519?
  - daneel_w 6mo ago
    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.
deleted 6mo ago
[deleted]
michaelsmanley 6mo ago
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.
- macshome 6mo ago
  Agreed. He presents the math in a way that illustrates his point without being difficult for non-mathematicians to grasp. A lot of blogs get hung up in the math, even when it is just supporting evidence for a broader point.
staticassertion 6mo ago
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?
- kirrent 6mo ago
  The only caveat is that AES is not necessarily a black box. It's possible there may be hidden structure to take advantage of, but if there is there's no reason to suspect it's one that's amenable to a quantum speedup. As far as the Grover speedup goes, it's already optimal. Requiring O(sqrt(N)) queries is the proven lower bound for unstructured search.
- amluto 6mo ago
  Yes and no. Grover's algorithm is provably optimal [0]. No quantum algorithm will ever find an n-bit key by queries to any reasonable sort of oracle faster than Grover's algorithm, and Grover's algorithm is way too slow to be a serious problem. But symmetric ciphers are not black boxes. They're mostly built on some variant of a Feistel network, which is a very nice construction for turning a messy function into an invertible function that, in a potentially very strong sense, acts like a cryptographically secure permutation. When I was in grad school, one project I contemplated but never spent any real time on was trying to either generate a real security proof for quantum attacks on Feistel networks or to come up with interesting quantum attacks. And there is indeed an interesting quantum attack against 3-round Feistel networks [1]. This is interesting, because, depending on what sort of security is needed, three or four rounds of Feistel network are sufficient against classical attack [2]. Now ciphers like AES have many more than 3 rounds, so hopefully they're fine. But maybe they're not. My intuition is that there is probably a reasonably small n1 and a reasonably small n2 >= n1 (probably constants, maybe logarithmic in numbers of bits) for which there is no quantum algorithm that can break symmetric crypto given classical query access even to the round functions (n1) or quantum query access to the round functions (n2) [3], but I'm not aware of any proof of anything of the sort. And my intuition definitely should be be trusted fully! (Maybe, even if I'm wrong, there is still a number of rounds that is sufficient for security against query access to the entire cipher.) [0] The classic result is https://arxiv.org/abs/quant-ph/9701001 https://arxiv.org/abs/quant-ph/9701001 and there are newer, more exact results, e.g. https://arxiv.org/abs/0810.3647 https://arxiv.org/abs/0810.3647 [1] https://ieeexplore.ieee.org/document/5513654 https://ieeexplore.ieee.org/document/5513654 [2] https://en.wikipedia.org/wiki/Feistel_cipher https://en.wikipedia.org/wiki/Feistel_cipher [3] It would be extremely cool if someone built quantum computers and networks and storage such that two parties that don't trust each other could actually communicate and exchange (interesting [5]) qubits. I've written some fun papers on the possible implications of this. If we ever get the technology, then it might actually be meaningful to consider things like chosen-quantum-ciphertext attacks against a classical symmetric cipher. But that's many, many years away, and, in any case, an attacker will only ever get to do a quantum query attack against a cryptosystem if a victim lets them. [4] Otherwise all queries will be classical. [4] Or in very complex settings where there is an obfuscated black box, for example. This may be relevant for zk-snarks or similar constructions. [5] I don’t consider the optical qubits exchanged in commercial devices that supposedly implement quantum key distribution to be interesting. To the vendors of such devices, sorry.
nelox 6mo ago
Certainty is a wonderful thing
SipitenoMK 6mo ago
[flagged]
fred_is_fred 6mo ago
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?
kazinator 6mo ago
Quantum computers are mainly a threat to naive investors.
- apgwoz 6mo ago
  Yeah, but… what if?
  - dboreham 6mo ago
    We found one :)
    - apgwoz 6mo ago
      Not at all. I was simply making a joke on the parallel exploration of states.
- wasabi991011 6mo ago
  Please follow the hackernews commenting guidelines in the future. It helps keep this place interesting. Shallow comments such as this one don't meaningful add to the conversation, and won't do much to convince others of your opinion. > Comments should get more thoughtful and substantive, not less, as a topic gets more divisive. > Don't be curmudgeonly. Thoughtful criticism is fine, but please don't be rigidly or generically negative. > Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something.
agent-kay 6mo ago
[flagged]
ardline 6mo ago
Interesting approach — curious how this scales under real load.
jeffrallen 6mo ago
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!
red_admiral 6mo ago
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.
jcalvinowens 6mo ago
> 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.
Luke25 6mo ago
[dead]
dogtimeimmortal 6mo ago
> there is a concrete danger to asymmetric cryptography 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/ 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...?
moktonar 6mo ago
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

307 points by hasheddan 6mo ago

[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.

FiloSottile 6mo ago
Hashes are symmetric cryptography primitives, and it's even proper to talk about key sizes for e.g. HMAC and HKDF hash-based constructions, to which Grover's algorithm applies analogously to how it applies to cipher keys.
- occamofsandwich 6mo ago
  Assuming a member of the target audience sees the connection between HMAC and symmetric keys AFA usage, would you like them to be making leaps like this in their regular usage of cryptography? (I really couldn't tell you if an algorithm that involves being able to look into the box in the middle might not have characteristics that means part or all the primitives involved are less quantum safe than an algorithm that lacks that possibility yet I'd suspect I have a lot more experience than the average reader drawn in by the title.)

kd913 6mo ago

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.

supernetworks_ 6mo ago
WPA3 moved from PBKDF to ECDH. AES CCMP and GCMP are still the underlying block ciphers in WPA3 with some other extensions for China
evil-olive 6mo ago
WPA3 was announced in 2018 [0]. I don't think it's reasonable to blame them for not anticipating the next decade of cryptographic research. ...but even if they had, what realistically could they have done about it? ML-KEM was only standardized in 2024 [1]. also, the addition of ECDH in WPA3 was to address an existing, very real, not-theoretical attack [2]: > WPA and WPA2 do not provide forward secrecy, meaning that once an adverse person discovers the pre-shared key, they can potentially decrypt all packets encrypted using that PSK transmitted in the future and even past, which could be passively and silently collected by the attacker. This also means an attacker can silently capture and decrypt others' packets if a WPA-protected access point is provided free of charge at a public place, because its password is usually shared to anyone in that place. 0: https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#WPA3 https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#WPA3 1: https://en.wikipedia.org/wiki/ML-KEM https://en.wikipedia.org/wiki/ML-KEM 2: https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#Lack_of_forward_secrecy https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#Lack_of...
- ndriscoll 6mo ago
  Does it matter if an attacker can decrypt public wifi traffic? You already have to assume the most likely adversary (e.g. the most likely to sell your information) is the entity running the free wifi, and they can already see everything.
  - bdamm 6mo ago
    It is precisely because the operator of the wifi is not necessarily the adversary a user may be most concerned about. They may be, but they are not the only one. They are the one you know can be, but they aren't the only one.
  - 6mo ago

bob1029 6mo ago

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.

glitchc 6mo ago
You're clearly not using these keys in certificates, which would need to be signed by a root or interim CA on every update.
- bob1029 6mo ago
  Correct. The keys are only used for signing JWTs. Trust was established with the vendor out of band from this wire protocol (the URL they scan for public keys).
  - SahAssar 6mo ago
    I'm not sure I understand, but haven't you just moved the problem to the out of band layer? And is that layer not secured using the same normal (somewhat) long-lived TLS as most sites? I don't think I understand the threat model you are using here?
    - bob1029 6mo ago
      Think of the out of band layer as two human executives exchanging URLs and GUIDs in person. You still need a secure transport, but in this model the thing that is being secured on the wire expires within 15 minutes. The only way to break the model is to defeat a transport or protocol key and only before rotation, revocation and expiration can catch up each time.

ninjahawk1 6mo ago

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?

cortesoft 6mo ago
I am not an expert, but while you are correct that a fast enough traditional computer (or a parallel enough computer) could brute force a 128 bit key, the amount of improvement required would dwarf what we have already experienced over the last 40 years, and is likely physically impossible without some major fundamental change in how computers work. Compute has seen in the ballpark of a 5-10 orders of magnitude increase over the last 40 years in terms of instructions per second. We would need an additional 20-30 orders of magnitude increase to make it even close to achievable with brute force in a reasonable time frame. That isn’t happening with how we make computers today.
- semi-extrinsic 6mo ago
  > That isn’t happening with how we make computers today. Keep here in mind that computers today have features approaching the size of a single atom, switching frequencies where the time to cross a single chip from one end to the other is becoming multiple cycles, and power densities that require us to operate at the physical limits of heat transfer for matter that exists at ambient conditions. We can squeeze it quite a bit further, sure. But anything like 20-30 orders of magnitude is just laughable even with an infinite supply of unobtanium and fairy dust.
  - f33d5173 6mo ago
    You don't need to keep shrinking features. Brute forcing is highly parallel; to break a key within a certain time frame all you need is a large enough quantity of chips. While it's in the realm of science fiction today, in a few centuries we might have nanorobots that can tile the entire surface of mars with processors. That would get you enough orders of magnitude of additional compute to break a 128 bit key. 256 bit would probably still be out though.

Strilanc 6mo ago

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.

rolph 6mo ago

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

gucci-on-fleek 6mo ago
> 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). [0]: https://en.wikipedia.org/wiki/One-time_pad https://en.wikipedia.org/wiki/One-time_pad
- rolph 6mo ago
  not trying to be obtuse, but there is at least one solution, the one used to decrypt. if you know something about the content e.g. it is for russians, or americans. you can use a frequency analysis to identify vowels. that goes for a simple substitution cypher that is relying on low frequency of usage[one time use] and does not keep it brief. when you further substitute numbers for words, you gain more room for verbosity. if you have high stakes, your message in the clear, should only be useful for a limited time, at the point that it is no longer actionable. im very familiar with one time pads random, and keyed. they are a little simple, you can use a triaxial scheme, or a tensor like scheme, for more leg room and more complexity. depending on what you are doing it may be necessary, to not carry any pads, but to have access at some point, to agreed upon keys, in order to generate a pad on the spot. or even work in your head, if you have skill. e.g. jackdwlovemybigsphnxfqurtz as a weak example.
  - 6mo ago

TacticalCoder 6mo ago

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?

quinnjh 6mo ago
> for RSA and ECC, is there anything preventing us from using keys 10x bigger? you can run benchmarks yourself: openssl speed rsa1024 rsa2048 also this (slightly dated) java ex writeup covers this well: https://www.javamex.com/tutorials/cryptography/rsa_key_length.shtml https://www.javamex.com/tutorials/cryptography/rsa_key_lengt... tldr trade off is found between better performance and how many years the data needs to be assumed confidential
dist-epoch 6mo ago
for a 10x bigger key the quantum computer needs to be 10x bigger - linear scaling. the time to run the algorithm has cubic scaling - 1000x more time required. but it remains exponentially faster, just 1 minute becomes 1 day, 1 day becomes 3 years. still "easily" broken
daneel_w 6mo ago
> 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.
briansmith 6mo ago
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).

rugina 6mo ago

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?

tptacek 6mo ago
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 6mo ago
  [deleted]
- kasey_junk 6mo ago
  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.
dlcarrier 6mo ago
Coherency To get useful results, a quantum computer needs all of its qbits to stay entangled with each other, until the entire group collapses into the result. With current technology, it is very difficult for a reasonable sized group of qbits to stay coherently entangled, so it can only solve problems that are also relatively easy to solve on classical computers. If someone today were to figure out how to keep large numbers of bits entangled, then quantum computing would instantly be able to break any encryption that isn't quantum safe. It's not something that we are slowly working toward; it's a breakthrough that we can't predict when, or even if, it will happen.
- Mithriil 6mo ago

daneel_w 6mo ago

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

farfatched 6mo ago
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.
- daneel_w 6mo ago
  Imagine if we would've had the same hesitant cost-first reasoning about Ed25519, and then again about ML-KEM and SNTRUP.
  - farfatched 6mo ago
    I didn't suggest cost-first. You suppose what happens if the OpenSSH maintainers considered the cost when implementing those algorithms? Perhaps they did, but decided the benefits were worth it.
mkj 6mo ago
What does ed448 mitigate against vs ed25519?
- daneel_w 6mo ago
  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.

deleted 6mo ago

[deleted]

michaelsmanley 6mo ago

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.

macshome 6mo ago
Agreed. He presents the math in a way that illustrates his point without being difficult for non-mathematicians to grasp. A lot of blogs get hung up in the math, even when it is just supporting evidence for a broader point.

staticassertion 6mo ago

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?

kirrent 6mo ago
The only caveat is that AES is not necessarily a black box. It's possible there may be hidden structure to take advantage of, but if there is there's no reason to suspect it's one that's amenable to a quantum speedup. As far as the Grover speedup goes, it's already optimal. Requiring O(sqrt(N)) queries is the proven lower bound for unstructured search.
amluto 6mo ago
Yes and no. Grover's algorithm is provably optimal [0]. No quantum algorithm will ever find an n-bit key by queries to any reasonable sort of oracle faster than Grover's algorithm, and Grover's algorithm is way too slow to be a serious problem. But symmetric ciphers are not black boxes. They're mostly built on some variant of a Feistel network, which is a very nice construction for turning a messy function into an invertible function that, in a potentially very strong sense, acts like a cryptographically secure permutation. When I was in grad school, one project I contemplated but never spent any real time on was trying to either generate a real security proof for quantum attacks on Feistel networks or to come up with interesting quantum attacks. And there is indeed an interesting quantum attack against 3-round Feistel networks [1]. This is interesting, because, depending on what sort of security is needed, three or four rounds of Feistel network are sufficient against classical attack [2]. Now ciphers like AES have many more than 3 rounds, so hopefully they're fine. But maybe they're not. My intuition is that there is probably a reasonably small n1 and a reasonably small n2 >= n1 (probably constants, maybe logarithmic in numbers of bits) for which there is no quantum algorithm that can break symmetric crypto given classical query access even to the round functions (n1) or quantum query access to the round functions (n2) [3], but I'm not aware of any proof of anything of the sort. And my intuition definitely should be be trusted fully! (Maybe, even if I'm wrong, there is still a number of rounds that is sufficient for security against query access to the entire cipher.) [0] The classic result is https://arxiv.org/abs/quant-ph/9701001 https://arxiv.org/abs/quant-ph/9701001 and there are newer, more exact results, e.g. https://arxiv.org/abs/0810.3647 https://arxiv.org/abs/0810.3647 [1] https://ieeexplore.ieee.org/document/5513654 https://ieeexplore.ieee.org/document/5513654 [2] https://en.wikipedia.org/wiki/Feistel_cipher https://en.wikipedia.org/wiki/Feistel_cipher [3] It would be extremely cool if someone built quantum computers and networks and storage such that two parties that don't trust each other could actually communicate and exchange (interesting [5]) qubits. I've written some fun papers on the possible implications of this. If we ever get the technology, then it might actually be meaningful to consider things like chosen-quantum-ciphertext attacks against a classical symmetric cipher. But that's many, many years away, and, in any case, an attacker will only ever get to do a quantum query attack against a cryptosystem if a victim lets them. [4] Otherwise all queries will be classical. [4] Or in very complex settings where there is an obfuscated black box, for example. This may be relevant for zk-snarks or similar constructions. [5] I don’t consider the optical qubits exchanged in commercial devices that supposedly implement quantum key distribution to be interesting. To the vendors of such devices, sorry.

nelox 6mo ago

Certainty is a wonderful thing

SipitenoMK 6mo ago

[flagged]

fred_is_fred 6mo ago

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?

kazinator 6mo ago

Quantum computers are mainly a threat to naive investors.

apgwoz 6mo ago
Yeah, but… what if?
- dboreham 6mo ago
  We found one :)
  - apgwoz 6mo ago
    Not at all. I was simply making a joke on the parallel exploration of states.
wasabi991011 6mo ago
Please follow the hackernews commenting guidelines in the future. It helps keep this place interesting. Shallow comments such as this one don't meaningful add to the conversation, and won't do much to convince others of your opinion. > Comments should get more thoughtful and substantive, not less, as a topic gets more divisive. > Don't be curmudgeonly. Thoughtful criticism is fine, but please don't be rigidly or generically negative. > Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something.

agent-kay 6mo ago

[flagged]

ardline 6mo ago

Interesting approach — curious how this scales under real load.

jeffrallen 6mo ago

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!

red_admiral 6mo ago

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.

jcalvinowens 6mo ago

> 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.

Luke25 6mo ago

[dead]

dogtimeimmortal 6mo ago

> there is a concrete danger to asymmetric cryptography 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/ 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...?

moktonar 6mo ago

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