src/HOL/Auth/WooLam.ML
author paulson
Fri Sep 19 18:27:31 1997 +0200 (1997-09-19)
changeset 3686 4b484805b4c4
parent 3683 aafe719dff14
child 3730 6933d20f335f
permissions -rw-r--r--
First working version with Oops event for session keys
paulson@2274
     1
(*  Title:      HOL/Auth/WooLam
paulson@2274
     2
    ID:         $Id$
paulson@2274
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
paulson@2274
     4
    Copyright   1996  University of Cambridge
paulson@2274
     5
paulson@2274
     6
Inductive relation "woolam" for the Woo-Lam protocol.
paulson@2274
     7
paulson@2274
     8
Simplified version from page 11 of
paulson@2274
     9
  Abadi and Needham.  Prudent Engineering Practice for Cryptographic Protocols.
paulson@2274
    10
  IEEE Trans. S.E. 22(1), 1996, pages 6-15.
paulson@2274
    11
*)
paulson@2274
    12
paulson@2274
    13
open WooLam;
paulson@2274
    14
paulson@2274
    15
proof_timing:=true;
paulson@2274
    16
HOL_quantifiers := false;
paulson@2274
    17
paulson@2274
    18
paulson@2321
    19
(*A "possibility property": there are traces that reach the end*)
paulson@2274
    20
goal thy 
paulson@2274
    21
 "!!A B. [| A ~= B; A ~= Server; B ~= Server |]   \
paulson@2283
    22
\        ==> EX NB. EX evs: woolam.               \
paulson@3466
    23
\              Says Server B (Crypt (shrK B) {|Agent A, Nonce NB|}) : set evs";
paulson@2274
    24
by (REPEAT (resolve_tac [exI,bexI] 1));
paulson@2274
    25
by (rtac (woolam.Nil RS woolam.WL1 RS woolam.WL2 RS woolam.WL3 RS 
paulson@2516
    26
          woolam.WL4 RS woolam.WL5) 2);
paulson@3471
    27
by possibility_tac;
paulson@2274
    28
result();
paulson@2274
    29
paulson@2274
    30
paulson@2274
    31
(**** Inductive proofs about woolam ****)
paulson@2274
    32
paulson@2274
    33
(*Nobody sends themselves messages*)
nipkow@3465
    34
goal thy "!!evs. evs : woolam ==> ALL A X. Says A A X ~: set evs";
paulson@2274
    35
by (etac woolam.induct 1);
paulson@2274
    36
by (Auto_tac());
paulson@2274
    37
qed_spec_mp "not_Says_to_self";
paulson@2274
    38
Addsimps [not_Says_to_self];
paulson@2274
    39
AddSEs   [not_Says_to_self RSN (2, rev_notE)];
paulson@2274
    40
paulson@2274
    41
paulson@2274
    42
(** For reasoning about the encrypted portion of messages **)
paulson@2274
    43
paulson@3683
    44
goal thy "!!evs. Says A' B X : set evs ==> X : analz (spies evs)";
paulson@3683
    45
by (etac (Says_imp_spies RS analz.Inj) 1);
paulson@3683
    46
qed "WL4_analz_spies";
paulson@2274
    47
paulson@3683
    48
bind_thm ("WL4_parts_spies",
paulson@3683
    49
          WL4_analz_spies RS (impOfSubs analz_subset_parts));
paulson@2274
    50
paulson@3683
    51
(*For proving the easier theorems about X ~: parts (spies evs) *)
paulson@3519
    52
fun parts_induct_tac i = 
paulson@3519
    53
    etac woolam.induct i  THEN 
paulson@3683
    54
    forward_tac [WL4_parts_spies] (i+5)  THEN
paulson@3471
    55
    prove_simple_subgoals_tac 1;
paulson@2274
    56
paulson@2274
    57
paulson@3683
    58
(** Theorems of the form X ~: parts (spies evs) imply that NOBODY
paulson@2274
    59
    sends messages containing X! **)
paulson@2274
    60
paulson@3683
    61
(*Spy never sees another agent's shared key! (unless it's bad at start)*)
paulson@2274
    62
goal thy 
paulson@3683
    63
 "!!evs. evs : woolam ==> (Key (shrK A) : parts (spies evs)) = (A : bad)";
paulson@3519
    64
