src/HOL/Auth/Yahalom.thy
author paulson
Tue Jul 01 17:38:49 1997 +0200 (1997-07-01)
changeset 3481 256f38c01b98
parent 3465 e85c24717cad
child 3519 ab0a9fbed4c0
permissions -rw-r--r--
Deleted a redundant A~=B in rules that refer to a previous event
     1 (*  Title:      HOL/Auth/Yahalom
     2     ID:         $Id$
     3     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     4     Copyright   1996  University of Cambridge
     5 
     6 Inductive relation "yahalom" for the Yahalom protocol.
     7 
     8 From page 257 of
     9   Burrows, Abadi and Needham.  A Logic of Authentication.
    10   Proc. Royal Soc. 426 (1989)
    11 *)
    12 
    13 Yahalom = Shared + 
    14 
    15 consts  yahalom   :: agent set => event list set
    16 inductive "yahalom lost"
    17   intrs 
    18          (*Initial trace is empty*)
    19     Nil  "[]: yahalom lost"
    20 
    21          (*The spy MAY say anything he CAN say.  We do not expect him to
    22            invent new nonces here, but he can also use NS1.  Common to
    23            all similar protocols.*)
    24     Fake "[| evs: yahalom lost;  B ~= Spy;  
    25              X: synth (analz (sees lost Spy evs)) |]
    26           ==> Says Spy B X  # evs : yahalom lost"
    27 
    28          (*Alice initiates a protocol run*)
    29     YM1  "[| evs: yahalom lost;  A ~= B;  Nonce NA ~: used evs |]
    30           ==> Says A B {|Agent A, Nonce NA|} # evs : yahalom lost"
    31 
    32          (*Bob's response to Alice's message.  Bob doesn't know who 
    33 	   the sender is, hence the A' in the sender field.*)
    34     YM2  "[| evs: yahalom lost;  B ~= Server;  Nonce NB ~: used evs;
    35              Says A' B {|Agent A, Nonce NA|} : set evs |]
    36           ==> Says B Server 
    37                   {|Agent B, Crypt (shrK B) {|Agent A, Nonce NA, Nonce NB|}|}
    38                 # evs : yahalom lost"
    39 
    40          (*The Server receives Bob's message.  He responds by sending a
    41             new session key to Alice, with a packet for forwarding to Bob.*)
    42     YM3  "[| evs: yahalom lost;  A ~= Server;  Key KAB ~: used evs;
    43              Says B' Server 
    44                   {|Agent B, Crypt (shrK B) {|Agent A, Nonce NA, Nonce NB|}|}
    45                : set evs |]
    46           ==> Says Server A
    47                    {|Crypt (shrK A) {|Agent B, Key KAB, Nonce NA, Nonce NB|},
    48                      Crypt (shrK B) {|Agent A, Key KAB|}|}
    49                 # evs : yahalom lost"
    50 
    51          (*Alice receives the Server's (?) message, checks her Nonce, and
    52            uses the new session key to send Bob his Nonce.*)
    53     YM4  "[| evs: yahalom lost;  A ~= Server;  
    54              Says S A {|Crypt (shrK A) {|Agent B, Key K, Nonce NA, Nonce NB|},
    55                         X|}  : set evs;
    56              Says A B {|Agent A, Nonce NA|} : set evs |]
    57           ==> Says A B {|X, Crypt K (Nonce NB)|} # evs : yahalom lost"
    58 
    59          (*This message models possible leaks of session keys.  The Nonces
    60            identify the protocol run.  Quoting Server here ensures they are
    61            correct.*)
    62     Oops "[| evs: yahalom lost;  A ~= Spy;
    63              Says Server A {|Crypt (shrK A)
    64                                    {|Agent B, Key K, Nonce NA, Nonce NB|},
    65                              X|}  : set evs |]
    66           ==> Says A Spy {|Nonce NA, Nonce NB, Key K|} # evs : yahalom lost"
    67 
    68 
    69 constdefs 
    70   KeyWithNonce :: [key, nat, event list] => bool
    71   "KeyWithNonce K NB evs ==
    72      EX A B na X. 
    73        Says Server A {|Crypt (shrK A) {|Agent B, Key K, na, Nonce NB|}, X|} 
    74          : set evs"
    75 
    76 end