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

Paper › Symbolic/Specifications/Security › Model.leanTier 2 · definitions

Model.lean🔗

Tier 2 · definitions used by the symbolic proof 12 headline theorems depend on it 257 of 403 lines trusted source ↗

trust banner in the header: none; the closure computes B2 for the symbolic proof

Read the definitions shown. Only the declarations that the headline statements use are shown, with the namespace, section, open and variable commands needed to read them. The collapsed runs are theorems, which Lean checks, and definitions that no headline statement uses.

Declarations on this page (46)

Symbolic Security Queries and Reachable-Trace Statements

Defines the ten whole-trace security queries for the composed protocol (FSQuery, PCSQuery, Theorems 7 to 9, and the five Theorem 1 corollaries of Bhargavan et al. and Cheval et al.) and quantifies them over reachable traces of Composed.reachability (AllModelSecurityQueriesHold).

@[expose] public section
section
namespace DY.Libsignal.PQXDH
open scoped Composed
open Composed (ComposedEvent)
open TripleRatchet (TREvent)
section

def IsHandshakeBlockL52–54 ↗#

k is one of the three 32-byte blocks (rk, ck, pqr) of keys.

def IsHandshakeBlock (keys: HandshakeKeys) (k: Bytes): Prop := k = keys.rk ∨ k = keys.ck ∨ k = keys.pqr

def HandshakeCompletedAtL56–60 ↗#

AliceDone or BobDone was logged at trace index i with keys.

def HandshakeCompletedAt (tr : ExecTrace) (a b : Participant) (ikA ikB spk pqpk : Bytes) (opk : Option Bytes) (keys : HandshakeKeys) (i : Nat) : Prop := (∃ ek ct, tr.EventLoggedAt (PQXDHEvent.AliceDone a b ikA ikB spk pqpk opk ek ct keys) i) ∨ (∃ ek ct, tr.EventLoggedAt (PQXDHEvent.BobDone b a ikB ikA spk pqpk opk ek ct keys) i)

def HandshakeKeysAtL62–63 ↗#

def HandshakeKeysAt (tr: ExecTrace) (j: Nat) (keys: HandshakeKeys): Prop := ∃ a b ikA ikB spk pqpk opk, HandshakeCompletedAt tr a b ikA ikB spk pqpk opk keys j

def SessionStateExposedL65–73 ↗#

Block k of keys was directly exposed as Triple Ratchet session state (ExposedSpqr for pqr, ExposedCKr / ExposedCKs for ck, or ExposedRK for rk) on a session started by a handshake deriving keys.

def SessionStateExposed (tr: ExecTrace) (keys: HandshakeKeys) (k: Bytes): Prop := ∃ s j, tr.EventLogged (ComposedEvent.HandshakeSession s j) ∧ HandshakeKeysAt tr j keys ∧ ((k = keys.pqr ∧ ∃ sp r, tr.EventLogged (TREvent.ExposedSpqr s sp r)) ∨ (k = keys.ck ∧ ∃ n r, tr.EventLogged (TREvent.ExposedCKr s keys.ck n r)) ∨ (k = keys.ck ∧ ∃ n r, tr.EventLogged (TREvent.ExposedCKs s keys.ck n r)) ∨ (k = keys.rk ∧ ∃ r, tr.EventLogged (TREvent.ExposedRK s keys.rk r)))

def HandshakeBlocksSecretL75–77 ↗#

Every block of keys not exposed via SessionStateExposed is unknown under Knows.

def HandshakeBlocksSecret (tr : ExecTrace) (Knows : Bytes → Prop) (keys : HandshakeKeys) : Prop := ∀ k, IsHandshakeBlock keys k → ¬ SessionStateExposed tr keys k → ¬ Knows k

def LoggedBeforeL79–80 ↗#

def LoggedBefore (ev: PQXDHEvent) (i: Nat) (tr: ExecTrace): Prop := ∃ j, tr.EventLoggedAt ev j ∧ j < i

def OPKAbsentOrCompromisedL82–83 ↗#

def OPKAbsentOrCompromised (b: Participant) (opk: Option Bytes) (i: Nat) (tr: ExecTrace): Prop := opk = none ∨ ∃ o, opk = some o ∧ LoggedBefore (PQXDHEvent.CompromisedOPK b o) i tr

def PQProtectionBypassedL85–86 ↗#

def PQProtectionBypassed (b : Participant) (pqpk : Bytes) (tr : ExecTrace) : Prop := tr.EventLogged (PQXDHEvent.CompromisedPQSPK b pqpk) ∨ tr.EventLogged PQXDHEvent.BrokenKEM

def SameDHKeyL88–90 ↗#

Equality of X25519 public keys up to normalizeX25519Key.

def SameDHKey (pk pk': Bytes): Prop := X25519.normalizeX25519Key pk = X25519.normalizeX25519Key pk'

def SameOPKL92–93 ↗#

def SameOPK (o o': Option Bytes): Prop := o.map X25519.normalizeX25519Key = o'.map X25519.normalizeX25519Key

def AliceHandshakeWasCompromisedL95–105 ↗#

Compromise excuse for Alice's handshake key at i (Bhargavan et al., Theorem 7): either IK_B was compromised (before i, or alongside spk and PQProtectionBypassed), or BrokenDH occurred (before i, or alongside PQProtectionBypassed).

def AliceHandshakeWasCompromised (b: Participant) (ikB spk pqpk: Bytes) (i: Nat) (tr: ExecTrace): Prop := (∃ j, tr.EventLoggedAt (PQXDHEvent.CompromisedIK b ikB) j ∧ (j < i ∨ (tr.EventLogged (PQXDHEvent.CompromisedSPK b spk) ∧ (tr.EventLogged (PQXDHEvent.CompromisedPQSPK b pqpk) ∨ tr.EventLogged PQXDHEvent.BrokenKEM)))) ∨ (∃ j, tr.EventLoggedAt PQXDHEvent.BrokenDH j ∧ (j < i ∨ tr.EventLogged (PQXDHEvent.CompromisedPQSPK b pqpk) ∨ tr.EventLogged PQXDHEvent.BrokenKEM))

def AliceInitiatorSecrecyQueryL107–112 ↗#

Secrecy of Alice's handshake blocks (Theorem 7).

def AliceInitiatorSecrecyQuery (tr: ExecTrace) (Knows: Bytes → Prop): Prop := ∀ a b ikA ikB spk pqpk opk ek ct keys i, tr.EventLoggedAt (PQXDHEvent.AliceDone a b ikA ikB spk pqpk opk ek ct keys) i → ∀ k, IsHandshakeBlock keys k → Knows k → AliceHandshakeWasCompromised b ikB spk pqpk i tr ∨ SessionStateExposed tr keys k

def HandshakeAuthWasCompromisedL114–120 ↗#

Pre-acceptance authentication compromise excuse at i (Theorem 8): IK_A, Bob's spk, or DH was compromised strictly before i.

def HandshakeAuthWasCompromised (b a : Participant) (ikA spk : Bytes) (i : Nat) (tr : ExecTrace) : Prop := LoggedBefore (PQXDHEvent.CompromisedIK a ikA) i tr ∨ LoggedBefore (PQXDHEvent.CompromisedSPK b spk) i tr ∨ LoggedBefore PQXDHEvent.BrokenDH i tr

def ResponderSessionAgreementL122–128 ↗#

Agreement witness for Theorem 8: a logged AliceDone strictly before i on the same pqpk, spk (up to SameDHKey), and opk (up to SameOPK).

def ResponderSessionAgreement (a: Participant) (spk pqpk: Bytes) (opk: Option Bytes) (i: Nat) (tr: ExecTrace): Prop := ∃ b' ikA' ikB' spk' opk' ek' ct' keys' j, tr.EventLoggedAt (PQXDHEvent.AliceDone a b' ikA' ikB' spk' pqpk opk' ek' ct' keys') j ∧ j < i ∧ SameDHKey spk spk' ∧ SameOPK opk opk'

def AuthenticationQueryL130–134 ↗#

Authentication of Alice to Bob (Theorem 8).

def AuthenticationQuery (tr: ExecTrace): Prop := ∀ b a ikB ikA spk pqpk opk ek ct keys i, tr.EventLoggedAt (PQXDHEvent.BobDone b a ikB ikA spk pqpk opk ek ct keys) i → ResponderSessionAgreement a spk pqpk opk i tr ∨ HandshakeAuthWasCompromised b a ikA spk i tr

def BobHandshakeWasCompromisedL136–146 ↗#

Compromise excuse for Bob's handshake key at i (Theorem 9): pre-acceptance authentication compromise, compromise of all of Bob's session secrets (IK_B, spk, opk, and pqpk/KEM), or BrokenDH paired with PQProtectionBypassed.

def BobHandshakeWasCompromised (b a : Participant) (ikB ikA spk pqpk : Bytes) (opk : Option Bytes) (i : Nat) (tr : ExecTrace) : Prop := HandshakeAuthWasCompromised b a ikA spk i tr ∨ (tr.EventLogged (PQXDHEvent.CompromisedIK b ikB) ∧ tr.EventLogged (PQXDHEvent.CompromisedSPK b spk) ∧ OPKAbsentOrCompromised b opk i tr ∧ PQProtectionBypassed b pqpk tr) ∨ (tr.EventLogged PQXDHEvent.BrokenDH ∧ PQProtectionBypassed b pqpk tr)

def HandshakeWasCompromisedAtL148–154 ↗#

def HandshakeWasCompromisedAt (tr: ExecTrace) (j: Nat): Prop := (∃ a b ikA ikB spk pqpk opk ek ct keys, tr.EventLoggedAt (PQXDHEvent.AliceDone a b ikA ikB spk pqpk opk ek ct keys) j ∧ AliceHandshakeWasCompromised b ikB spk pqpk j tr) ∨ (∃ b a ikB ikA spk pqpk opk ek ct keys, tr.EventLoggedAt (PQXDHEvent.BobDone b a ikB ikA spk pqpk opk ek ct keys) j ∧ BobHandshakeWasCompromised b a ikB ikA spk pqpk opk j tr)

def BobResponderSecrecyQueryL156–161 ↗#

Secrecy of Bob's handshake blocks (Theorem 9).

def BobResponderSecrecyQuery (tr: ExecTrace) (Knows: Bytes → Prop): Prop := ∀ b a ikB ikA spk pqpk opk ek ct keys i, tr.EventLoggedAt (PQXDHEvent.BobDone b a ikB ikA spk pqpk opk ek ct keys) i → ∀ k, IsHandshakeBlock keys k → Knows k → BobHandshakeWasCompromised b a ikB ikA spk pqpk opk i tr ∨ SessionStateExposed tr keys k

def FSPremiseL163–170 ↗#

Premise for handshake forward secrecy at i: identity keys are compromised only after i, session spk and pqpk are uncompromised, and neither DH nor the KEM is broken.

def FSPremise (a b: Participant) (ikA ikB spk pqpk: Bytes) (i: Nat) (tr: ExecTrace): Prop := (∀ j, tr.EventLoggedAt (PQXDHEvent.CompromisedIK a ikA) j → i < j) ∧ (∀ j, tr.EventLoggedAt (PQXDHEvent.CompromisedIK b ikB) j → i < j) ∧ ¬ tr.EventLogged (PQXDHEvent.CompromisedSPK b spk) ∧ ¬ tr.EventLogged (PQXDHEvent.CompromisedPQSPK b pqpk) ∧ ¬ tr.EventLogged PQXDHEvent.BrokenDH ∧ ¬ tr.EventLogged PQXDHEvent.BrokenKEM

def ForwardSecrecyQueryL172–177 ↗#

Handshake forward secrecy (Theorem 1).

def ForwardSecrecyQuery (tr : ExecTrace) (Knows : Bytes → Prop) : Prop := ∀ a b ikA ikB spk pqpk opk keys i, HandshakeCompletedAt tr a b ikA ikB spk pqpk opk keys i → FSPremise a b ikA ikB spk pqpk i tr → HandshakeBlocksSecret tr Knows keys

def HNDLPremiseL179–187 ↗#

Premise for harvest-now-decrypt-later resistance at i: BrokenDH occurs only after i, the KEM is unbroken, and ikA, ikB, spk, and pqpk are not explicitly compromised.

def HNDLPremise (a b: Participant) (ikA ikB spk pqpk: Bytes) (i: Nat) (tr: ExecTrace): Prop := (∀ j, tr.EventLoggedAt PQXDHEvent.BrokenDH j → i < j) ∧ ¬ tr.EventLogged PQXDHEvent.BrokenKEM ∧ ¬ tr.EventLogged (PQXDHEvent.CompromisedIK a ikA) ∧ ¬ tr.EventLogged (PQXDHEvent.CompromisedIK b ikB) ∧ ¬ tr.EventLogged (PQXDHEvent.CompromisedSPK b spk) ∧ ¬ tr.EventLogged (PQXDHEvent.CompromisedPQSPK b pqpk)

def HNDLQueryL189–194 ↗#

Harvest-now-decrypt-later resistance (Theorem 1).

def HNDLQuery (tr : ExecTrace) (Knows : Bytes → Prop) : Prop := ∀ a b ikA ikB spk pqpk opk keys i, HandshakeCompletedAt tr a b ikA ikB spk pqpk opk keys i → HNDLPremise a b ikA ikB spk pqpk i tr → HandshakeBlocksSecret tr Knows keys

def KCIQueryL196–202 ↗#

Key-compromise-impersonation resistance (Theorem 1).

def KCIQuery (tr: ExecTrace): Prop := ∀ b a ikB ikA spk pqpk opk ek ct keys i, tr.EventLoggedAt (PQXDHEvent.BobDone b a ikB ikA spk pqpk opk ek ct keys) i → tr.EventLogged (PQXDHEvent.CompromisedIK b ikB) → ¬ HandshakeAuthWasCompromised b a ikA spk i tr → ResponderSessionAgreement a spk pqpk opk i tr

def PeerAuthenticationQueryL204–209 ↗#

Peer authentication (Theorem 1).

def PeerAuthenticationQuery (tr : ExecTrace) : Prop := ∀ b a ikB ikA spk pqpk opk ek ct keys i, tr.EventLoggedAt (PQXDHEvent.BobDone b a ikB ikA spk pqpk opk ek ct keys) i → ¬ HandshakeAuthWasCompromised b a ikA spk i tr → ResponderSessionAgreement a spk pqpk opk i tr

def SIPremiseL211–220 ↗#

Premise for session independence: identity keys, DH, and the KEM are uncompromised, and only prekeys distinct from (spk, pqpk, opk) are compromised.

def SIPremise (a b: Participant) (ikA ikB spk pqpk: Bytes) (opk: Option Bytes) (tr: ExecTrace): Prop := ¬ tr.EventLogged (PQXDHEvent.CompromisedIK a ikA) ∧ ¬ tr.EventLogged (PQXDHEvent.CompromisedIK b ikB) ∧ ¬ tr.EventLogged PQXDHEvent.BrokenDH ∧ ¬ tr.EventLogged PQXDHEvent.BrokenKEM ∧ (∀ s, tr.EventLogged (PQXDHEvent.CompromisedSPK b s) → s ≠ spk) ∧ (∀ q, tr.EventLogged (PQXDHEvent.CompromisedPQSPK b q) → q ≠ pqpk) ∧ (∀ o, tr.EventLogged (PQXDHEvent.CompromisedOPK b o) → ¬ SameOPK (some o) opk)

def SessionIndependenceQueryL222–227 ↗#

Session independence against compromise of other sessions' prekeys (Theorem 1).

def SessionIndependenceQuery (tr : ExecTrace) (Knows : Bytes → Prop) : Prop := ∀ a b ikA ikB spk pqpk opk keys i, HandshakeCompletedAt tr a b ikA ikB spk pqpk opk keys i → SIPremise a b ikA ikB spk pqpk opk tr → HandshakeBlocksSecret tr Knows keys
end
end DY.Libsignal.PQXDH
namespace DY.Libsignal.TripleRatchet.Cheval
section
open scoped Composed

def StateStoredAtL242–244 ↗#

def StateStoredAt (me : Participant) (st : TRState) (stateIdx : Nat) (tr : ExecTrace) : Prop := tr.at? stateIdx = some (PersistentGlobalState.State.ExecEntryT.mk ({ participant := me, state := st } : PersistentLocalState.LocalState TRState))

def TRKeyKnownL246–249 ↗#

Knows holds for either the Double Ratchet seed or the derived hybrid cipher key (trMsgKeys pqSalt seed).cipherKey.

def TRKeyKnown (Knows : Bytes → Prop) (seed pqSalt : Bytes) : Prop := Knows seed ∨ Knows (trMsgKeys pqSalt seed).cipherKey

def HandshakeRootCompromisedL251–255 ↗#

k is an initial rk or ck of some PQXDH handshake on tr, and every PQXDH handshake on tr producing k as rk or ck satisfies HandshakeWasCompromisedAt.

def HandshakeRootCompromised (tr : ExecTrace) (k : Bytes) : Prop := (∃ keys j, HandshakeKeysAt tr j keys ∧ (k = keys.rk ∨ k = keys.ck)) ∧ (∀ keys j, HandshakeKeysAt tr j keys → (k = keys.rk ∨ k = keys.ck) → HandshakeWasCompromisedAt tr j)

def HonestDHKeyL257–260 ↗#

d is an honest DH ratchet secret key on tr (HonestDH or st.dhs of a stored snapshot).

def HonestDHKey (tr : ExecTrace) (d : Bytes) : Prop := (∃ s i, tr.EventLogged (TREvent.HonestDH s d i)) ∨ (∃ me st idx, StateStoredAt me st idx tr ∧ st.dhs = d)

def CompromisedKeyL262–272 ↗#

Ratchet secret k was compromised on tr: directly exposed (ExposedRK, ExposedDHs, ExposedCKs, ExposedCKr, ExposedMK), derived from HandshakeRootCompromised, or an HonestDHKey under BrokenDH (ExposedSpqr excuses no ratchet secret).

def CompromisedKey (tr : ExecTrace) (k : Bytes) : Prop := (∃ s i, tr.EventLogged (TREvent.ExposedRK s k i)) ∨ (∃ s i, tr.EventLogged (TREvent.ExposedDHs s k i)) ∨ (∃ s ns i, tr.EventLogged (TREvent.ExposedCKs s k ns i)) ∨ (∃ s nr i, tr.EventLogged (TREvent.ExposedCKr s k nr i)) ∨ (∃ s n i, tr.EventLogged (TREvent.ExposedMK s k n i)) ∨ HandshakeRootCompromised tr k ∨ (HonestDHKey tr k ∧ tr.EventLogged PQXDHEvent.BrokenDH)

def MessageSeedUsedL274–276 ↗#

def MessageSeedUsed (tr : ExecTrace) (seed pqSalt : Bytes) : Prop := ∃ s dir n i parentStateIdx, tr.EventLogged (TREvent.MessageKey s dir seed pqSalt n i parentStateIdx)

def FSQueryL278–287 ↗#

Ratchet forward secrecy (Cheval et al., Table 2): if TRKeyKnown Knows seed pqSalt holds for a used seed, then seed, an ancestor chain key (DerivesMsgKey), or an ancestor root key (DerivesChain) satisfies CompromisedKey.

def FSQuery (tr : ExecTrace) (Knows : Bytes → Prop := fun t => t.AttackerKnows tr) : Prop := ∀ seed pqSalt, MessageSeedUsed tr seed pqSalt → TRKeyKnown Knows seed pqSalt → CompromisedKey tr seed ∨ (∃ ck, DerivesMsgKey ck seed ∧ CompromisedKey tr ck) ∨ (∃ rk ck, DerivesChain rk ck ∧ DerivesMsgKey ck seed ∧ CompromisedKey tr rk)

def PCSQueryL289–305 ↗#

Ratchet post-compromise security (Cheval et al., Table 2): if seed descends from a healing DH step createChain rk_prev (dhPk peerSk) ownSk between honest DH secrets ownSk and peerSk and TRKeyKnown Knows seed pqSalt holds, then seed, a post-heal chain or root key, or both a pre-heal root key and one of (ownSk, peerSk) satisfies CompromisedKey.

def PCSQuery (tr : ExecTrace) (Knows : Bytes → Prop := fun t => t.AttackerKnows tr) : Prop := ∀ seed pqSalt rk_prev ownSk peerSk, MessageSeedUsed tr seed pqSalt → TRKeyKnown Knows seed pqSalt → HonestDHKey tr ownSk → HonestDHKey tr peerSk → let (rk_heal, ck_heal) := createChain rk_prev (DiffieHellman.dhPk peerSk) ownSk (DerivesMsgKey ck_heal seed ∨ ∃ ck, DerivesChain rk_heal ck ∧ DerivesMsgKey ck seed) → CompromisedKey tr seed ∨ (∃ ck, DerivesMsgKey ck seed ∧ CompromisedKey tr ck) ∨ (∃ rk ck, RootDescends rk_heal rk ∧ DerivesChain rk ck ∧ DerivesMsgKey ck seed ∧ CompromisedKey tr rk) ∨ ((∃ rk, RootDescends rk rk_prev ∧ CompromisedKey tr rk) ∧ (CompromisedKey tr ownSk ∨ CompromisedKey tr peerSk))
end
end DY.Libsignal.TripleRatchet.Cheval
namespace DY.Libsignal.Composed.Security
open scoped Composed
open TripleRatchet.Cheval (FSQuery PCSQuery)
section

def AllSecurityQueriesHoldL323–334 ↗#

Conjunction of all ten whole-trace security queries on tr against Knows.

def AllSecurityQueriesHold (tr : ExecTrace) (Knows : Bytes → Prop) : Prop := FSQuery tr Knows ∧ PCSQuery tr Knows ∧ AliceInitiatorSecrecyQuery tr Knows ∧ BobResponderSecrecyQuery tr Knows ∧ AuthenticationQuery tr ∧ PeerAuthenticationQuery tr ∧ ForwardSecrecyQuery tr Knows ∧ KCIQuery tr ∧ SessionIndependenceQuery tr Knows ∧ HNDLQuery tr Knows
end
end DY.Libsignal.Composed.Security
end
namespace DY.Libsignal.Composed.Security
open DY.Libsignal.Composed
open TripleRatchet (TREvent)
open TripleRatchet.Cheval
section

def ForwardSecrecyL353–354 ↗#

def ForwardSecrecy : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → FSQuery tr

def PostCompromiseSecurityL356–357 ↗#

def PostCompromiseSecurity : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → PCSQuery tr

def AliceInitiatorSecrecyL359–361 ↗#

def AliceInitiatorSecrecy : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → AliceInitiatorSecrecyQuery tr (fun t => t.AttackerKnows tr)

def BobResponderSecrecyL363–365 ↗#

def BobResponderSecrecy : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → BobResponderSecrecyQuery tr (fun t => t.AttackerKnows tr)

def AuthenticationL367–368 ↗#

def Authentication : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → AuthenticationQuery tr

def PeerAuthenticationL370–371 ↗#

def PeerAuthentication : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → PeerAuthenticationQuery tr

def HandshakeForwardSecrecyL373–375 ↗#

def HandshakeForwardSecrecy : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → ForwardSecrecyQuery tr (fun t => t.AttackerKnows tr)

def KCIResistanceL377–378 ↗#

def KCIResistance : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → KCIQuery tr

def SessionIndependenceL380–382 ↗#

def SessionIndependence : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → SessionIndependenceQuery tr (fun t => t.AttackerKnows tr)

def HNDLResistanceL384–386 ↗#

def HNDLResistance : Prop := ∀ tr : ExecTrace, tr.Reachable reachability → HNDLQuery tr (fun t => t.AttackerKnows tr)

def AllModelSecurityQueriesHoldL388–404 ↗#

Conjunction of all ten security properties over reachable traces of Composed.reachability.

end
end DY.Libsignal.Composed.Security