src/HOL/Auth/Yahalom.thy
author paulson
Thu Sep 23 13:06:31 1999 +0200 (1999-09-23)
changeset 7584 5be4bb8e4e3f
parent 6335 7e4bffaa2a3e
child 11185 1b737b4c2108
permissions -rw-r--r--
tidied; added lemma restrict_to_left
     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   :: event list set
    16 inductive "yahalom"
    17   intrs 
    18          (*Initial trace is empty*)
    19     Nil  "[]: yahalom"
    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;  X: synth (analz (knows Spy evs)) |]
    25           ==> Says Spy B X  # evs : yahalom"
    26 
    27          (*A message that has been sent can be received by the
    28            intended recipient.*)
    29     Reception "[| evsr: yahalom;  Says A B X : set evsr |]
    30                ==> Gets B X # evsr : yahalom"
    31 
    32          (*Alice initiates a protocol run*)
    33     YM1  "[| evs1: yahalom;  Nonce NA ~: used evs1 |]
    34           ==> Says A B {|Agent A, Nonce NA|} # evs1 : yahalom"
    35 
    36          (*Bob's response to Alice's message.*)
    37     YM2  "[| evs2: yahalom;  Nonce NB ~: used evs2;
    38              Gets B {|Agent A, Nonce NA|} : set evs2 |]
    39           ==> Says B Server 
    40                   {|Agent B, Crypt (shrK B) {|Agent A, Nonce NA, Nonce NB|}|}
    41                 # evs2 : yahalom"
    42 
    43          (*The Server receives Bob's message.  He responds by sending a
    44             new session key to Alice, with a packet for forwarding to Bob.*)
    45     YM3  "[| evs3: yahalom;  Key KAB ~: used evs3;
    46              Gets Server 
    47                   {|Agent B, Crypt (shrK B) {|Agent A, Nonce NA, Nonce NB|}|}
    48                : set evs3 |]
    49           ==> Says Server A
    50                    {|Crypt (shrK A) {|Agent B, Key KAB, Nonce NA, Nonce NB|},
    51                      Crypt (shrK B) {|Agent A, Key KAB|}|}
    52                 # evs3 : yahalom"
    53 
    54          (*Alice receives the Server's (?) message, checks her Nonce, and
    55            uses the new session key to send Bob his Nonce.  The premise
    56            A ~= Server is needed to prove Says_Server_not_range.*)
    57     YM4  "[| evs4: yahalom;  A ~= Server;
    58              Gets A {|Crypt(shrK A) {|Agent B, Key K, Nonce NA, Nonce NB|}, X|}
    59                 : set evs4;
    60              Says A B {|Agent A, Nonce NA|} : set evs4 |]
    61           ==> Says A B {|X, Crypt K (Nonce NB)|} # evs4 : yahalom"
    62 
    63          (*This message models possible leaks of session keys.  The Nonces
    64            identify the protocol run.  Quoting Server here ensures they are
    65            correct.*)
    66     Oops "[| evso: yahalom;  
    67              Says Server A {|Crypt (shrK A)
    68                                    {|Agent B, Key K, Nonce NA, Nonce NB|},
    69                              X|}  : set evso |]
    70           ==> Notes Spy {|Nonce NA, Nonce NB, Key K|} # evso : yahalom"
    71 
    72 
    73 constdefs 
    74   KeyWithNonce :: [key, nat, event list] => bool
    75   "KeyWithNonce K NB evs ==
    76      EX A B na X. 
    77        Says Server A {|Crypt (shrK A) {|Agent B, Key K, na, Nonce NB|}, X|} 
    78          : set evs"
    79 
    80 end