# Tamarin Models

Symbolic formal verification of the Soliton cryptographic protocol using
[Tamarin Prover](https://tamarin-prover.com/). 8 models, 55 lemmas.

These models were authored by the protocol designers and have not undergone
independent peer review. They are published for transparency and to facilitate
third-party verification. All results are machine-checkable and reproducible.

## Requirements

- tamarin-prover 1.12.0+
- maude 3.5.1+

## Usage

```bash
# All models
../verify.sh tamarin

# Single model
tamarin-prover LO_Auth.spthy --prove
```

## Resource Usage

All 8 models complete in under 90 seconds total with under 2 GB peak RAM.
No special hardware or overnight runs required — a laptop is sufficient.

This is achieved through bounded unrolling (3–4 steps for ratchet and chain
models) and unique fact names per state (eliminating branching during source
analysis).

## Results

Verified with Tamarin 1.12.0, Maude 3.5.1.

### LO_Auth.spthy — Theorem 6 (Key Possession)

| Lemma | Result | Steps |
|-------|--------|-------|
| Auth_Exists | verified | 5 |
| Auth_Ordering | verified | 2 |
| Auth_Single_Use | verified | 8 |
| Auth_No_Accept_After_Timeout | verified | 3 |
| Auth_Unique_Challenge | verified | 2 |
| Theorem6_Key_Possession | verified | 11 |
| Theorem6_No_Oracle | verified | 11 |

### LO_KEX.spthy — Theorems 1, 2a, 2b (Session Key Secrecy, Authentication)

OPK-present case only. See header comment for OPK-absent scope note.

| Lemma | Result | Steps |
|-------|--------|-------|
| KEX_Exists | verified | 27 |
| Theorem1_Session_Key_Secrecy_A | verified | 70 |
| Theorem1_Session_Key_Secrecy_B | verified | 136 |
| Theorem1_EK_Secrecy_A | verified | 70 |
| Theorem1_EK_Secrecy_B | verified | 136 |
| Theorem2a_Recipient_Binding | verified | 2 |
| Theorem2b_Initiator_Authentication | verified | 10 |
| OPK_Single_Use | verified | 24 |
| Key_Uniqueness | verified | 2 |

### LO_Ratchet.spthy — Theorems 4, 5 (Forward Secrecy, PCS — structural)

Abstract model using Fr() epoch keys. Proves FS and PCS are structural
properties of the state machine, independent of KDF/KEM security.

| Lemma | Result | Steps | Notes |
|-------|--------|-------|-------|
| send_sanity | verified | 7 | |
| send_fs | verified | 2818 | Theorem 4a |
| send_corrupt_terminates | verified | 193 | |
| send_pcs | verified | 2 | Abstract model only |
| recv_sanity | verified | 6 | |
| recv_fs_1step | **falsified** | 11 | Expected — prev_ek_r retains old key |
| recv_fs_2step | verified | 9132 | Theorem 4b |
| recv_corrupt_terminates | verified | 273 | |
| recv_pcs | verified | 107 | Abstract model only (see comment) |

### LO_Ratchet_PCS.spthy — Theorem 5 (PCS — KEM-level)

KEM-level model proving the 1-step non-recovery / 1-direction-change recovery
that the abstract Fr() model cannot distinguish.

| Lemma | Result | Steps | Notes |
|-------|--------|-------|-------|
| pcs_sanity | verified | 3 | |
| pcs_no_recovery_after_recv | **falsified** | 9 | Expected — adversary holds sk_own |
| pcs_recovery_after_send | verified | 7 | |
| pcs_recovery_sustained | verified | 15 | |
| pcs_f4_violated | verified | 7 | F4 defeats next recv, not this send |

### LO_Call.spthy — Theorems 8–11 (Call Key Security)

| Lemma | Result | Steps |
|-------|--------|-------|
| Call_Exists | verified | 6 |
| Call_Key_Agreement | verified | 56 |
| Theorem8_Call_Key_Secrecy | verified | 24 |
| Theorem9_Intra_Call_FS | verified | 193 |
| Theorem10_Call_Ratchet_Ind | verified | 3 |
| Theorem11_Concurrent_Ind | verified | 52 |

### LO_AntiReflection.spthy — Theorem 12 (Anti-Reflection)

| Lemma | Result | Steps |
|-------|--------|-------|
| Reflection_Sanity | verified | 8 |
| Theorem12_Anti_Reflection | verified | 5 |

### LO_Stream.spthy — Theorem 13, Properties 2–5 (Streaming AEAD)

| Lemma | Result | Steps |
|-------|--------|-------|
| Stream_Sanity | verified | 11 |
| Stream_Sanity_Finalize | verified | 7 |
| Theorem13_P2_Integrity | verified | 28 |
| Theorem13_P3_Ordering | verified | 18 |
| Theorem13_P4_No_False_Final | verified | 17 |
| Theorem13_P5_Cross_Stream | verified | 55 |
| Theorem13_Key_Secrecy | verified | 3 |

### LO_NegativeTests.spthy — Expected Falsifications

Each lemma confirms a known attack path works in the model. All should be
falsified (or verified for exists-trace). If any result flips, the model has
a bug.

| Lemma | Result | Steps | Attack path |
|-------|--------|-------|-------------|
| neg_auth_ik_corrupt | falsified | 8 | IK corruption forges auth |
| neg_auth_rng_corrupt | falsified | 10 | RNG corruption forges auth |
| neg_ratchet_no_fs_0step | falsified | 8 | Corrupt immediately reveals ek |
| neg_ratchet_recv_1step | falsified | 10 | 1-step recv, prev retains ek |
| neg_call_rk_plus_rng | falsified | 9 | rk + RNG derives call key |
| neg_stream_key_corrupt | falsified | 5 | Key corruption enables forgery |
| neg_reflect_self_session | falsified | 7 | Self-session enables reflection |
| neg_kex_no_opk | falsified | 11 | IK+SPK alone breaks OPK-absent |
| neg_ratchet_duplicate | falsified | 7 | No recv_seen → duplicate accepted |
| neg_call_self_session | verified | 3 | Self-call reachable without guard |

## Scope and Limitations

- **OPK-absent KEX**: LO_KEX.spthy models the 3-key (OPK-present) case only.
  The 2-key OPK-absent case has a weaker secrecy threshold (IK+SPK), validated
  by neg_kex_no_opk in the negative tests.
- **X-Wing as black box**: All models treat X-Wing as a single IND-CCA2 KEM
  without opening the combiner (draft-09 hybrid argument).
- **Abstract ratchet**: LO_Ratchet.spthy uses Fr() epoch keys (not KDF-derived).
  KEM-level properties are in LO_Ratchet_PCS.spthy.
- **No Theorem 7**: Domain separation is vacuously true in Tamarin (string
  constants are structurally distinct).
- **No Theorem 3/13-P1**: Message confidentiality (IND-CPA) is computational,
  covered by the CryptoVerif models.
- **Bounded chains**: Ratchet and call chain steps are bounded (3–4 steps)
  to prevent Tamarin non-termination.

## Theorem Coverage

| Theorem | Model | Type |
|---------|-------|------|
| 1 (KEX Key Secrecy) | LO_KEX | Symbolic secrecy |
| 2a (Recipient Auth) | LO_KEX | Structural binding |
| 2b (Initiator Auth) | LO_KEX | Correspondence |
| 4 (Forward Secrecy) | LO_Ratchet | Structural FS |
| 5 (PCS) | LO_Ratchet + LO_Ratchet_PCS | Structural + KEM-level |
| 6 (Auth Key Possession) | LO_Auth | Correspondence |
| 8 (Call Key Secrecy) | LO_Call | Symbolic secrecy |
| 9 (Intra-Call FS) | LO_Call | Chain one-wayness |
| 10 (Call/Ratchet Ind.) | LO_Call | Independence |
| 11 (Concurrent Calls) | LO_Call | Independence |
| 12 (Anti-Reflection) | LO_AntiReflection | AAD direction binding |
| 13 P2–P5 | LO_Stream | Integrity, ordering, truncation, isolation |