src/HOL/Auth/WooLam.ML

Some X-symbols for <notin>, <noteq>, <forall>, <exists>
Streamlining of Yahalom proofs
Removal of redundant proofs

(*  Title:      HOL/Auth/WooLam
    ID:         $Id$
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
    Copyright   1996  University of Cambridge

Inductive relation "woolam" for the Woo-Lam protocol.

Simplified version from page 11 of
  Abadi and Needham.  Prudent Engineering Practice for Cryptographic Protocols.
  IEEE Trans. S.E. 22(1), 1996, pages 6-15.
*)

AddDs  [Says_imp_knows_Spy RS parts.Inj, parts.Body];
AddDs  [impOfSubs analz_subset_parts, impOfSubs Fake_parts_insert];


(*A "possibility property": there are traces that reach the end*)
Goal "\\<exists>NB. \\<exists>evs \\<in> woolam.  \
\           Says Server B (Crypt (shrK B) {|Agent A, Nonce NB|}) \\<in> set evs";
by (REPEAT (resolve_tac [exI,bexI] 1));
by (rtac (woolam.Nil RS woolam.WL1 RS woolam.WL2 RS woolam.WL3 RS 
          woolam.WL4 RS woolam.WL5) 2);
by possibility_tac;
result();


(**** Inductive proofs about woolam ****)

(** For reasoning about the encrypted portion of messages **)

Goal "Says A' B X \\<in> set evs ==> X \\<in> analz (spies evs)";
by (etac (Says_imp_spies RS analz.Inj) 1);
qed "WL4_analz_spies";

bind_thm ("WL4_parts_spies",
          WL4_analz_spies RS (impOfSubs analz_subset_parts));

(*For proving the easier theorems about X \\<notin> parts (spies evs) *)
fun parts_induct_tac i = 
    etac woolam.induct i  THEN 
    ftac WL4_parts_spies (i+5)  THEN
    prove_simple_subgoals_tac 1;


(** Theorems of the form X \\<notin> parts (spies evs) imply that NOBODY
    sends messages containing X! **)

(*Spy never sees another agent's shared key! (unless it's bad at start)*)
Goal "evs \\<in> woolam ==> (Key (shrK A) \\<in> parts (spies evs)) = (A \\<in> bad)";
by (parts_induct_tac 1);
by (Blast_tac 1);
qed "Spy_see_shrK";
Addsimps [Spy_see_shrK];

Goal "evs \\<in> woolam ==> (Key (shrK A) \\<in> analz (spies evs)) = (A \\<in> bad)";
by Auto_tac;
qed "Spy_analz_shrK";
Addsimps [Spy_analz_shrK];

AddSDs [Spy_see_shrK RSN (2, rev_iffD1), 
	Spy_analz_shrK RSN (2, rev_iffD1)];


(**** Autheticity properties for Woo-Lam ****)


(*** WL4 ***)

(*If the encrypted message appears then it originated with Alice*)
Goal "[| Crypt (shrK A) (Nonce NB) \\<in> parts (spies evs);  \
\        A \\<notin> bad;  evs \\<in> woolam |]                      \
\     ==> \\<exists>B. Says A B (Crypt (shrK A) (Nonce NB)) \\<in> set evs";
by (etac rev_mp 1);
by (parts_induct_tac 1);
by (ALLGOALS Blast_tac);
qed "NB_Crypt_imp_Alice_msg";

(*Guarantee for Server: if it gets a message containing a certificate from 
  Alice, then she originated that certificate.  But we DO NOT know that B
  ever saw it: the Spy may have rerouted the message to the Server.*)
Goal "[| Says B' Server {|Agent A, Agent B, Crypt (shrK A) (Nonce NB)|} \
\          \\<in> set evs;                                                   \
\        A \\<notin> bad;  evs \\<in> woolam |]                                     \
\     ==> \\<exists>B. Says A B (Crypt (shrK A) (Nonce NB)) \\<in> set evs";
by (blast_tac (claset() addSIs [NB_Crypt_imp_Alice_msg]) 1);
qed "Server_trusts_WL4";

AddDs [Server_trusts_WL4];


(*** WL5 ***)

(*Server sent WL5 only if it received the right sort of message*)
Goal "[| Says Server B (Crypt (shrK B) {|Agent A, NB|}) \\<in> set evs;      \
\        evs \\<in> woolam |]                                                \
\     ==> \\<exists>B'. Says B' Server {|Agent A, Agent B, Crypt (shrK A) NB|} \
\            \\<in> set evs";
by (etac rev_mp 1);
by (parts_induct_tac 1);
by (ALLGOALS Blast_tac);
qed "Server_sent_WL5";

AddDs [Server_sent_WL5];

(*If the encrypted message appears then it originated with the Server!*)
Goal "[| Crypt (shrK B) {|Agent A, NB|} \\<in> parts (spies evs);  \
\        B \\<notin> bad;  evs \\<in> woolam |]                           \
\     ==> Says Server B (Crypt (shrK B) {|Agent A, NB|}) \\<in> set evs";
by (etac rev_mp 1);
by (parts_induct_tac 1);
by (Blast_tac 1);
qed_spec_mp "NB_Crypt_imp_Server_msg";

(*Guarantee for B.  If B gets the Server's certificate then A has encrypted
  the nonce using her key.  This event can be no older than the nonce itself.
  But A may have sent the nonce to some other agent and it could have reached
  the Server via the Spy.*)
Goal "[| Says S B (Crypt (shrK B) {|Agent A, Nonce NB|}): set evs; \
\        A \\<notin> bad;  B \\<notin> bad;  evs \\<in> woolam  |]                  \
\     ==> \\<exists>B. Says A B (Crypt (shrK A) (Nonce NB)) \\<in> set evs";
by (blast_tac (claset() addSDs [NB_Crypt_imp_Server_msg]) 1);
qed "B_trusts_WL5";


(*B only issues challenges in response to WL1.  Not used.*)
Goal "[| Says B A (Nonce NB) \\<in> set evs;  B \\<noteq> Spy;  evs \\<in> woolam |]  \
\     ==> \\<exists>A'. Says A' B (Agent A) \\<in> set evs";
by (etac rev_mp 1);
by (parts_induct_tac 1);
by (ALLGOALS Blast_tac);
qed "B_said_WL2";


(**CANNOT be proved because A doesn't know where challenges come from...
Goal "[| A \\<notin> bad;  B \\<noteq> Spy;  evs \\<in> woolam |]           \
\ ==> Crypt (shrK A) (Nonce NB) \\<in> parts (spies evs) &  \
\     Says B A (Nonce NB) \\<in> set evs                       \
\     --> Says A B (Crypt (shrK A) (Nonce NB)) \\<in> set evs";
by (parts_induct_tac 1);
by (Blast_tac 1);
by Safe_tac;
**)