Quantum Computers Are Not a Threat to 128-bit Symmetric Keys
64 points by Shorden
64 points by Shorden
Very nice article. But there is one thing I don't understand. If key exchange algorithms like ECDH are in danger of being broken, then all currently happening symmetric encryption which is set up using ECDH can be recorded now and later decrypted?
This would mean that currently, Alice could record all of Bob's https traffic, and have some hope that in, say, 40 years, she can decrypt it all. Is this understanding correct?
Yes, that’s why people are recommending adopting PQC for key exchange now, rather than after quantum computers exist.
The danger of that depends a lot on the use case. For a lot of things, TLS is really there for authentication and integrity: I am really talking to the server I think I am talking to, and no one can tamper with messages in either direction.
If you’re using passwords to log in, there’s a danger that someone can record the session and, later, decrypt the messages in both directions and get your password. That won’t be cheap for a while after quantum computers exist, so is not a huge threat for non-critical systems. Banks might worry though.
Passkeys are more interesting. The standards now support using PQC and, I believe, there’s a flow for a client to say ‘you know me by this public key, but I am also known by this public key for a stronger algorithm’. If you do that, you don’t need to actually deploy PQC for passkeys, just make sure you have the public keys on file. When quantum computers look plausible, you can switch over to rejecting quantum-vulnerable algorithms.
This is more or less Soatok’s point about signatures. For key exchange, store and decrypt later is a valid attack. For signatures, you check the signature at a point in time and you need to worry only about attacks on the signature scheme that are possible before you check it. As long as you can move to a different signature scheme, you’re fine. This is less true for long-lived signatures: if you’re signing something now and someone wants to verify the authenticity in ten years, now would be a really good time to discover ML-DSA.
Yes, I think that is why OpenSSH began warning if you don't use PQ: https://www.openssh.org/pq.html IT says you are vulnerable to a "store now, decrypt later" attack.
I'm not a cryptographer, but to my understanding yes, that's correct. ECDH is used to derive the symmetric AES key, so if you record both the ECDH exchange and the symmetric AES encrypted traffic after it, then in 40 years you'll be able to (i) break the ECDH exchange to learn the symmetric AES key, then (ii) use that key to decrypt the traffic.
I'm guessing that when quantum computers are on the verge of decrypting ECDH there will be a big push to get people to change e.g. their bank passwords if they've been using them for a long time.
The article merely states that AES is secure, and of course the entire system is not secure if the AES key can be decrypted during exchange. However, there is also symmetric encryption using pre-agreed keys: e.g., AES for encrypting hard drives, files, and backups, and that is post-quantum secure.
Interestingly, a lot of IoT things use TLS with AES and pre-shared keys, because even ECDH is hard on tiny embedded devices. This remains secure (as long as the keys are not leaked: the fact that this is hard is a big part of why people don’t do this in other contexts).
Some systems also have a SHA-256-based KDF and a secret that generates an AES key from the secret and a nonce (often a device ID and a random number), which should also be fine, if I understand correctly.
I knew that there were attacks better than grovers already, but I'm glad we have found an upper limit.
I read the article but didn't see any discussion of attacks better then Grover, or any upper limits, can you explain?