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
- 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.
- 2024 · PQXDH specification analysis [5]
Karthikeyan Bhargavan and colleagues Formalized and analyzed the PQXDH key agreement protocol in symbolic and computational models.
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
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.
Sources
- Chaudhuri and colleagues, AlphaProof Code technical report
- Google DeepMind’s Lean development for the Signal build
- Google DeepMind’s announcement and proof authorship
- Cohn-Gordon and colleagues, A Formal Security Analysis of the Signal Messaging Protocol
- Bhargavan and colleagues, Formal verification of the PQXDH key agreement protocol
Publication history
AlphaProof Code: Verifying Signal’s Security at the Machine-Code Level
Daily emails by default, only when there’s an update.