Im feeling pretty dumb even after reading the tldr. Can anyone who is well versed in this explain how this is better or safer? I read about the time, will it now be slower to send messages?
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.
I 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.
The static symmetric key is fundamentally different from an ephemeral asymmetric key. We've no indication that symmetric encryption is vulnerable to "store now, decrypt later" attacks when used with a sufficiently long key, which Signal has. Non-post-quantum asymmertic cryptography is vulnerable to "store now, decrypt later" attacks, which is why forward secrecy is needed.
The backups feature doesn't open up any new vulnerability that didn't inherently exist in sending messages to someone else you might not fully trust. One person in a group chat can also take pictures of their phone's screen & upload your messages to the public.
Images can be modified, won't these essentially be signed as verifiably coming from the sender, or is cryptographic proof of that thrown away in what they store?
This 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.
There'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.
These 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.
Those are the breaks though when catering to a large audience with wildly differing threat models. Do you throw away users that are looking for a vague sense of security so they run off somewhere else less secure because you lack some feature?
If you are just looking for "secure(TM)[X]", you are making a mistake somewhere anyway.
If your life or livelihood depends on it, you learn what the impact of every choice is and you painstakingly keep to your opsec.
Somewhere between the two user action becomes a necessity. You need to judge where that point is for you and take responsibility for it because nobody else can guarantee it.
At the very least they should have excluded any chats with disappearing messages enabled from being included in backups.
With disappearing messages off it was already reasonable to assume that a compromise of a counterparty's phone would result in exposure of all previous messages, so enabling backups wouldn't expose you to new risk.
That would cater to those who want to keep their chat history forever without exposing those with disappearing messages enabled to new risk.
The history of Signal has been to provide the security properties we're talking about without users having to think about it or understand. To suddenly remove forward secrecy is a very big change, and it isn't one that they seem to have acknowledged or documented. Like this blog post: they are making an announcement that they have a "post-quantum ratchet," when they have effectively removed the ratchet. It's theater.
I think you missed the point entirely. You can't have security without thinking about it. You can have vague sense of security, which is the theater you are talking about.
Show me a company anywhere that can provide security without user thought and deliberate action. It's a fantasy to believe anything you don't have to think about isn't theater. Hell, if you aren't thinking about it, you're one of the actors in that theater.
But practically, it probably has more risk as people bypassing employer or legal controls think it’s “secure”. So they have conversations that they wouldn’t have.
The security problem that a messaging app like Signal solves is NOT: Allow a person to secure their communication against eavesdroppers.
It solves the problem: How can a group of people (two or more people) securely communicate with each other.
The group has to mutually decide their risk profile, and then decide which features of the application to use. And each person in the group has to decide whether they can trust others in the group to follow the agreed upon opsec. Signal cannot solve these social problems.
Historically as long as everything remained "in the app," it was secure. It's an easy assumption to make and communicate to others. Now it's more complicated: there are things that people can unwittingly do "in the app" that make it less secure.
AFAIK, it has the same security as before. Perfect forward secrecy means that if someone starts recording encrypted messages in transit and two years later obtains an encryption key, they cannot use that key to decrypt the messages they recorded earlier (because of re-keying).
On the other hand, if an adversary captures one of the group participants' phone and breaks device security, and the chat was recorded on that device, then they can access all recorded chats. By the same token, no cryptography can protect against a malicious group participant who records messages.
In the same scenario, cloud backups seem to merely imply that the same adversary can obtain the cloud backup key and therefore decipher the cloud backups if they get their hands on it. They won't need that, however, since the group chat history is already stored on the device. If no chats were recorded on the device at all the situation would be different.
You also have no way of knowing when someone you're chatting with screenshots your messages and uploads them to Imgur.
I jest, and Signal's support for backups do really increase exposure to this risk, but just trying to say its a matter of degree not a fundamentally new change. People that have been using sigtop[0] to backup their Signal messages to plaintext also create the same exposure risk.
I don't think that's quite right. PQ attacks focus on the "trapdoor" functions in asymmetric cryptography, _not_ the symmetric encryption that happens after key negotiation. The current concern is that a future attacker could unwrap the symmetric key, not directly attack the symmetric encryption that is used for something like backups.
(Note: I didn't actually dig into the backup implementation, but my guess is that it's more of a KDF -> symmetric design, rather than the sorts of asymmetric negotiation you'd find in multi-party messaging.)
If the app takes your disappearing message, encrypts it with a static key that never changes and is never deleted, and uploads it to the cloud, then the message is never truly "disappearing." A "post compromise" event will allow the attacker to decrypt that ciphertext at any point in the future. All of this ratcheting is undone by backups.
Disappearing messages were never a real thing in the first place. You can have a gentleman's agreement that the person you send your message to will delete it after reading it, there's no way to guarantee anything beyond that.
(Fair point though that probably "disappearing" messages shouldn't be included in backups since that obviously prevents them from being deleted. Idk if Signal implements that or not.)
What type of static key? If it's just a big symmetric key that isn't derived from an asymmetric handshake of some type then no, that's not our current understanding of the PQ threat model.
Part of the premise of FS/PCS is that "shit happens" to compromise keys even if the underlying cryptography is strong, so if you want a coherent end-to-end FS/PCS story, the claim would be that you need to be ratcheting everywhere.
Definitely, but when we're running around sprinkling PQ algorithms all over the place, it's on top of the asymmetric bits, not replacing the "boring" stuff like your symmetrically encrypted backups. Shit certainly does happen, especially where key management is involved, but I'm not sure I agree that offering an encrypted backup feature is necessarily undoing the FS/PCS story.
edit: Well, let me argue with myself for a moment. I don't think offering an encrypted backup feature undoes the PQ story. But FS/PCS is weakened, sure, since we're talking about all types of shit happening, not just currently known (or strongly theorized) attacks.
Yes, if Signal has effectively removed ratcheting and forward secrecy from the logical "encryption protocol" by encrypting all messages (even disappearing messages) with a single static key that never changes for your lifetime and sending them to the cloud, then all this talk about "post-quantum ratchets" is theater. There are no ratchets.
I'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?
The 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.
What 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?
> 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.
And 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.
Well, 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.
They 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.
>> 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 :)
Their existing post quantum encryption didn't do post compromise security (PCS) against quantum attackers. This new one does.
I am excited to finally know what they mean by PCS after reading this article. It means that the session keys from their key agreement scheme (n ratchet) are generated new so an attacker doesn't get them again after a fairly specific sort of compromise. So from that I get that the off the record (OTR) protocol also has PCS. Which is a bit disappointing, I thought that they had come up with some new concept.
This key agreement doesn't happen that often. So a user isn't going to notice any slowness even if it was significantly slower.
> "What does this mean for you as a Signal user? First, when it comes to your experience using the app, nothing changes. Second, because of how we’re rolling this out and mixing it in with our existing encryption, eventually all of your conversations will move to this new protocol without you needing to take any action. Third, and most importantly, this protects your communications both now and in the event that cryptographically relevant quantum computers eventually become a reality, and it allows us to maintain our existing security guarantees of forward secrecy and post-compromise security as we proactively prepare for that new world."
