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

Get email updates

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.

What was already known

Earlier analyses proved security properties of abstract Signal protocol models, including a formal analysis of PQXDH. The new proofs connect the modeled properties to a compiled reference implementation.

AI involvement AI-led

The authors credit Gemini Carbon agents with synthesizing the Lean proofs. Researchers guided the specification work, approved the statements and reviewed selected proof areas.

Importance Major

The proofs link a deployed protocol’s security model to concrete machine-code behavior, including how the implementation stores session state and handles messages. The authors report that Lean also proved violations for two historical bugs reintroduced into the build.

Technical verification Formal (Lean 4)

The paper reports that Lean checked the proofs and that a comparator matched them to held-out specifications. The checked conclusions depend on the stated cryptographic assumptions, routine contracts and AArch64 semantics.

Formal checking

The paper reports that Lean checked the proofs and that a comparator matched them to held-out specifications. The checked conclusions depend on the stated cryptographic assumptions, routine contracts and AArch64 semantics.

Checker
Lean kernel and Lean comparator as reported by Chaudhuri and colleagues
Scope
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.
Basis
Reported by the linked checker

Human understanding Partial

The authors explain how the proof connects binary traces to symbolic events and give the computational proof structure. The report does not document a human review of every generated argument.

Correction and publication history