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