We are excited to announce a significant advancement in the security of the Signal Protocol: the introduction of the Sparse Post Quantum Ratchet (SPQR). This new ratchet enhances the Signal Protocol’s resilience against future quantum computing threats while maintaining our existing security guarantees of forward secrecy and post-compromise security.
The Signal Protocol is a set of cryptographic specifications that provides end-to-end encryption for private communications exchanged daily by billions of people around the world. After its publication in 2013, the open source Signal Protocol was adopted not only by the Signal application but also by other major messaging products. Technical information on the Signal Protocol can be found in the specifications section of our docs site.
In a previous blog post, we announced the first step towards advancing quantum resistance for the Signal Protocol: an upgrade called PQXDH that incorporates quantum-resistent cryptographic secrets when chat sessions are established in order to protect against harvest-now-decrypt-later attacks that could allow current chat sessions to become compromised if a sufficiently powerful quantum computer is developed in the future. However, the Signal Protocol isn’t just about protecting cryptographic material and keys at the beginning of a new chat or phone call; it’s also designed to minimize damage and heal from compromise as that conversation continues.
We refer to these security goals as Forward Secrecy (FS) and Post-Compromise Security (PCS). FS and PCS can be considered mirrors of each other: FS protects past messages against future compromise, while PCS protects future messages from past compromise. Today, we are happy to announce the next step in advancing quantum resistance for the Signal Protocol: an additional regularly advancing post-quantum ratchet called the Sparse Post Quantum Ratchet, or SPQR. On its own, SPQR provides secure messaging that provably achieves these FS and PCS guarantees in a quantum safe manner. We mix the output of this new ratcheting protocol with Signal’s existing Double Ratchet, in a combination we refer to as the Triple Ratchet.
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.
The Current State of the Signal Protocol
The original Signal ratchet uses hash functions for FS and a set of elliptic-curve Diffie Hellman (ECDH) secret exchanges for PCS. The hash functions are quantum safe, but elliptic-curve cryptography is not. An example is in order: our favorite users, Alice and Bob, establish a long-term connection and chat over it regularly. During that session’s lifetime, Alice and Bob regularly agree on new ECDH secrets and use them to “ratchet” their session. Mean ol’ Mallory records the entire (encrypted) communication, and really wants to know what Alice and Bob are talking about.
The concept of a “ratchet” is crucial to our current non-quantum FS/PCS protection. In the physical world, a ratchet is a mechanism that allows a gear to rotate forward, but disallows rotation backwards. In the Signal Protocol, it takes on a similar role. When Alice and Bob “ratchet” their session, they replace the set of keys they were using prior with a new set based on both the older secrets and a new one they agree upon. Given access to those new secrets, though, there’s no (non-quantum) way to compute the older secrets. By being “one-way”, this ratcheting mechanism provides FS.
The ECDH mechanism allows Alice and Bob to generate new, small (32 bytes) data blobs and attach them to every message. Whenever each party receives a message from the other, they can locally (and relatively cheaply) use this data blob to agree on a new shared secret, then use that secret to ratchet their side of the protocol. Crucially, ECDH also allows Alice and Bob to both agree on the new secret without sending that secret itself over their session, and in fact without sending anything over the session that Mallory could use to determine it. This description of Diffie-Hellman key exchange provides more details on the concepts of such a key exchange, and this description of ECDH provides specific details on the variant used by the current Signal protocol.
Sometime midway through the lifetime of Alice and Bob’s session, Mallory successfully breaches the defences of both Alice and Bob, gaining access to all of the (current) secrets used for their session at the time of request. Alice and Bob should have the benefits of Forward Secrecy - they’ve ratcheted sometime recently before the compromise, so no messages earlier than their last ratchet are accessible to Mallory, since ratcheting isn’t reversible. They also retain the benefits of Post-Compromise Security. Their ratcheting after Mallory’s secret access agrees upon new keys that can’t be gleaned just from the captured data they pass between each other, re-securing the session.
... continue reading