by (parts_induct_tac 1);
paulson@3121
    65
by (Fake_parts_insert_tac 1);
paulson@2274
    66
qed "Spy_see_shrK";
paulson@2274
    67
Addsimps [Spy_see_shrK];
paulson@2274
    68
paulson@2274
    69
goal thy 
paulson@3683
    70
 "!!evs. evs : woolam ==> (Key (shrK A) : analz (spies evs)) = (A : bad)";
paulson@2274
    71
by (auto_tac(!claset addDs [impOfSubs analz_subset_parts], !simpset));
paulson@2274
    72
qed "Spy_analz_shrK";
paulson@2274
    73
Addsimps [Spy_analz_shrK];
paulson@2274
    74
paulson@3683
    75
goal thy  "!!A. [| Key (shrK A) : parts (spies evs);       \
paulson@3683
    76
\                  evs : woolam |] ==> A:bad";
paulson@3121
    77
by (blast_tac (!claset addDs [Spy_see_shrK]) 1);
paulson@2274
    78
qed "Spy_see_shrK_D";
paulson@2274
    79
paulson@2274
    80
bind_thm ("Spy_analz_shrK_D", analz_subset_parts RS subsetD RS Spy_see_shrK_D);
paulson@2274
    81
AddSDs [Spy_see_shrK_D, Spy_analz_shrK_D];
paulson@2274
    82
paulson@2274
    83
paulson@2274
    84
(**** Autheticity properties for Woo-Lam ****)
paulson@2274
    85
paulson@2274
    86
paulson@2274
    87
(*** WL4 ***)
paulson@2274
    88
paulson@2274
    89
(*If the encrypted message appears then it originated with Alice*)
paulson@2274
    90
goal thy 
paulson@3683
    91
 "!!evs. [| A ~: bad;  evs : woolam |]                        \
paulson@3683
    92
\        ==> Crypt (shrK A) (Nonce NB) : parts (spies evs)  \
paulson@3519
    93
\            --> (EX B. Says A B (Crypt (shrK A) (Nonce NB)) : set evs)";
paulson@3519
    94
by (parts_induct_tac 1);
paulson@3121
    95
by (Fake_parts_insert_tac 1);
paulson@3121
    96
by (Blast_tac 1);
paulson@2274
    97
qed_spec_mp "NB_Crypt_imp_Alice_msg";
paulson@2274
    98
paulson@2274
    99
(*Guarantee for Server: if it gets a message containing a certificate from 
paulson@2274
   100
  Alice, then she originated that certificate.  But we DO NOT know that B
paulson@2274
   101
  ever saw it: the Spy may have rerouted the message to the Server.*)
paulson@2274
   102
goal thy 
paulson@3683
   103
 "!!evs. [| A ~: bad;  evs : woolam;                      \
paulson@2283
   104
\           Says B' Server {|Agent A, Agent B, Crypt (shrK A) (Nonce NB)|} \
nipkow@3465
   105
\            : set evs |]                                  \
nipkow@3465
   106
\        ==> EX B. Says A B (Crypt (shrK A) (Nonce NB)) : set evs";
paulson@3121
   107
by (blast_tac (!claset addSIs [NB_Crypt_imp_Alice_msg]
paulson@2274
   108
                      addSEs [MPair_parts]
paulson@3683
   109
                      addDs  [Says_imp_spies RS parts.Inj]) 1);
paulson@2321
   110
qed "Server_trusts_WL4";
paulson@2274
   111
paulson@2274
   112
paulson@2274
   113
(*** WL5 ***)
paulson@2274
   114
paulson@2274
   115
(*Server sent WL5 only if it received the right sort of message*)
paulson@2274
   116
goal thy 
paulson@3466
   117
 "!!evs. evs : woolam ==>                                                   \
paulson@3466
   118
\        Says Server B (Crypt (shrK B) {|Agent A, NB|}) : set evs           \
paulson@2283
   119
\        --> (EX B'. Says B' Server {|Agent A, Agent B, Crypt (shrK A) NB|} \
nipkow@3465
   120
\               : set evs)";
paulson@3519
   121
by (parts_induct_tac 1);
paulson@3121
   122
by (Fake_parts_insert_tac 1);
paulson@3121
   123
by (ALLGOALS Blast_tac);
paulson@2274
   124
