Computer Laboratory

Technical reports

Mechanized proofs for a recursive authentication protocol

Lawrence C. Paulson

March 1997, 30 pages


A novel protocol has been formally analyzed using the prover Isabelle/HOL, following the inductive approach described in earlier work. There is no limit on the length of a run, the nesting of messages or the number of agents involved. A single run of the protocol delivers session keys for all the agents, allowing neighbours to perform mutual authentication. The basic security theorem states that session keys are correctly delivered to adjacent pairs of honest agents, regardless of whether other agents in the chain are compromised. The protocol’s complexity caused some difficulties in the specification and proofs, but its symmetry reduced the number of theorems to prove.

Full text

PDF (0.2 MB)
PS (0.1 MB)

BibTeX record

  author =	 {Paulson, Lawrence C.},
  title = 	 {{Mechanized proofs for a recursive authentication protocol}},
  year = 	 1997,
  month = 	 mar,
  url = 	 {},
  institution =  {University of Cambridge, Computer Laboratory},
  number = 	 {UCAM-CL-TR-418}