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?
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.
> 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.
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.
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.
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 are you doing the key rotation? You have to have some way of authenticating with the rotation service, and what is to stop them from breaking THAT key, and getting their own new certificate? Or breaking the trusted root authority and giving themselves a key?
> 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 traffic is possible. Any TLS break delayed by more than 15 minutes would be worthless.
> Any TLS break delayed by more than 15 minutes would be worthless.
It sounds like you’re talking about breaking TLS’s key exchange? Why would this not have the usual issue of being able to decrypt recorded traffic at any time in the future?
Edit: If it’s because the plaintext isn’t useful, as knorker got at in a sibling comment… I sure hope we aren’t still using classical TLS by the time requiring it to be broken in 1 minute instead of 15 is considered a mitigation. Post-quantum TLS already exists and is being deployed…
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?
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.
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).
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.
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.
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.
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.
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.
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.
> You already have to assume the most likely adversary is the entity running the free wifi
why do you have to assume that?
you're at Acme Coffeeshop. their wifi password is "greatcoffee" and it's printed next to the cash register where all customers can see it.
with WPA2 you have to consider N possible adversaries - Acme Coffee themselves, as well as every single other person at the coffeeshop.
...and also anyone else within signal range of their AP. maybe I live in an apartment above the coffeeshop, and think "lol it'd be fun to collect all that traffic and see if any of it is unencrypted".
with WPA3 you only have to consider the single possible adversary, the coffeeshop themselves.
Because it's a near certainty (at least in the US) that businesses will spy on you to the extent that they can, but it's actually incredibly rare to be around a nerd with Wireshark? Things like facebook used to not use https long after public wifi was ubiquitous and you could easily sniff people, and it basically didn't matter. Now nearly everything uses TLS so it really doesn't matter. Actually most public wifi I encounter has no security.
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
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.
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.
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).
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.
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.
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.)
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?
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.
> 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.
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.
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.
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 are you doing the key rotation? You have to have some way of authenticating with the rotation service, and what is to stop them from breaking THAT key, and getting their own new certificate? Or breaking the trusted root authority and giving themselves a key?
> 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 traffic is possible. Any TLS break delayed by more than 15 minutes would be worthless.
> Any TLS break delayed by more than 15 minutes would be worthless.
It sounds like you’re talking about breaking TLS’s key exchange? Why would this not have the usual issue of being able to decrypt recorded traffic at any time in the future?
Edit: If it’s because the plaintext isn’t useful, as knorker got at in a sibling comment… I sure hope we aren’t still using classical TLS by the time requiring it to be broken in 1 minute instead of 15 is considered a mitigation. Post-quantum TLS already exists and is being deployed…
> Any TLS break delayed by more than 15 minutes would be worthless.
What makes you say that? This is the store now decrypt later attack, and it's anything but worthless.
Oh, worthless for your oauth? Uh… but how do you bootstrap the trust? Sounds to me like you need post quantum to carry the whole thing anyway.
Or you mean one key signs the next? Ok, so your bet is that within the time window an RSA key, RSA can't be cracked?
Why in the world would anyone want to depend on that? Surely you will also pair it with PQ?
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?
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.
You're clearly not using these keys in certificates, which would need to be signed by a root or interim CA on every update.
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).
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.
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.
> instantly
Shor's and Grover's still are algorithm that require a massive amount of steps...
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.
WPA3 moved from PBKDF to ECDH. AES CCMP and GCMP are still the underlying block ciphers in WPA3 with some other extensions for China
Just yesterday I used an IoT device with WEP as the only WiFi option. Needless tosay, I use the wired connection.
The say the 's' in IoT stands for secure, and from my experience that is true. Pretty much nothing is getting thrown out, because it isn't secure.
For what it's worth, cryptography engineers were generally not happy with the Dragonfly PAKE, and PQC was a legitimate concern even in 2012.
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
1: https://en.wikipedia.org/wiki/ML-KEM
2: https://en.wikipedia.org/wiki/Wi-Fi_Protected_Access#Lack_of...
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.
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.
> You already have to assume the most likely adversary is the entity running the free wifi
why do you have to assume that?
you're at Acme Coffeeshop. their wifi password is "greatcoffee" and it's printed next to the cash register where all customers can see it.
with WPA2 you have to consider N possible adversaries - Acme Coffee themselves, as well as every single other person at the coffeeshop.
...and also anyone else within signal range of their AP. maybe I live in an apartment above the coffeeshop, and think "lol it'd be fun to collect all that traffic and see if any of it is unencrypted".
with WPA3 you only have to consider the single possible adversary, the coffeeshop themselves.
Because it's a near certainty (at least in the US) that businesses will spy on you to the extent that they can, but it's actually incredibly rare to be around a nerd with Wireshark? Things like facebook used to not use https long after public wifi was ubiquitous and you could easily sniff people, and it basically didn't matter. Now nearly everything uses TLS so it really doesn't matter. Actually most public wifi I encounter has no security.
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
I wonder when the OpenSSH developers will change their stance on Ed448.
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.
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.
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).
> 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_lengt...
tldr trade off is found between better performance and how many years the data needs to be assumed confidential
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
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.
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.
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.)