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 13 minutes 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.
bob1029 47 minutes 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 35 minutes 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 18 minutes 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).
rugina 6 minutes 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?
kd913 1 hours 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_ 1 hours 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
tptacek 32 minutes ago [-]
For what it's worth, cryptography engineers were generally not happy with the Dragonfly PAKE, and PQC was a legitimate concern even in 2012.
evil-olive 48 minutes 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.
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 17 minutes 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.
rolph 25 minutes 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
TacticalCoder 24 minutes 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?
Strilanc 28 minutes 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.
occamofsandwich 2 hours 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 2 hours 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 23 minutes 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.)
jeremie_strand 4 hours ago [-]
[dead]
Rendered at 20:25:21 GMT+0000 (Coordinated Universal Time) with Vercel.
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?
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.
What is going on?
WPA3 moved from symmetric AES to ECDH which is vulnerable to Quantum. Gonna be a tonne of IOT inverters waste.
...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...
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
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?
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.