1. Signal secures its chats against quantum computers

• Protection before and after the disaster
• Cleverly split
• Error-free roll-out

Messenger Signal has introduced a new key exchange protocol for its communication service. “SPQR” is also designed to protect messages from attackers using quantum computers and adds a third component to the double ratchet method established by Signal, which is why the developers now refer to it as “Triple Ratchet.”

SPQR does not stand for the Senate and the people of Rome, but for “Sparse Post-Quantum Ratchet.” Post-quantum methods are cryptographic protocols that conventional computers can execute but which, according to the current state of science, cannot be cracked even by quantum computers. There are currently no quantum computers that have the potential to attack conventional encryption and signature processes. But people are afraid of “harvest now, decrypt later” attacks. Encrypted data could be recorded today to decrypt it in the future, when (and if) quantum computers are available.

Signal has been using the post-quantum protocol PQXDH (Post-Quantum Extended Diffie-Hellman) for some time now, but this is only used for the initial key exchange at the start of a conversation. SPQR, on the other hand, generates new keys during ongoing communication, similar to the two existing “ratchets,” but these are not secure against quantum computers.

Protection before and after the disaster

These “ratchets” are components of the protocol that can symbolically only be turned in one direction: chat participants can use them to continuously generate new keys, from which no conclusions can be drawn about older keys. This means that attackers cannot decrypt ciphertext recorded in the past, even if they compromise one (or both) chat partners and capture the current secret keys—a feature known as “forward secrecy”.

Furthermore, signal ratchets offer “post-compromise security”: because the devices of conversation partners also negotiate keys interactively, the communication can recover from the compromise of the chat participants and securely encrypt future messages again. The attacker is, so to speak, kicked off the line as long as he does not have permanent access to the keys of the affected devices. Such self-healing after a temporary compromise is relevant, for example, when attackers capture backups. These provide them with access to the keys used at the time of the backup. This allows them to decrypt some of the messages they have recorded, even if the messages have been deleted from the chats and are not included in the backup. However, because Signal’s previous “asymmetric ratchet” and, in the future, SPQR will also negotiate new keys in the ongoing conversation, the keys captured by the attacker will eventually become obsolete. Communication is then secure again.

Cleverly split

SPQR does not replace the asymmetric ratchet but comes in addition to it. This is partly due to a hurdle that many post-quantum methods have: their keys are large, in Signal’s case over a kilobyte. This is not only a lot compared to the 32-byte keys of the classic asymmetric ratchet, but also a lot compared to the size of a typical text message. Therefore, SPQR does not immediately establish a new key with every change in the direction of communication (as the classic asymmetric ratchet does). Instead, SPQR distributes its keys over several messages, thus minimizing the overhead.

However, the protocol does not simply divide the keys into n parts but uses erasure codes to encode key fragments. In this way, the recipient can use the new key as soon as it has received n messages with key parts, regardless of which n messages they are. Attackers therefore cannot prevent new keys by allowing most messages to pass but blocking every nth message, for example.

In one-sided chats, however, in which one party sends many more messages than the other, even this division does not solve all problems: the silent partner hinders quick key changes, which the talkative chatter could make good use of. Signal therefore modifies the underlying post-quantum method ML-KEM 768 so that conversation partners can generate and transmit key fragments themselves more quickly and do not have to wait until they have received all n fragments from the other party. Signal calls the resulting incremental procedure “ML-KEM Braid” and has documented it as a separate protocol.

Error-free roll-out

SPQR and its components are complex procedures whose security properties can be disrupted by both design and implementation errors. Signal tries to prevent the former through peer review. The developers refer to two papers at the relevant Eurocrypt and USENIX conferences, which present partial aspects of the protocol. Signal aims to avoid implementation errors through extensive formal verification: The SPQR code written in Rust is continuously and automatically translated into the F* language and then formally verified. F* is a functional, “proof-oriented” language that is well suited for automated proofs. In this way, Signal wants to ensure that the software still maintains all the assumptions, constraints, and guarantees of SPQR every time the code is updated.

Signal also describes how the protocol should be distributed in the SPQR blog post: Initial SPQR data is sent by the messenger in such a way that older Signal versions that cannot do anything with it ignore the data. However, the established message authentication does capture the data so that attackers cannot simply remove it and thus keep the chat SPQR-free. New clients allow a downgrade at the start of a conversation: if the partner does not speak SPQR, the protocol is not used. Signal wants to prevent downgrade attacks that exploit such behavior by only allowing the downgrade at the start of a conversation. Once SPQR is activated, it must continue to be used. When SPQR-enabled clients have become sufficiently widespread, Signal wants to remove the downgrade option with a further update and force SPQR for all chats. Remaining chats without SPQR will then be archived.

Many more details on the protocol (and some ideas that were ultimately discarded) can be found in Signal’s detailed blog post on SPQR. Researchers from PQShield, who were involved in the development of the protocol, have also blogged about their work on SPQR. (mma)

Don’t miss any news – follow us on Facebook, LinkedIn or Mastodon.

This article was originally published in German. It was translated with technical assistance and editorially reviewed before publication.