Machine-code security of the Signal protocol

Signal’s protocol sets up encrypted conversations and updates the keys as messages are exchanged. Can formal proofs connect its security properties to the instructions that actually run in a compiled implementation?

Why it matters and what counts as progress

Why it matters: An abstract protocol proof describes an ideal sequence of operations. Proving a property about compiled code also has to account for implementation details such as stored session state and messages arriving out of order.

What counts as progress: Progress means linking an exact build to a precise property and attacker model. Proofs should identify which operations, cryptographic assumptions and session scenarios they cover.

How the problem developed

  1. 2017 · Security proof for an abstract protocol model [4]

    Katriel Cohn-Gordon, Cas Cremers, Benjamin Dowling, Luke Garratt and Douglas Stebila Extracted an abstract description from the implementation and proved core security properties under a model that accounts for ratcheting.

  2. 2024 · PQXDH specification analysis [5]

    Karthikeyan Bhargavan and colleagues Formalized and analyzed the PQXDH key agreement protocol in symbolic and computational models.

  3. 10 Nov 2026 · Machine-code security proofs [1][2]

    Google DeepMind with Gemini Carbon Reported Lean-checked proofs for the PQXDH and Triple Ratchet operations in an AArch64 harness built from libsignal.

AI contribution

AlphaProof Code: Verifying Signal’s Security at the Machine-Code Level

Swarat Chaudhuri, Andrew Ferraiuolo, Anton Kovsharov, Tej Chajed, Sam Schlesinger, Karn Seth, Jonathan Katz, Charles Sutton, Pushmeet Kohli

AlphaProof Code agents proved security properties of the PQXDH handshake and Triple Ratchet messaging for a command-line harness built from unmodified libsignal 0.105.4 and SPQR 1.6.0 on AArch64 Linux. The symbolic and computational proofs cover different properties and attacker models.

AI involvementAI-led
ImportanceMajor
Technical verificationFormal (Lean 4)
Human understandingPartial
Paper date:

Sources

  1. Chaudhuri and colleagues, AlphaProof Code technical report
  2. Google DeepMind’s Lean development for the Signal build
  3. Google DeepMind’s announcement and proof authorship
  4. Cohn-Gordon and colleagues, A Formal Security Analysis of the Signal Messaging Protocol
  5. Bhargavan and colleagues, Formal verification of the PQXDH key agreement protocol
Publication history