bind_thm ("Server_sent_WL5", result() RSN (2, rev_mp));
paulson@2274
   125
paulson@2274
   126
paulson@2274
   127
(*If the encrypted message appears then it originated with the Server!*)
paulson@2274
   128
goal thy 
paulson@3683
   129
 "!!evs. [| B ~: bad;  evs : woolam |]                             \
paulson@3683
   130
\        ==> Crypt (shrK B) {|Agent A, NB|} : parts (spies evs)  \
nipkow@3465
   131
\        --> Says Server B (Crypt (shrK B) {|Agent A, NB|}) : set evs";
paulson@3519
   132
by (parts_induct_tac 1);
paulson@3121
   133
by (Fake_parts_insert_tac 1);
paulson@2274
   134
qed_spec_mp "NB_Crypt_imp_Server_msg";
paulson@2274
   135
paulson@2274
   136
(*Partial guarantee for B: if it gets a message of correct form then the Server
paulson@2274
   137
  sent the same message.*)
paulson@2274
   138
goal thy 
paulson@3466
   139
 "!!evs. [| Says S B (Crypt (shrK B) {|Agent A, NB|}) : set evs;         \
paulson@3683
   140
\           B ~: bad;  evs : woolam |]                                  \
nipkow@3465
   141
\        ==> Says Server B (Crypt (shrK B) {|Agent A, NB|}) : set evs";
paulson@3121
   142
by (blast_tac (!claset addSIs [NB_Crypt_imp_Server_msg]
paulson@3683
   143
                      addDs  [Says_imp_spies RS parts.Inj]) 1);
paulson@2274
   144
qed "B_got_WL5";
paulson@2274
   145
paulson@2274
   146
(*Guarantee for B.  If B gets the Server's certificate then A has encrypted
paulson@2274
   147
  the nonce using her key.  This event can be no older than the nonce itself.
paulson@2274
   148
  But A may have sent the nonce to some other agent and it could have reached
paulson@2274
   149
  the Server via the Spy.*)
paulson@2274
   150
goal thy 
nipkow@3465
   151
 "!!evs. [| Says S B (Crypt (shrK B) {|Agent A, Nonce NB|}): set evs; \
paulson@3683
   152
\           A ~: bad;  B ~: bad;  evs : woolam  |]                  \
nipkow@3465
   153
\        ==> EX B. Says A B (Crypt (shrK A) (Nonce NB)) : set evs";
paulson@3121
   154
by (blast_tac (!claset addIs  [Server_trusts_WL4]
paulson@2274
   155
                      addSDs [B_got_WL5 RS Server_sent_WL5]) 1);
paulson@2321
   156
qed "B_trusts_WL5";
paulson@2274
   157
paulson@2274
   158
paulson@2274
   159
(*B only issues challenges in response to WL1.  Useful??*)
paulson@2274
   160
goal thy 
paulson@3519
   161
 "!!evs. [| B ~= Spy;  evs : woolam |]        \
nipkow@3465
   162
\    ==> Says B A (Nonce NB) : set evs        \
nipkow@3465
   163
\        --> (EX A'. Says A' B (Agent A) : set evs)";
paulson@3519
   164
by (parts_induct_tac 1);
paulson@3121
   165
by (Fake_parts_insert_tac 1);
paulson@3121
   166
by (ALLGOALS Blast_tac);
paulson@2274
   167
bind_thm ("B_said_WL2", result() RSN (2, rev_mp));
paulson@2274
   168
paulson@2274
   169
paulson@2274
   170
(**CANNOT be proved because A doesn't know where challenges come from...
paulson@2274
   171
goal thy 
paulson@3683
   172
 "!!evs. [| A ~: bad;  B ~= Spy;  evs : woolam |]           \
paulson@3683
   173
\    ==> Crypt (shrK A) (Nonce NB) : parts (spies evs) &  \
paulson@3519
   174
\        Says B A (Nonce NB) : set evs                       \
nipkow@3465
   175
\        --> Says A B (Crypt (shrK A) (Nonce NB)) : set evs";
paulson@3519
   176
by (parts_induct_tac 1);
paulson@3121
   177
by (Fake_parts_insert_tac 1);
paulson@2274
   178
by (Step_tac 1);
paulson@3121
   179
by (blast_tac (!claset addSEs partsEs) 1);
paulson@2274
   180
**)