4 ms·
Sure. In the standard practical analysis of quantum threats to cryptography, your adversary is "harvesting and then decrypting". Everybody agrees that no adver
by tptacek 1y ago
Sure.
In the standard practical analysis of quantum threats to cryptography, your adversary is "harvesting and then decrypting". Everybody agrees that no adversary can perform quantum cryptography today, but we agree (to agree) that they'll plausibly be able to at some point in the future. If you assume Signal is carrying messages that have to be kept secret many years into the future, you have to assume your adversary is just stockpiling Signal ciphertexts in a warehouse somewhere waiting so that 15 or 20 years from now they can decrypt them.
That's why you want PQ key agreement today: to protect against a future capability targeting a record of the past. (It's also why you don't care as much about PQ signatures, because we agree no adversary can time travel back and MITM, say, a TLS signature verification).
To understand the importance of a PQ ratchet, add one more capability to the adversary. In addition to holding on to ciphertexts for 15-20 years, assume they will eventually compromise a device, or find an implementation-specific flaw in cryptography code that they can exploit to extract key material. This is a very realistic threat model; in fact, it's of much more practical importance than the collapse of an entire cryptographic primitive.
You defend against that threat model with "forward secrecy" and "post-compromise security". You continually update your key, so the compromise of any one key doesn't allow an attacker to retrospectively decrypt, or to encrypt future messages.
For those defenses to hold against a "harvest and decrypt" attacker, the "ratchet" mechanism you use to keep re-keying your session also needs to be PQ secure. If it isn't, attackers will target the ratchet instead of the messages, and your system will lose its forward and post-compromise secrecy.
- ls612 1y agoWhat is the state of PQ symmetric crypto? My layman's understanding is that 128 bit AES is known to be broken by a quantum computer and that 256 AES may be OK but that isn't certain? Is this an additional vector for the "harvest and wait" strategy in the future?
- twiggers 1y ago128-bit AES is fine. To run Grover’s algorithm against it you’d need to cover the moon with qubits.
- ziofill 1y agowhich algorithm are you referring to?
- dist-epoch 1y ago> My layman's understanding is that 128 bit AES is known to be broken by a quantum computer Weakened, not broken. Quantum computers turns 128 bit AES into 64 bit equivalent. Which will still be extremely difficult for quantum computers due to the large computer size/number of steps required.
- SAI_Peregrinus 1y agoAnd it's 64-bit equivalent in a way that's inherently impossible to parallelize, so 2^64 sequential quantum operations. Those operations are much, much slower than classical ones.
- cyberax 1y agoYou can trivially parallelize Grover's search by assigning each quantum computer it's own search space.
- upofadown 1y agoYes, but then you give up the advantage that Grover's gives you in the first place. The advantage is sqrt(n). You are reducing n by parallelizing.
- cyberax 1y agoWell, you get sqrt(n / N) as a result. It works like any other parallel computation. E.g. if you have 256 quantum computers, then each one of them needs to search only 60 bits of the key space to crack a 128-bit key (each one of them will only need to search 2^120 keys). It's not really going to make much difference with near-future quantum computers. Especially since Grover's algorithm _has_ to complete all the 2^60 steps to produce a reliable result, you can't just run a quantum computer for a while, stop it, and then restart it.
- SAI_Peregrinus 1y agoThey still take the same amount of time to run it. You don't get a result by running for 1/n of the steps, so adding more QCs lets you attack more keys at once but doesn't let you attack any given key any faster.
- a022311 1y agoI'm slightly confused about the PCS part. If I've understood correctly the new key is derived from the old key + some kind or message header. If the attacker has access to a key and messages encrypted with it, can't they read the shared secret used for key exchange and use their existing key to generate the new one? Or is this only possible with ECDH and not KEM?
- Sesse__ 1y agoThe new one is randomly chosen (with the randomness coming from both parties, and then combined using ECDH and/or KEM). So you cannot predict it from previous key material, pretty much by definition.
- immibis 1y agoThey also don't know the random elements used in previous headers, since they're thrown away a few rounds after the message was decrypted.
- bilal4hmed 1y agoah ok, thank you. Starting to make sense now
- elvisloops 1y agoI think this used to be true. Now one problem is that a Signal message goes through this whole forward secrecy protocol, but the receiving device has some probability of uploading it to the cloud with a static key that never changes. You don't have to enable the Signal backups feature, but you have no way of knowing whether the recipient of your messages has. One person in a group chat with that enabled will undo all of the forward secrecy you're describing.
- jt2190 1y agoThis is no different than if recipient of the secure message shares the message in plaintext. The problem is a discipline problem not a technology one, and the solution is the same in both cases.
- elvisloops 1y agoThere's a difference between what Signal does in the app and a manual action a user performs outside of the app. It is not realistic to expect that people will see a feature Signal has built for them in the app and understand the underlying implications to "post compromise security" and "forward secrecy" that it may have. The expectation is that what happens inside Signal is secure, and the features Signal provides are secure. If the idea is that nobody is going to enable this feature, then why build it? If the idea is that many people are going to enable this feature, then this entire cryptographic protocol is meaningless.
- immibis 1y agoThese things can still be used as evidence. The process used by the police of a rogue country (or any other adversary) isn't a cryptographer's highly technical wet dream or nightmare. They simply look at the screen of your phone saying you sent or received a message, and as far as the adversary is concerned, that proves you sent or received it. Even if you didn't. (Actually, they use Cellebrite and just trust whatever the Cellebrite analyzer outputs, which is basically what your screen would have said) I've yet to see a protocol that lets you convincingly insert fake messages into both sides of your own chat history, especially in a way that isn't detectable by say, sqlite rowid order, but that would be an interesting idea for where to take this sort of thing.
- aborsy 1y ago>> Forward secrecy is somewhat overrated in end to end encrypted messaging. Most people do not want a truly off the record experience but instead keep their old messages around indefinitely. As long as those old messages exist and are accessible to the user they will be just as accessible to any attacker that gets access to the secret key material. On a more serious note, if a quantum computer can break a key, a task requiring exponential complexity with key length on a classical computer, then breaking N keys is only a negligible additional cost in comparison. So it kind of feels like it’s overrated in this case to be honest :)