The advent of quantum computing poses a significant threat to modern digital communication security, which relies on cryptographic protocols that are vulnerable to quantum attacks.
This piece explores Signal Protocol’s proactive measures to achieve quantum resistance. It details a two-phased approach, starting with the Post-Quantum Extended Triple Diffie-Hellman (PQXDH) protocol to secure initial key exchanges against “harvest now, decrypt later” attacks and then examines the introduction of the Sparse Post-Quantum Ratchet (SPQR), which forms the “Triple Ratchet” when combined with the Double Ratchet. This hybrid system provides ongoing quantum-safe forward secrecy and post-compromise security throughout a conversation’s life cycle.
Sunil Gentyala
The quantum threat to modern cryptography
Most current secure communication relies on public-key cryptography, such as RSA and elliptic curve cryptography (ECC), which are based on mathematical problems that are computationally infeasible for classical computers to solve. ECC’s security, for example, relies on the difficulty of the elliptic curve discrete logarithm problem. These systems enable the creation of a public key for encrypting messages and a private key for decrypting them.
However, large-scale quantum computers threaten to render these cryptographic foundations obsolete. A sufficiently powerful quantum computer could use algorithms like Shor’s algorithm to solve the underlying mathematical problems of both RSA and ECC, allowing an attacker to derive a private key from a public key and compromise communications.
This threat has led to the harvest now, decrypt later (HNDL) attack scenario, where an adversary collects and stores encrypted data to decrypt it when a powerful quantum computer becomes available. Post-quantum cryptography (PQC) has emerged to develop new cryptographic algorithms resistant to both classical and quantum computers.
The Signal Protocol: A pre-quantum overview
The Signal Protocol provides end-to-end encryption for asynchronous messaging and is the foundation for the Signal app’s security. It offers robust security guarantees, including:
Forward secrecy (FS): Past messages remain secure if a user’s keys are compromised.
Post-compromise security (PCS): The protocol can heal itself after key compromise.
These properties are achieved through the Double Ratchet algorithm, which continuously generates new encryption keys. The Double Ratchet relies on elliptic curve diffie-hellman (ECDH) key exchanges for PCS. However, ECDH is not quantum-resistant.
Phase 1: Securing the initial handshake with PQXDH
Signal introduced PQXDH to address HNDL attacks. PQXDH is a hybrid approach that combines a traditional X25519 elliptic curve key agreement with a post-quantum key encapsulation mechanism (KEM), specifically CRYSTALS-Kyber. An attacker must break both classical and post-quantum algorithms to compromise the initial encryption key.
Phase 2: Ongoing quantum-safe security with SPQR and the Triple Ratchet
While PQXDH secures the initial handshake, the Double Ratchet’s ongoing security remained vulnerable to quantum attacks, so Signal developed SPQR to provide quantum-safe FS and PCS. SPQR runs parallel with the Double Ratchet, forming the Triple Ratchet.
Challenges and solutions in SPQR
Integrating a post-quantum KEM into a continuous ratcheting protocol presented challenges:
Key size: Post-quantum KEMs have larger key sizes compared to ECDH.
Asynchronous communication: The protocol must be robust against message loss and offline users.
Security vs. speed: Generating keys too far in advance could expose future epochs to compromise.
SPQR incorporates:
State machine: Coordinates key material exchange between parties.
Erasure codes: Breaks key material into smaller chunks for transmission.
Optimized ML-KEM Braid: Allows parallel transmission of key material.
The Triple Ratchet derives the final encryption key from both the Double Ratchet and SPQR, ensuring hybrid security.
Formal verification and future-proofing
Signal emphasized formal verification from the outset, collaborating with academic researchers and using ProVerif for machine-verified proofs. The Rust implementation is translated into F* verification language using hax on every code change.
A step forward, but the work continues
Signal’s adoption of post-quantum cryptography represents a significant step forward in securing digital communications. By implementing PQXDH and introducing SPQR to create the Triple Ratchet, Signal has built a robust defense system providing quantum-resistant forward secrecy and post-compromise security.
The rollout is designed to be seamless for users. Through cutting-edge research, innovative solutions and formal verification, Signal Protocol has established a new benchmark for secure messaging in the quantum era.
Global internet data on the topic includes various research papers and articles discussing post-quantum cryptography and its applications in secure messaging protocols. Some notable works include:
Research on post-quantum ratcheted key exchange from coding assumptions, which proposes a practical post-quantum RKE protocol based on the Syndrome Decoding problem.
Signal’s blog post on Signal Protocol and Post-Quantum Ratchets, which announces the introduction of SPQR and its benefits.
Research on Ilyazh-Web3E2E, a hybrid post-quantum-resilient end-to-end messaging protocol that combines classical X25519 with a NIST-selected KEM.
Research on K-Waay, a fast and deniable post-quantum X3DH protocol without ring signatures, which proposes an efficient and deniable post-quantum X3DH-like protocol.
These works demonstrate the ongoing efforts to develop quantum-resistant cryptographic protocols and their potential applications in secure messaging.
This article is published as part of the Foundry Expert Contributor Network.
Want to join?
No Responses