Comment by tptacek

Comment by tptacek 19 hours ago

40 replies

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.

elvisloops 19 hours ago

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.

  • SAI_Peregrinus 17 hours ago

    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.

    • tptacek 17 hours ago

      I think they're making a point that is broader than PQ and a more general complaint about Signal's direction.

    • cma 16 hours ago

      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?

  • jt2190 18 hours ago

    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.

    • elvisloops 17 hours ago

      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.

      • jfyi 16 hours ago

        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.

      • immibis 16 hours ago

        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.

    • Spooky23 16 hours ago

      I think you’re right.

      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.

    • heavyset_go 17 hours ago

      It's a technological one when the feature is offered to laymen for their convenience.

  • abdullahkhalids 16 hours ago

    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.

    • elvisloops 15 hours ago

      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.

      • jonathanstrange 15 hours ago

        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.

  • varenc 16 hours ago

    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.

    [0] https://github.com/tbvdm/sigtop

  • ragona 17 hours ago

    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.)

    • elvisloops 17 hours ago

      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.

      • Ajedi32 17 hours ago

        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.)

        • tptacek 17 hours ago

          Disappearing messages are an opsec feature for trusted counterparties, not a cryptographic feature. They are very much a real thing.

      • ragona 17 hours ago

        > encrypts it with a static key

        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.

a022311 19 hours ago

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?

  • Sesse__ 17 hours ago

    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.

    • immibis 16 hours ago

      They also don't know the random elements used in previous headers, since they're thrown away a few rounds after the message was decrypted.

ls612 19 hours ago

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?

  • twiggers 19 hours ago

    128-bit AES is fine. To run Grover’s algorithm against it you’d need to cover the moon with qubits.

  • dist-epoch 17 hours 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 17 hours ago

      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.

      • cyberax 16 hours ago

        You can trivially parallelize Grover's search by assigning each quantum computer it's own search space.

aborsy 17 hours 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 :)