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