src/HOL/Auth/Event.thy
author paulson
Tue Apr 29 12:36:49 2003 +0200 (2003-04-29)
changeset 13935 4822d9597d1e
parent 13926 6e62e5357a10
child 13956 8fe7e12290e1
permissions -rw-r--r--
tweaks
     1 (*  Title:      HOL/Auth/Event
     2     ID:         $Id$
     3     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     4     Copyright   1996  University of Cambridge
     5 
     6 Theory of events for security protocols
     7 
     8 Datatype of events; function "spies"; freshness
     9 
    10 "bad" agents have been broken by the Spy; their private keys and internal
    11     stores are visible to him
    12 *)
    13 
    14 theory Event = Message:
    15 
    16 consts  (*Initial states of agents -- parameter of the construction*)
    17   initState :: "agent => msg set"
    18 
    19 datatype
    20   event = Says  agent agent msg
    21         | Gets  agent       msg
    22         | Notes agent       msg
    23        
    24 consts 
    25   bad    :: "agent set"				(*compromised agents*)
    26   knows  :: "agent => event list => msg set"
    27 
    28 
    29 (*"spies" is retained for compatibility's sake*)
    30 syntax
    31   spies  :: "event list => msg set"
    32 
    33 translations
    34   "spies"   => "knows Spy"
    35 
    36 
    37 axioms
    38   (*Spy has access to his own key for spoof messages, but Server is secure*)
    39   Spy_in_bad     [iff] :    "Spy \<in> bad"
    40   Server_not_bad [iff] : "Server \<notin> bad"
    41 
    42 primrec
    43   knows_Nil:   "knows A [] = initState A"
    44   knows_Cons:
    45     "knows A (ev # evs) =
    46        (if A = Spy then 
    47 	(case ev of
    48 	   Says A' B X => insert X (knows Spy evs)
    49 	 | Gets A' X => knows Spy evs
    50 	 | Notes A' X  => 
    51 	     if A' \<in> bad then insert X (knows Spy evs) else knows Spy evs)
    52 	else
    53 	(case ev of
    54 	   Says A' B X => 
    55 	     if A'=A then insert X (knows A evs) else knows A evs
    56 	 | Gets A' X    => 
    57 	     if A'=A then insert X (knows A evs) else knows A evs
    58 	 | Notes A' X    => 
    59 	     if A'=A then insert X (knows A evs) else knows A evs))"
    60 
    61 (*
    62   Case A=Spy on the Gets event
    63   enforces the fact that if a message is received then it must have been sent,
    64   therefore the oops case must use Notes
    65 *)
    66 
    67 consts
    68   (*Set of items that might be visible to somebody:
    69     complement of the set of fresh items*)
    70   used :: "event list => msg set"
    71 
    72 primrec
    73   used_Nil:   "used []         = (UN B. parts (initState B))"
    74   used_Cons:  "used (ev # evs) =
    75 		     (case ev of
    76 			Says A B X => parts {X} \<union> used evs
    77 		      | Gets A X   => used evs
    78 		      | Notes A X  => parts {X} \<union> used evs)"
    79     --{*The case for @{term Gets} seems anomalous, but @{term Gets} always
    80         follows @{term Says} in real protocols.  Seems difficult to change.
    81         See @{text Gets_correct} in theory @{text "Guard/Extensions.thy"}. *}
    82 
    83 lemma Notes_imp_used [rule_format]: "Notes A X \<in> set evs --> X \<in> used evs"
    84 apply (induct_tac evs)
    85 apply (auto split: event.split) 
    86 done
    87 
    88 lemma Says_imp_used [rule_format]: "Says A B X \<in> set evs --> X \<in> used evs"
    89 apply (induct_tac evs)
    90 apply (auto split: event.split) 
    91 done
    92 
    93 lemma MPair_used [rule_format]:
    94      "MPair X Y \<in> used evs --> X \<in> used evs & Y \<in> used evs"
    95 apply (induct_tac evs)
    96 apply (auto split: event.split) 
    97 done
    98 
    99 
   100 subsection{*Function @{term knows}*}
   101 
   102 text{*Simplifying   @term{"parts (insert X (knows Spy evs))
   103       = parts {X} \<union> parts (knows Spy evs)"}.  The general case loops.*)
   104 
   105 text{*This version won't loop with the simplifier.*}
   106 lemmas parts_insert_knows_A = parts_insert [of _ "knows A evs", standard]
   107 
   108 lemma knows_Spy_Says [simp]:
   109      "knows Spy (Says A B X # evs) = insert X (knows Spy evs)"
   110 by simp
   111 
   112 text{*The point of letting the Spy see "bad" agents' notes is to prevent
   113   redundant case-splits on whether A=Spy and whether A:bad*}
   114 lemma knows_Spy_Notes [simp]:
   115      "knows Spy (Notes A X # evs) =  
   116           (if A:bad then insert X (knows Spy evs) else knows Spy evs)"
   117 by simp
   118 
   119 lemma knows_Spy_Gets [simp]: "knows Spy (Gets A X # evs) = knows Spy evs"
   120 by simp
   121 
   122 lemma knows_Spy_subset_knows_Spy_Says:
   123      "knows Spy evs \<subseteq> knows Spy (Says A B X # evs)"
   124 by (simp add: subset_insertI)
   125 
   126 lemma knows_Spy_subset_knows_Spy_Notes:
   127      "knows Spy evs \<subseteq> knows Spy (Notes A X # evs)"
   128 by force
   129 
   130 lemma knows_Spy_subset_knows_Spy_Gets:
   131      "knows Spy evs \<subseteq> knows Spy (Gets A X # evs)"
   132 by (simp add: subset_insertI)
   133 
   134 text{*Spy sees what is sent on the traffic*}
   135 lemma Says_imp_knows_Spy [rule_format]:
   136      "Says A B X \<in> set evs --> X \<in> knows Spy evs"
   137 apply (induct_tac "evs")
   138 apply (simp_all (no_asm_simp) split add: event.split)
   139 done
   140 
   141 lemma Notes_imp_knows_Spy [rule_format]:
   142      "Notes A X \<in> set evs --> A: bad --> X \<in> knows Spy evs"
   143 apply (induct_tac "evs")
   144 apply (simp_all (no_asm_simp) split add: event.split)
   145 done
   146 
   147 
   148 text{*Elimination rules: derive contradictions from old Says events containing
   149   items known to be fresh*}
   150 lemmas knows_Spy_partsEs =
   151      Says_imp_knows_Spy [THEN parts.Inj, THEN revcut_rl, standard] 
   152      parts.Body [THEN revcut_rl, standard]
   153 
   154 text{*Compatibility for the old "spies" function*}
   155 lemmas spies_partsEs = knows_Spy_partsEs
   156 lemmas Says_imp_spies = Says_imp_knows_Spy
   157 lemmas parts_insert_spies = parts_insert_knows_A [of _ Spy]
   158 
   159 
   160 subsection{*Knowledge of Agents*}
   161 
   162 lemma knows_Says: "knows A (Says A B X # evs) = insert X (knows A evs)"
   163 by simp
   164 
   165 lemma knows_Notes: "knows A (Notes A X # evs) = insert X (knows A evs)"
   166 by simp
   167 
   168 lemma knows_Gets:
   169      "A \<noteq> Spy --> knows A (Gets A X # evs) = insert X (knows A evs)"
   170 by simp
   171 
   172 
   173 lemma knows_subset_knows_Says: "knows A evs \<subseteq> knows A (Says A' B X # evs)"
   174 by (simp add: subset_insertI)
   175 
   176 lemma knows_subset_knows_Notes: "knows A evs \<subseteq> knows A (Notes A' X # evs)"
   177 by (simp add: subset_insertI)
   178 
   179 lemma knows_subset_knows_Gets: "knows A evs \<subseteq> knows A (Gets A' X # evs)"
   180 by (simp add: subset_insertI)
   181 
   182 text{*Agents know what they say*}
   183 lemma Says_imp_knows [rule_format]: "Says A B X \<in> set evs --> X \<in> knows A evs"
   184 apply (induct_tac "evs")
   185 apply (simp_all (no_asm_simp) split add: event.split)
   186 apply blast
   187 done
   188 
   189 text{*Agents know what they note*}
   190 lemma Notes_imp_knows [rule_format]: "Notes A X \<in> set evs --> X \<in> knows A evs"
   191 apply (induct_tac "evs")
   192 apply (simp_all (no_asm_simp) split add: event.split)
   193 apply blast
   194 done
   195 
   196 text{*Agents know what they receive*}
   197 lemma Gets_imp_knows_agents [rule_format]:
   198      "A \<noteq> Spy --> Gets A X \<in> set evs --> X \<in> knows A evs"
   199 apply (induct_tac "evs")
   200 apply (simp_all (no_asm_simp) split add: event.split)
   201 done
   202 
   203 
   204 text{*What agents DIFFERENT FROM Spy know 
   205   was either said, or noted, or got, or known initially*}
   206 lemma knows_imp_Says_Gets_Notes_initState [rule_format]:
   207      "[| X \<in> knows A evs; A \<noteq> Spy |] ==> EX B.  
   208   Says A B X \<in> set evs | Gets A X \<in> set evs | Notes A X \<in> set evs | X \<in> initState A"
   209 apply (erule rev_mp)
   210 apply (induct_tac "evs")
   211 apply (simp_all (no_asm_simp) split add: event.split)
   212 apply blast
   213 done
   214 
   215 text{*What the Spy knows -- for the time being --
   216   was either said or noted, or known initially*}
   217 lemma knows_Spy_imp_Says_Notes_initState [rule_format]:
   218      "[| X \<in> knows Spy evs |] ==> EX A B.  
   219   Says A B X \<in> set evs | Notes A X \<in> set evs | X \<in> initState Spy"
   220 apply (erule rev_mp)
   221 apply (induct_tac "evs")
   222 apply (simp_all (no_asm_simp) split add: event.split)
   223 apply blast
   224 done
   225 
   226 lemma parts_knows_Spy_subset_used: "parts (knows Spy evs) \<subseteq> used evs"
   227 apply (induct_tac "evs", force)  
   228 apply (simp add: parts_insert_knows_A knows_Cons add: event.split, blast) 
   229 done
   230 
   231 lemmas usedI = parts_knows_Spy_subset_used [THEN subsetD, intro]
   232 
   233 lemma initState_into_used: "X \<in> parts (initState B) ==> X \<in> used evs"
   234 apply (induct_tac "evs")
   235 apply (simp_all add: parts_insert_knows_A split add: event.split, blast)
   236 done
   237 
   238 lemma used_Says [simp]: "used (Says A B X # evs) = parts{X} \<union> used evs"
   239 by simp
   240 
   241 lemma used_Notes [simp]: "used (Notes A X # evs) = parts{X} \<union> used evs"
   242 by simp
   243 
   244 lemma used_Gets [simp]: "used (Gets A X # evs) = used evs"
   245 by simp
   246 
   247 lemma used_nil_subset: "used [] \<subseteq> used evs"
   248 apply simp
   249 apply (blast intro: initState_into_used)
   250 done
   251 
   252 text{*NOTE REMOVAL--laws above are cleaner, as they don't involve "case"*}
   253 declare knows_Cons [simp del]
   254         used_Nil [simp del] used_Cons [simp del]
   255 
   256 
   257 text{*For proving theorems of the form @{term "X \<notin> analz (knows Spy evs) --> P"}
   258   New events added by induction to "evs" are discarded.  Provided 
   259   this information isn't needed, the proof will be much shorter, since
   260   it will omit complicated reasoning about @{term analz}.*}
   261 
   262 lemmas analz_mono_contra =
   263        knows_Spy_subset_knows_Spy_Says [THEN analz_mono, THEN contra_subsetD]
   264        knows_Spy_subset_knows_Spy_Notes [THEN analz_mono, THEN contra_subsetD]
   265        knows_Spy_subset_knows_Spy_Gets [THEN analz_mono, THEN contra_subsetD]
   266 
   267 ML
   268 {*
   269 val analz_mono_contra_tac = 
   270   let val analz_impI = inst "P" "?Y \<notin> analz (knows Spy ?evs)" impI
   271   in
   272     rtac analz_impI THEN' 
   273     REPEAT1 o 
   274       (dresolve_tac (thms"analz_mono_contra"))
   275     THEN' mp_tac
   276   end
   277 *}
   278 
   279 
   280 lemma knows_subset_knows_Cons: "knows A evs \<subseteq> knows A (e # evs)"
   281 by (induct e, auto simp: knows_Cons)
   282 
   283 lemma initState_subset_knows: "initState A \<subseteq> knows A evs"
   284 apply (induct_tac evs, simp) 
   285 apply (blast intro: knows_subset_knows_Cons [THEN subsetD])
   286 done
   287 
   288 
   289 text{*For proving @{text new_keys_not_used}*}
   290 lemma keysFor_parts_insert:
   291      "[| K \<in> keysFor (parts (insert X G));  X \<in> synth (analz H) |] 
   292       ==> K \<in> keysFor (parts (G \<union> H)) | Key (invKey K) \<in> parts H"; 
   293 by (force 
   294     dest!: parts_insert_subset_Un [THEN keysFor_mono, THEN [2] rev_subsetD]
   295            analz_subset_parts [THEN keysFor_mono, THEN [2] rev_subsetD]
   296     intro: analz_subset_parts [THEN subsetD] parts_mono [THEN [2] rev_subsetD])
   297 
   298 method_setup analz_mono_contra = {*
   299     Method.no_args
   300       (Method.METHOD (fn facts => REPEAT_FIRST analz_mono_contra_tac)) *}
   301     "for proving theorems of the form X \<notin> analz (knows Spy evs) --> P"
   302 
   303 subsubsection{*Useful for case analysis on whether a hash is a spoof or not*}
   304 
   305 ML
   306 {*
   307 val knows_Cons     = thm "knows_Cons"
   308 val used_Nil       = thm "used_Nil"
   309 val used_Cons      = thm "used_Cons"
   310 
   311 val Notes_imp_used = thm "Notes_imp_used";
   312 val Says_imp_used = thm "Says_imp_used";
   313 val MPair_used = thm "MPair_used";
   314 val Says_imp_knows_Spy = thm "Says_imp_knows_Spy";
   315 val Notes_imp_knows_Spy = thm "Notes_imp_knows_Spy";
   316 val knows_Spy_partsEs = thms "knows_Spy_partsEs";
   317 val spies_partsEs = thms "spies_partsEs";
   318 val Says_imp_spies = thm "Says_imp_spies";
   319 val parts_insert_spies = thm "parts_insert_spies";
   320 val Says_imp_knows = thm "Says_imp_knows";
   321 val Notes_imp_knows = thm "Notes_imp_knows";
   322 val Gets_imp_knows_agents = thm "Gets_imp_knows_agents";
   323 val knows_imp_Says_Gets_Notes_initState = thm "knows_imp_Says_Gets_Notes_initState";
   324 val knows_Spy_imp_Says_Notes_initState = thm "knows_Spy_imp_Says_Notes_initState";
   325 val usedI = thm "usedI";
   326 val initState_into_used = thm "initState_into_used";
   327 val used_Says = thm "used_Says";
   328 val used_Notes = thm "used_Notes";
   329 val used_Gets = thm "used_Gets";
   330 val used_nil_subset = thm "used_nil_subset";
   331 val analz_mono_contra = thms "analz_mono_contra";
   332 val knows_subset_knows_Cons = thm "knows_subset_knows_Cons";
   333 val initState_subset_knows = thm "initState_subset_knows";
   334 val keysFor_parts_insert = thm "keysFor_parts_insert";
   335 
   336 
   337 val synth_analz_mono = thm "synth_analz_mono";
   338 
   339 val knows_Spy_subset_knows_Spy_Says = thm "knows_Spy_subset_knows_Spy_Says";
   340 val knows_Spy_subset_knows_Spy_Notes = thm "knows_Spy_subset_knows_Spy_Notes";
   341 val knows_Spy_subset_knows_Spy_Gets = thm "knows_Spy_subset_knows_Spy_Gets";
   342 
   343 
   344 val synth_analz_mono_contra_tac = 
   345   let val syan_impI = inst "P" "?Y \<notin> synth (analz (knows Spy ?evs))" impI
   346   in
   347     rtac syan_impI THEN' 
   348     REPEAT1 o 
   349       (dresolve_tac 
   350        [knows_Spy_subset_knows_Spy_Says RS synth_analz_mono RS contra_subsetD,
   351         knows_Spy_subset_knows_Spy_Notes RS synth_analz_mono RS contra_subsetD,
   352 	knows_Spy_subset_knows_Spy_Gets RS synth_analz_mono RS contra_subsetD])
   353     THEN'
   354     mp_tac
   355   end;
   356 *}
   357 
   358 method_setup synth_analz_mono_contra = {*
   359     Method.no_args
   360       (Method.METHOD (fn facts => REPEAT_FIRST synth_analz_mono_contra_tac)) *}
   361     "for proving theorems of the form X \<notin> synth (analz (knows Spy evs)) --> P"
   362 
   363 end