Overview

Signal has added post-quantum cryptography with a new protocol called the SPQR (Sparse Post-Quantum Ratchet). This combines with Signal’s existing Double Ratchet to form a Triple Ratchet system.

Signal uses the quantum-secure Key-Encapsulation Mechanism (ML-KEM 768) algorithm alongside traditional elliptic curve cryptography, which means attackers need to break both elliptic curve and ML-KEM cryptography to read messages.

Signal are rolling out this new protocol in multiple phases - initially allowing older non-SPQR clients to interact with up-to-date clients and for older sessions (which might last for years) to continue working. In their final phase (once Signal have determined that all clients support the new protocol) older sessions will be upgraded to use SPQR. These phases are being planned to ensure nothing changes from an end-user experience.

OpenSSH and TLS comparisons

My previous post on post-quantum cryptography reviewed how SSH and TLS have changed to support post-quantum cryptography. Signal’s implementation needed to meet a different set of techincal challenges including both minimisation of overhead for the messenging protocol and also continuing to ensure Forward Secrecy (FS) and Post-Compromise Security (PCS).

OpenSSH vs Signal: Different Problems, Different Solutions

OpenSSH and Signal both use hybrid post-quantum key exchange, but their implementations differ based on how the protocols work.

Protocol Differences

OpenSSH: Connection-Based

  • Each SSH connection performs one key exchange at startup
  • Key exchange happens once, then the connection uses symmetric encryption
  • Bandwidth overhead: ~1KB one-time cost per connection
  • Each connection is independent

Signal: Message-Based

  • Bandwidth use and cost are a major consideration
  • Keys update continuously (ratcheting) during conversations
  • Messages can arrive out of order or get delayed
  • Conversations last days, weeks, months, years
  • Messages send asynchronously
  • State management across message streams

Technical Challenges

Bandwidth

Elliptic curve key exchange uses 32 bytes. ML-KEM uses over 1,000 bytes. For many small messages over slower and potentially expensive mobile data this creates efficiency problems.

Signal’s approach is a compromise between efficiently using the bandwidth (and handling out-of-order or lost packets) and reducing the impact on Forward Secrecy if a client is compromised.

Deployment Approaches

OpenSSH Gradual Adoption

  • Default algorithm list includes PQC (sntrup761x25519-sha512, mlkem768x25519)
  • Automatic negotiation: PQC activates when both client and server support it
  • Falls back to classical algorithms with older versions
  • All SSH clients still connect
  • Systems with immediate higher-security concerns can mandate PQC algorithms to protect against “Harvest now, decrypt later” attacks.

Signal Phased Rollout

  1. New conversations use SPQR when both participants updated
  2. Legacy clients use classical cryptography
  3. Once SPQR starts, downgrade attacks are blocked
  4. Non-SPQR conversations will eventually be force upgraded

PQC Implementation Considerations

OpenSSH and Signal show how different protocols need different PQC approaches:

  1. Protocol type matters - Connection-based protocols integrate PQC more simply than message-based protocols
  2. Bandwidth needs vary - One-time overhead works for connections, continuous messaging needs optimization
  3. Requirements vary - Signal uses ratcheting to provide Forward Secrecy (FS) and Post-Compromise Security (PCS)
  4. Hybrid cryptography is common - Both implementations mix classical and post-quantum algorithms

References: