PQXDH in Lean

7.2. Adversary models🔗

The Dolev-Yao adversary model (symbolic/ProVerif). The adversary controls the network (active MitM) but cryptographic primitives are ideal black boxes. Security properties are expressed as correspondence assertions. Used in Theorem 1 (section 3.1).

Code for Definition7.31 definition
  • inductive DolevYao : TypeA type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. 
    inductive DolevYao : TypeA type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. 
    §3.1, p. 473 and §3.4, p. 474: The Dolev-Yao adversary model (symbolic/ProVerif).
    
    A marker type indicating the analysis is carried out in the symbolic
    model, where:
      - The adversary controls the network (active MitM): it can
        intercept, inject, replay, and modify all messages.
      - Cryptographic primitives are ideal black boxes — the
        adversary cannot break encryption, forge signatures, or invert
        hashes except by using the appropriate key.
      - The adversary may compromise long-term keys at any time
        (adaptive corruption).
    
    Security properties are expressed as correspondence assertions:
      "if event A occurred (e.g. Bob completed a session with Alice),
       then event B must have occurred (e.g. Alice initiated it)."
    
    In the post-quantum extension, the adversary is additionally given
    the power to break DH (compute discrete logs) at some point in
    time, modeling a future quantum computer. Security of sessions
    completed *before* this point is then analyzed.
    
    Since all primitives are ideal, no computational hardness
    assumptions appear as hypotheses in the symbolic model.
    Theorem 1 depends only on the protocol logic. 

    Constructors

    mk : DolevYaoDolevYao : Type§3.1, p. 473 and §3.4, p. 474: The Dolev-Yao adversary model (symbolic/ProVerif).
    
    A marker type indicating the analysis is carried out in the symbolic
    model, where:
      - The adversary controls the network (active MitM): it can
        intercept, inject, replay, and modify all messages.
      - Cryptographic primitives are ideal black boxes — the
        adversary cannot break encryption, forge signatures, or invert
        hashes except by using the appropriate key.
      - The adversary may compromise long-term keys at any time
        (adaptive corruption).
    
    Security properties are expressed as correspondence assertions:
      "if event A occurred (e.g. Bob completed a session with Alice),
       then event B must have occurred (e.g. Alice initiated it)."
    
    In the post-quantum extension, the adversary is additionally given
    the power to break DH (compute discrete logs) at some point in
    time, modeling a future quantum computer. Security of sessions
    completed *before* this point is then analyzed.
    
    Since all primitives are ideal, no computational hardness
    assumptions appear as hypotheses in the symbolic model.
    Theorem 1 depends only on the protocol logic. 
    complete

Oracle queries available to the adversary in the computational AKE security game: NewSession, Send, Corrupt, RevealSessionKey, and Test. Models the interface between adversary and challenger in CryptoVerif (section 3.2).

Code for Definition7.41 definition
  • inductive AKE_Query : TypeA type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. 
    inductive AKE_Query : TypeA type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. 
    §3.2, p. 473 and §3.5, p. 475: Oracle queries available to the adversary
    in the computational authenticated key exchange (AKE) security game.
    This models the interface between the adversary and the challenger in CryptoVerif. 

    Constructors

    NewSession : AKE_QueryAKE_Query : Type§3.2, p. 473 and §3.5, p. 475: Oracle queries available to the adversary
    in the computational authenticated key exchange (AKE) security game.
    This models the interface between the adversary and the challenger in CryptoVerif. 
    Initiate a new protocol session between two identified parties.
    Returns a session handle. 
    Send : AKE_QueryAKE_Query : Type§3.2, p. 473 and §3.5, p. 475: Oracle queries available to the adversary
    in the computational authenticated key exchange (AKE) security game.
    This models the interface between the adversary and the challenger in CryptoVerif. 
    Deliver a (possibly modified) message to a session, advancing
    the protocol state. Models an active network attacker. 
    Corrupt : AKE_QueryAKE_Query : Type§3.2, p. 473 and §3.5, p. 475: Oracle queries available to the adversary
    in the computational authenticated key exchange (AKE) security game.
    This models the interface between the adversary and the challenger in CryptoVerif. 
    Obtain the long-term secret key of a named party.
    Models key compromise / corruption. 
    RevealSessionKey : AKE_QueryAKE_Query : Type§3.2, p. 473 and §3.5, p. 475: Oracle queries available to the adversary
    in the computational authenticated key exchange (AKE) security game.
    This models the interface between the adversary and the challenger in CryptoVerif. 
    Obtain the session key of a completed session.
    Models compromise of session-specific secrets. 
    Test : AKE_QueryAKE_Query : Type§3.2, p. 473 and §3.5, p. 475: Oracle queries available to the adversary
    in the computational authenticated key exchange (AKE) security game.
    This models the interface between the adversary and the challenger in CryptoVerif. 
    Challenge query: receive either the real session key or a
    uniformly random key (determined by a hidden coin flip).
    The adversary must guess which. 
    complete
Definition7.5

Freshness condition for the AKE security game. A test session is fresh if the adversary has not trivially obtained the answer — e.g., has not revealed the test/partner session key or corrupted both long-term keys before session completion (section 3.3).

Code for Definition7.51 definition
  • structure Freshness : TypeA type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. 
    structure Freshness : TypeA type universe. `Type ≡ Type 0`, `Type u ≡ Sort (u + 1)`. 
    §3.3, p. 473–474: Freshness condition for the AKE security game.
    
    A test session is *fresh* if the adversary has not trivially obtained
    the answer. Specifically, a session between Alice (initiator) and
    Bob (responder) is fresh if:
    
      1. The adversary did not `RevealSessionKey` on the test session
         or its matching partner session.
      2. The adversary did not `Corrupt` *both* Alice's and Bob's
         long-term identity keys before the test session completed.
      3. (For forward secrecy) The adversary did not `Corrupt` the
         ephemeral key of the test session.
    
    The exact freshness condition varies by theorem; the paper defines
    it within each CryptoVerif game. 

    Constructor

    Freshness.mk
      (no_reveal_testProp no_reveal_partnerProp
        no_dual_corruption_before_completionProp :
        PropThe universe of propositions. `Prop ≡ Sort 0`.
    
    Every proposition is propositionally equal to either `True` or `False`. ) :
      FreshnessFreshness : Type§3.3, p. 473–474: Freshness condition for the AKE security game.
    
    A test session is *fresh* if the adversary has not trivially obtained
    the answer. Specifically, a session between Alice (initiator) and
    Bob (responder) is fresh if:
    
      1. The adversary did not `RevealSessionKey` on the test session
         or its matching partner session.
      2. The adversary did not `Corrupt` *both* Alice's and Bob's
         long-term identity keys before the test session completed.
      3. (For forward secrecy) The adversary did not `Corrupt` the
         ephemeral key of the test session.
    
    The exact freshness condition varies by theorem; the paper defines
    it within each CryptoVerif game. 

    Fields

    no_reveal_testPropTest session key was not revealed.  : PropThe universe of propositions. `Prop ≡ Sort 0`.
    
    Every proposition is propositionally equal to either `True` or `False`. 
    Test session key was not revealed. 
    no_reveal_partnerPropPartner session key was not revealed.  : PropThe universe of propositions. `Prop ≡ Sort 0`.
    
    Every proposition is propositionally equal to either `True` or `False`. 
    Partner session key was not revealed. 
    no_dual_corruption_before_completionPropNot both long-term keys corrupted before session completion.  : PropThe universe of propositions. `Prop ≡ Sort 0`.
    
    Every proposition is propositionally equal to either `True` or `False`. 
    Not both long-term keys corrupted before session completion. 
    complete