Signal Protocol and Post-Quantum Ratchets (opens in new tab)

https://news.ycombinator.com/item?id=39444500 Keep your phone number private with Signal usernames (2024-02-20, 1422 points, 890 comments)

In many countries your SIM card is tied to you, which is a huge deal-breaker.

  > identification via a phone number.

  > an authoritarian governments too may take ownership of a number at any moment.

Don't get me wrong, Signal has issues and we should be critical and hold them to high standards. BUT *they are only E2EE and low metadata Messenger that my grandma can use.* That's a big fucking deal. If we want secure communication to be common place we need to make sure it's usable. Sure, there's more secure and more private services, but none that my grandma could use.

I very much think signal should shift focus to privacy as they've got the security side pretty well handled (as this blog illustrates). But also these comments at the top of any signal thread feel a bit out of touch. Maybe I'm reading too much into it but there's a lot of people who confidently act like this compromises security or places harm on a user. The existence of a registered signal account means very little, especially as you note numbers can be spoofed. You need more than a number to hijack an account and hijacking only reveals messages moving forward while telling the compromised user they're compromised.

So can we focus on bigger issues? Can we critique while still recommending? I have no problem saying I have issues with signal and wish they did more while acknowledging that it is strongly my preferred means of contact and I try to convince others to talk to me that way. These things are not at odds. I've gone so far as donating to them several times because I use the service so much

[0] https://signal.org/bigbrother/

This problem is honestly minor compared to teaching users to have opsec practices suitable against such a threat.

https://molly.im/

Not iMessage, which is the largest messaging app in the US. Uniquely, it doesn't even have an android app, so android users have to pay $800 to buy a single-use device with an effectively worthless OS bundled on it just to be able to join group chats.

iMessage doesn't even have good crypto, the default settings include unencrypted iCloud backups of your iMessage data lol.

I'll take Signal, which works on my desktop linux machine and android phone, over iMessage any day of the week, but the US as a whole seems to have chosen differently

That's a big can of worms that invariably will impact their ability to deliver on their main mission - private IM. Eg of problems: Who gets dev access, how do you vet plugins/aps from deceiving users, would users understand the risks, when an app gets compromised how to fight malicious campaign to discourage using Signal etc. etc.

My one serious problem with Signal is that it silently goes out of date then stops sending notifications, so I miss messages entirely. Kind of its one job.

That's a fast on-ramp to an extremely shitty experience moving forward.

and it's a deliberate choice that they are defending for seceral years now, ever since they removed the submarine sound.

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

   Devices are always retrieving messages from their mailbox when they are 
   online, and as soon as the device confirms they’ve gotten a message, it is 
   deleted from the Signal servers.

   If a device has been offline for a while, it may have a lot of messages 
   waiting in its mailbox when it returns. Today, Signal will hold a message in 
   a device’s mailbox for up to 45 days, giving an idle device a chance to wake 
   up and fetch it.

So you're in an even worse post-quantum situation with email, even if you end up with TLS-encrypted PGP-encrypted messages, you're still not post-quantum secure.

In good approximation, nobody does that.

You don't have to imagine, there's literally a NSA datacenter in Utah for doing just that.

https://en.wikipedia.org/wiki/Utah_Data_Center

Harvard physicists working to develop game-changing tech demonstrate 3,000 quantum-bit system capable of continuous operation

https://news.harvard.edu/gazette/story/2025/09/clearing-sign...

PsiQuantum Raises $1 Billion, Says Its Computer Will Be Ready in Two Years

https://archive.is/AEuan

This seems to me the most valid reason. Any other secret is useless after 30 years.

Doesn't the fact that nobody has built apps on it indicate the license (AGPL 3) is a real issue for its ecosystem?

Everyone is worried about the fact that ML-KEM keys are so chonky, so PQ3 sends them out only occasionally while Signal chunks them up and sends them in pieces along with all normal messages. Signal's argument is that a huge re-keying message could be detected and blocked, and chunking them is both safer and smoother on bandwidth. Erasure coding will likely wind up costing a bit more overall bandwidth, but each message will be more consistently sized. Given the wide range of Signal's deployment posture, that is probably a wise tradeoff to make. I would expect that Apple has a bit more control over their networks and are in a better position to deal with adversaries attempting to actively block their re-key updates.

Given that, Apple can already decrypt messages of users, if so requested by law enforcement and intelligence agencies. No fancy quantum breaches needed.

“Signal Protocol” is a somewhat fuzzy description of whatever Signal does at a given point in time. Historically, this meant Double Ratchet, which is O(N) with the number of devices in a conversation. This uses elliptic curve cryptography to exchange keys (X25519); it was then extended to be PQ via PQXDH by adding Kyber512 to the initial key exchange, and has now also been extended to be PQ for subsequent ratcheting by mixing in the SQPR ratchet. Signal itself is obviously centralised; 3rd party implementations are forbidden; the implementation is AGPL+CLA. It has good metadata protection thanks to hiding group membership from the sender and “sealed sender” to hide the sender from the server too.

Matrix is an open standard communication protocol. It supports pluggable E2EE, although the only protocol in production right now is Olm+Megolm. Olm is an implementation of the Double Ratchet, and Megolm is a per-sender ratchet used to share keys with the group. The current implementation of Olm from the Matrix Fdn is an Apache-licensed project called vodozemac. This sprouted experimental PQXDH support in Jan 2024 (https://github.com/matrix-org/vodozemac/pull/120). Matrix is decentralised; anyone can run a server; multiple heterogeneous implementations are heavily encouraged. More metadata is exposed to the server than Signal - for instance the server can see the group membership, and key-value data is not encrypted (although we’re working on that right now: https://element.io/blog/hiding-room-metadata-from-servers/). Also, group membership is controlled by the server; clients warn when if unexpected users/devices are added, but the protocol does not forbid it. We’re also working on fixing that, but it is a huge change.

Finally, MLS (RFC 9420) is effectively a key exchange and group membership protocol. You can use it to add E2EE to messaging systems as an alternative to the Double Ratchet, while also using it to control group membership. By default it uses classical elliptic curve encryption, but there are proposals to make it PQ. It’s more performant than the double ratchet in that calculating new ratchets is O(log N). However, joining groups is still O(N). It’s much less mature than the Double Ratchet, more complicated, but benefits from significant cryptanalysis and formal verification thanks to being an IETF standard. It also seems to get significant hype just by being an IETF standard. It requires a centralised component to sequence MLS group operations, so to use it in systems like Matrix you have to extend it to be decentralised (see arewemlsyet.com). It doesn’t hide metadata from the server. It also doesn’t provide cryptographic deniability (unlike the double ratchet). It is not that widely deployed yet, although Google apparently uses it for RCS (presumably thanks to it being IETF and avoids any possible IPR questions over the double ratchet), which means it should be huge. Discord and Webex also use it for VoIP conferences.

Which of the so-called Signal competitors have implemented something like this already today?

But apparently there is an XMPP extension that implements the Double Ratchet algorithm that Signal is based on:

https://en.wikipedia.org/wiki/OMEMO