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