author | wenzelm |
Sat, 05 Jan 2019 17:24:33 +0100 | |
changeset 69597 | ff784d5a5bfb |
parent 69505 | cc2d676d5395 |
permissions | -rw-r--r-- |
49322 | 1 |
(* Author: Lawrence C Paulson, Cambridge University Computer Laboratory |
11250 | 2 |
Copyright 1996 University of Cambridge |
3 |
||
4 |
Datatype of events; function "spies"; freshness |
|
5 |
||
6 |
"bad" agents have been broken by the Spy; their private keys and internal |
|
7 |
stores are visible to him |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
8 |
*)(*<*) |
11250 | 9 |
|
67406 | 10 |
section\<open>Theory of Events for Security Protocols\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
11 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
12 |
theory Event imports Message begin |
11250 | 13 |
|
14 |
consts (*Initial states of agents -- parameter of the construction*) |
|
67613 | 15 |
initState :: "agent \<Rightarrow> msg set" |
11250 | 16 |
|
17 |
datatype |
|
18 |
event = Says agent agent msg |
|
19 |
| Gets agent msg |
|
20 |
| Notes agent msg |
|
21 |
||
22 |
consts |
|
67406 | 23 |
bad :: "agent set" \<comment> \<open>compromised agents\<close> |
11250 | 24 |
|
25 |
||
67406 | 26 |
text\<open>The constant "spies" is retained for compatibility's sake\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
27 |
|
11250 | 28 |
primrec |
67613 | 29 |
knows :: "agent \<Rightarrow> event list \<Rightarrow> msg set" |
39795 | 30 |
where |
11250 | 31 |
knows_Nil: "knows A [] = initState A" |
39795 | 32 |
| knows_Cons: |
11250 | 33 |
"knows A (ev # evs) = |
34 |
(if A = Spy then |
|
32960
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
30548
diff
changeset
|
35 |
(case ev of |
67613 | 36 |
Says A' B X \<Rightarrow> insert X (knows Spy evs) |
37 |
| Gets A' X \<Rightarrow> knows Spy evs |
|
38 |
| Notes A' X \<Rightarrow> |
|
32960
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
30548
diff
changeset
|
39 |
if A' \<in> bad then insert X (knows Spy evs) else knows Spy evs) |
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
30548
diff
changeset
|
40 |
else |
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
30548
diff
changeset
|
41 |
(case ev of |
67613 | 42 |
Says A' B X \<Rightarrow> |
32960
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
30548
diff
changeset
|
43 |
if A'=A then insert X (knows A evs) else knows A evs |
67613 | 44 |
| Gets A' X \<Rightarrow> |
32960
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
30548
diff
changeset
|
45 |
if A'=A then insert X (knows A evs) else knows A evs |
67613 | 46 |
| Notes A' X \<Rightarrow> |
32960
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
30548
diff
changeset
|
47 |
if A'=A then insert X (knows A evs) else knows A evs))" |
11250 | 48 |
|
39795 | 49 |
abbreviation (input) |
67613 | 50 |
spies :: "event list \<Rightarrow> msg set" where |
39795 | 51 |
"spies == knows Spy" |
52 |
||
67406 | 53 |
text\<open>Spy has access to his own key for spoof messages, but Server is secure\<close> |
39795 | 54 |
specification (bad) |
55 |
Spy_in_bad [iff]: "Spy \<in> bad" |
|
56 |
Server_not_bad [iff]: "Server \<notin> bad" |
|
57 |
by (rule exI [of _ "{Spy}"], simp) |
|
58 |
||
11250 | 59 |
(* |
60 |
Case A=Spy on the Gets event |
|
61 |
enforces the fact that if a message is received then it must have been sent, |
|
62 |
therefore the oops case must use Notes |
|
63 |
*) |
|
64 |
||
39795 | 65 |
primrec |
11250 | 66 |
(*Set of items that might be visible to somebody: |
67 |
complement of the set of fresh items*) |
|
67613 | 68 |
used :: "event list \<Rightarrow> msg set" |
39795 | 69 |
where |
11250 | 70 |
used_Nil: "used [] = (UN B. parts (initState B))" |
39795 | 71 |
| used_Cons: "used (ev # evs) = |
32960
69916a850301
eliminated hard tabulators, guessing at each author's individual tab-width;
wenzelm
parents:
30548
diff
changeset
|
72 |
(case ev of |
67613 | 73 |
Says A B X \<Rightarrow> parts {X} \<union> used evs |
74 |
| Gets A X \<Rightarrow> used evs |
|
75 |
| Notes A X \<Rightarrow> parts {X} \<union> used evs)" |
|
69597 | 76 |
\<comment> \<open>The case for \<^term>\<open>Gets\<close> seems anomalous, but \<^term>\<open>Gets\<close> always |
77 |
follows \<^term>\<open>Says\<close> in real protocols. Seems difficult to change. |
|
78 |
See \<^text>\<open>Gets_correct\<close> in theory \<^text>\<open>Guard/Extensions.thy\<close>.\<close> |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
79 |
|
67613 | 80 |
lemma Notes_imp_used [rule_format]: "Notes A X \<in> set evs \<longrightarrow> X \<in> used evs" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
81 |
apply (induct_tac evs) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
82 |
apply (auto split: event.split) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
83 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
84 |
|
67613 | 85 |
lemma Says_imp_used [rule_format]: "Says A B X \<in> set evs \<longrightarrow> X \<in> used evs" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
86 |
apply (induct_tac evs) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
87 |
apply (auto split: event.split) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
88 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
89 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
90 |
|
69597 | 91 |
subsection\<open>Function \<^term>\<open>knows\<close>\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
92 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
93 |
(*Simplifying |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
94 |
parts(insert X (knows Spy evs)) = parts{X} \<union> parts(knows Spy evs). |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
95 |
This version won't loop with the simplifier.*) |
55142 | 96 |
lemmas parts_insert_knows_A = parts_insert [of _ "knows A evs"] for A evs |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
97 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
98 |
lemma knows_Spy_Says [simp]: |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
99 |
"knows Spy (Says A B X # evs) = insert X (knows Spy evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
100 |
by simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
101 |
|
67406 | 102 |
text\<open>Letting the Spy see "bad" agents' notes avoids redundant case-splits |
69597 | 103 |
on whether \<^term>\<open>A=Spy\<close> and whether \<^term>\<open>A\<in>bad\<close>\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
104 |
lemma knows_Spy_Notes [simp]: |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
105 |
"knows Spy (Notes A X # evs) = |
67613 | 106 |
(if A\<in>bad then insert X (knows Spy evs) else knows Spy evs)" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
107 |
by simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
108 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
109 |
lemma knows_Spy_Gets [simp]: "knows Spy (Gets A X # evs) = knows Spy evs" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
110 |
by simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
111 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
112 |
lemma knows_Spy_subset_knows_Spy_Says: |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
113 |
"knows Spy evs \<subseteq> knows Spy (Says A B X # evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
114 |
by (simp add: subset_insertI) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
115 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
116 |
lemma knows_Spy_subset_knows_Spy_Notes: |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
117 |
"knows Spy evs \<subseteq> knows Spy (Notes A X # evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
118 |
by force |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
119 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
120 |
lemma knows_Spy_subset_knows_Spy_Gets: |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
121 |
"knows Spy evs \<subseteq> knows Spy (Gets A X # evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
122 |
by (simp add: subset_insertI) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
123 |
|
67406 | 124 |
text\<open>Spy sees what is sent on the traffic\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
125 |
lemma Says_imp_knows_Spy [rule_format]: |
67613 | 126 |
"Says A B X \<in> set evs \<longrightarrow> X \<in> knows Spy evs" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
127 |
apply (induct_tac "evs") |
63648 | 128 |
apply (simp_all (no_asm_simp) split: event.split) |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
129 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
130 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
131 |
lemma Notes_imp_knows_Spy [rule_format]: |
67613 | 132 |
"Notes A X \<in> set evs \<longrightarrow> A \<in> bad \<longrightarrow> X \<in> knows Spy evs" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
133 |
apply (induct_tac "evs") |
63648 | 134 |
apply (simp_all (no_asm_simp) split: event.split) |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
135 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
136 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
137 |
|
67406 | 138 |
text\<open>Elimination rules: derive contradictions from old Says events containing |
139 |
items known to be fresh\<close> |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
140 |
lemmas knows_Spy_partsEs = |
46471 | 141 |
Says_imp_knows_Spy [THEN parts.Inj, elim_format] |
142 |
parts.Body [elim_format] |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
143 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
144 |
lemmas Says_imp_analz_Spy = Says_imp_knows_Spy [THEN analz.Inj] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
145 |
|
67406 | 146 |
text\<open>Compatibility for the old "spies" function\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
147 |
lemmas spies_partsEs = knows_Spy_partsEs |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
148 |
lemmas Says_imp_spies = Says_imp_knows_Spy |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
149 |
lemmas parts_insert_spies = parts_insert_knows_A [of _ Spy] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
150 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
151 |
|
67406 | 152 |
subsection\<open>Knowledge of Agents\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
153 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
154 |
lemma knows_Says: "knows A (Says A B X # evs) = insert X (knows A evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
155 |
by simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
156 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
157 |
lemma knows_Notes: "knows A (Notes A X # evs) = insert X (knows A evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
158 |
by simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
159 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
160 |
lemma knows_Gets: |
67613 | 161 |
"A \<noteq> Spy \<longrightarrow> knows A (Gets A X # evs) = insert X (knows A evs)" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
162 |
by simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
163 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
164 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
165 |
lemma knows_subset_knows_Says: "knows A evs \<subseteq> knows A (Says A' B X # evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
166 |
by (simp add: subset_insertI) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
167 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
168 |
lemma knows_subset_knows_Notes: "knows A evs \<subseteq> knows A (Notes A' X # evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
169 |
by (simp add: subset_insertI) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
170 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
171 |
lemma knows_subset_knows_Gets: "knows A evs \<subseteq> knows A (Gets A' X # evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
172 |
by (simp add: subset_insertI) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
173 |
|
67406 | 174 |
text\<open>Agents know what they say\<close> |
67613 | 175 |
lemma Says_imp_knows [rule_format]: "Says A B X \<in> set evs \<longrightarrow> X \<in> knows A evs" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
176 |
apply (induct_tac "evs") |
63648 | 177 |
apply (simp_all (no_asm_simp) split: event.split) |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
178 |
apply blast |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
179 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
180 |
|
67406 | 181 |
text\<open>Agents know what they note\<close> |
67613 | 182 |
lemma Notes_imp_knows [rule_format]: "Notes A X \<in> set evs \<longrightarrow> X \<in> knows A evs" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
183 |
apply (induct_tac "evs") |
63648 | 184 |
apply (simp_all (no_asm_simp) split: event.split) |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
185 |
apply blast |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
186 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
187 |
|
67406 | 188 |
text\<open>Agents know what they receive\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
189 |
lemma Gets_imp_knows_agents [rule_format]: |
67613 | 190 |
"A \<noteq> Spy \<longrightarrow> Gets A X \<in> set evs \<longrightarrow> X \<in> knows A evs" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
191 |
apply (induct_tac "evs") |
63648 | 192 |
apply (simp_all (no_asm_simp) split: event.split) |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
193 |
done |
11250 | 194 |
|
195 |
||
67406 | 196 |
text\<open>What agents DIFFERENT FROM Spy know |
197 |
was either said, or noted, or got, or known initially\<close> |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
198 |
lemma knows_imp_Says_Gets_Notes_initState [rule_format]: |
67613 | 199 |
"[| X \<in> knows A evs; A \<noteq> Spy |] ==> \<exists>B. |
200 |
Says A B X \<in> set evs \<or> Gets A X \<in> set evs \<or> Notes A X \<in> set evs \<or> X \<in> initState A" |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
201 |
apply (erule rev_mp) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
202 |
apply (induct_tac "evs") |
63648 | 203 |
apply (simp_all (no_asm_simp) split: event.split) |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
204 |
apply blast |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
205 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
206 |
|
67406 | 207 |
text\<open>What the Spy knows -- for the time being -- |
208 |
was either said or noted, or known initially\<close> |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
209 |
lemma knows_Spy_imp_Says_Notes_initState [rule_format]: |
67613 | 210 |
"[| X \<in> knows Spy evs |] ==> \<exists>A B. |
211 |
Says A B X \<in> set evs \<or> Notes A X \<in> set evs \<or> X \<in> initState Spy" |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
212 |
apply (erule rev_mp) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
213 |
apply (induct_tac "evs") |
63648 | 214 |
apply (simp_all (no_asm_simp) split: event.split) |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
215 |
apply blast |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
216 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
217 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
218 |
lemma parts_knows_Spy_subset_used: "parts (knows Spy evs) \<subseteq> used evs" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
219 |
apply (induct_tac "evs", force) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
220 |
apply (simp add: parts_insert_knows_A knows_Cons add: event.split, blast) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
221 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
222 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
223 |
lemmas usedI = parts_knows_Spy_subset_used [THEN subsetD, intro] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
224 |
|
67613 | 225 |
lemma initState_into_used: "X \<in> parts (initState B) \<Longrightarrow> X \<in> used evs" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
226 |
apply (induct_tac "evs") |
63648 | 227 |
apply (simp_all add: parts_insert_knows_A split: event.split, blast) |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
228 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
229 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
230 |
lemma used_Says [simp]: "used (Says A B X # evs) = parts{X} \<union> used evs" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
231 |
by simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
232 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
233 |
lemma used_Notes [simp]: "used (Notes A X # evs) = parts{X} \<union> used evs" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
234 |
by simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
235 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
236 |
lemma used_Gets [simp]: "used (Gets A X # evs) = used evs" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
237 |
by simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
238 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
239 |
lemma used_nil_subset: "used [] \<subseteq> used evs" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
240 |
apply simp |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
241 |
apply (blast intro: initState_into_used) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
242 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
243 |
|
67406 | 244 |
text\<open>NOTE REMOVAL--laws above are cleaner, as they don't involve "case"\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
245 |
declare knows_Cons [simp del] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
246 |
used_Nil [simp del] used_Cons [simp del] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
247 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
248 |
|
69597 | 249 |
text\<open>For proving theorems of the form \<^term>\<open>X \<notin> analz (knows Spy evs) \<longrightarrow> P\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
250 |
New events added by induction to "evs" are discarded. Provided |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
251 |
this information isn't needed, the proof will be much shorter, since |
69597 | 252 |
it will omit complicated reasoning about \<^term>\<open>analz\<close>.\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
253 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
254 |
lemmas analz_mono_contra = |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
255 |
knows_Spy_subset_knows_Spy_Says [THEN analz_mono, THEN contra_subsetD] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
256 |
knows_Spy_subset_knows_Spy_Notes [THEN analz_mono, THEN contra_subsetD] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
257 |
knows_Spy_subset_knows_Spy_Gets [THEN analz_mono, THEN contra_subsetD] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
258 |
|
55142 | 259 |
lemmas analz_impI = impI [where P = "Y \<notin> analz (knows Spy evs)"] for Y evs |
27225 | 260 |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
261 |
ML |
67406 | 262 |
\<open> |
58963
26bf09b95dda
proper context for assume_tac (atac remains as fall-back without context);
wenzelm
parents:
58889
diff
changeset
|
263 |
fun analz_mono_contra_tac ctxt = |
60754 | 264 |
resolve_tac ctxt @{thms analz_impI} THEN' |
59498
50b60f501b05
proper context for resolve_tac, eresolve_tac, dresolve_tac, forward_tac etc.;
wenzelm
parents:
58963
diff
changeset
|
265 |
REPEAT1 o (dresolve_tac ctxt @{thms analz_mono_contra}) |
58963
26bf09b95dda
proper context for assume_tac (atac remains as fall-back without context);
wenzelm
parents:
58889
diff
changeset
|
266 |
THEN' mp_tac ctxt |
67406 | 267 |
\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
268 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
269 |
lemma knows_subset_knows_Cons: "knows A evs \<subseteq> knows A (e # evs)" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
270 |
by (induct e, auto simp: knows_Cons) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
271 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
272 |
lemma initState_subset_knows: "initState A \<subseteq> knows A evs" |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
273 |
apply (induct_tac evs, simp) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
274 |
apply (blast intro: knows_subset_knows_Cons [THEN subsetD]) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
275 |
done |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
276 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
277 |
|
69505 | 278 |
text\<open>For proving \<open>new_keys_not_used\<close>\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
279 |
lemma keysFor_parts_insert: |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
280 |
"[| K \<in> keysFor (parts (insert X G)); X \<in> synth (analz H) |] |
58860 | 281 |
==> K \<in> keysFor (parts (G \<union> H)) | Key (invKey K) \<in> parts H" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
282 |
by (force |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
283 |
dest!: parts_insert_subset_Un [THEN keysFor_mono, THEN [2] rev_subsetD] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
284 |
analz_subset_parts [THEN keysFor_mono, THEN [2] rev_subsetD] |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
285 |
intro: analz_subset_parts [THEN subsetD] parts_mono [THEN [2] rev_subsetD]) |
11250 | 286 |
|
67406 | 287 |
method_setup analz_mono_contra = \<open> |
288 |
Scan.succeed (fn ctxt => SIMPLE_METHOD (REPEAT_FIRST (analz_mono_contra_tac ctxt)))\<close> |
|
67613 | 289 |
"for proving theorems of the form X \<notin> analz (knows Spy evs) \<longrightarrow> P" |
11250 | 290 |
|
67406 | 291 |
subsubsection\<open>Useful for case analysis on whether a hash is a spoof or not\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
292 |
|
55142 | 293 |
lemmas syan_impI = impI [where P = "Y \<notin> synth (analz (knows Spy evs))"] for Y evs |
27225 | 294 |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
295 |
ML |
67406 | 296 |
\<open> |
39282 | 297 |
val knows_Cons = @{thm knows_Cons}; |
298 |
val used_Nil = @{thm used_Nil}; |
|
299 |
val used_Cons = @{thm used_Cons}; |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
300 |
|
39282 | 301 |
val Notes_imp_used = @{thm Notes_imp_used}; |
302 |
val Says_imp_used = @{thm Says_imp_used}; |
|
303 |
val Says_imp_knows_Spy = @{thm Says_imp_knows_Spy}; |
|
304 |
val Notes_imp_knows_Spy = @{thm Notes_imp_knows_Spy}; |
|
305 |
val knows_Spy_partsEs = @{thms knows_Spy_partsEs}; |
|
306 |
val spies_partsEs = @{thms spies_partsEs}; |
|
307 |
val Says_imp_spies = @{thm Says_imp_spies}; |
|
308 |
val parts_insert_spies = @{thm parts_insert_spies}; |
|
309 |
val Says_imp_knows = @{thm Says_imp_knows}; |
|
310 |
val Notes_imp_knows = @{thm Notes_imp_knows}; |
|
311 |
val Gets_imp_knows_agents = @{thm Gets_imp_knows_agents}; |
|
312 |
val knows_imp_Says_Gets_Notes_initState = @{thm knows_imp_Says_Gets_Notes_initState}; |
|
313 |
val knows_Spy_imp_Says_Notes_initState = @{thm knows_Spy_imp_Says_Notes_initState}; |
|
314 |
val usedI = @{thm usedI}; |
|
315 |
val initState_into_used = @{thm initState_into_used}; |
|
316 |
val used_Says = @{thm used_Says}; |
|
317 |
val used_Notes = @{thm used_Notes}; |
|
318 |
val used_Gets = @{thm used_Gets}; |
|
319 |
val used_nil_subset = @{thm used_nil_subset}; |
|
320 |
val analz_mono_contra = @{thms analz_mono_contra}; |
|
321 |
val knows_subset_knows_Cons = @{thm knows_subset_knows_Cons}; |
|
322 |
val initState_subset_knows = @{thm initState_subset_knows}; |
|
323 |
val keysFor_parts_insert = @{thm keysFor_parts_insert}; |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
324 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
325 |
|
39282 | 326 |
val synth_analz_mono = @{thm synth_analz_mono}; |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
327 |
|
39282 | 328 |
val knows_Spy_subset_knows_Spy_Says = @{thm knows_Spy_subset_knows_Spy_Says}; |
329 |
val knows_Spy_subset_knows_Spy_Notes = @{thm knows_Spy_subset_knows_Spy_Notes}; |
|
330 |
val knows_Spy_subset_knows_Spy_Gets = @{thm knows_Spy_subset_knows_Spy_Gets}; |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
331 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
332 |
|
58963
26bf09b95dda
proper context for assume_tac (atac remains as fall-back without context);
wenzelm
parents:
58889
diff
changeset
|
333 |
fun synth_analz_mono_contra_tac ctxt = |
60754 | 334 |
resolve_tac ctxt @{thms syan_impI} THEN' |
27225 | 335 |
REPEAT1 o |
59498
50b60f501b05
proper context for resolve_tac, eresolve_tac, dresolve_tac, forward_tac etc.;
wenzelm
parents:
58963
diff
changeset
|
336 |
(dresolve_tac ctxt |
27225 | 337 |
[@{thm knows_Spy_subset_knows_Spy_Says} RS @{thm synth_analz_mono} RS @{thm contra_subsetD}, |
338 |
@{thm knows_Spy_subset_knows_Spy_Notes} RS @{thm synth_analz_mono} RS @{thm contra_subsetD}, |
|
339 |
@{thm knows_Spy_subset_knows_Spy_Gets} RS @{thm synth_analz_mono} RS @{thm contra_subsetD}]) |
|
340 |
THEN' |
|
58963
26bf09b95dda
proper context for assume_tac (atac remains as fall-back without context);
wenzelm
parents:
58889
diff
changeset
|
341 |
mp_tac ctxt |
67406 | 342 |
\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
343 |
|
67406 | 344 |
method_setup synth_analz_mono_contra = \<open> |
345 |
Scan.succeed (fn ctxt => SIMPLE_METHOD (REPEAT_FIRST (synth_analz_mono_contra_tac ctxt)))\<close> |
|
67613 | 346 |
"for proving theorems of the form X \<notin> synth (analz (knows Spy evs)) \<longrightarrow> P" |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
347 |
(*>*) |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
348 |
|
67406 | 349 |
section\<open>Event Traces \label{sec:events}\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
350 |
|
67406 | 351 |
text \<open> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
352 |
The system's behaviour is formalized as a set of traces of |
69505 | 353 |
\emph{events}. The most important event, \<open>Says A B X\<close>, expresses |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
354 |
$A\to B : X$, which is the attempt by~$A$ to send~$B$ the message~$X$. |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
355 |
A trace is simply a list, constructed in reverse |
69505 | 356 |
using~\<open>#\<close>. Other event types include reception of messages (when |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
357 |
we want to make it explicit) and an agent's storing a fact. |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
358 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
359 |
Sometimes the protocol requires an agent to generate a new nonce. The |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
360 |
probability that a 20-byte random number has appeared before is effectively |
69597 | 361 |
zero. To formalize this important property, the set \<^term>\<open>used evs\<close> |
69505 | 362 |
denotes the set of all items mentioned in the trace~\<open>evs\<close>. |
363 |
The function \<open>used\<close> has a straightforward |
|
364 |
recursive definition. Here is the case for \<open>Says\<close> event: |
|
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
365 |
@{thm [display,indent=5] used_Says [no_vars]} |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
366 |
|
69505 | 367 |
The function \<open>knows\<close> formalizes an agent's knowledge. Mostly we only |
69597 | 368 |
care about the spy's knowledge, and \<^term>\<open>knows Spy evs\<close> is the set of items |
69505 | 369 |
available to the spy in the trace~\<open>evs\<close>. Already in the empty trace, |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
370 |
the spy starts with some secrets at his disposal, such as the private keys |
69505 | 371 |
of compromised users. After each \<open>Says\<close> event, the spy learns the |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
372 |
message that was sent: |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
373 |
@{thm [display,indent=5] knows_Spy_Says [no_vars]} |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
374 |
Combinations of functions express other important |
69505 | 375 |
sets of messages derived from~\<open>evs\<close>: |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
376 |
\begin{itemize} |
69597 | 377 |
\item \<^term>\<open>analz (knows Spy evs)\<close> is everything that the spy could |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
378 |
learn by decryption |
69597 | 379 |
\item \<^term>\<open>synth (analz (knows Spy evs))\<close> is everything that the spy |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
380 |
could generate |
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
381 |
\end{itemize} |
67406 | 382 |
\<close> |
23925
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
383 |
|
ee98c2528a8f
LaTeX code is now generated directly from theory files.
berghofe
parents:
16417
diff
changeset
|
384 |
(*<*) |
11250 | 385 |
end |
62392 | 386 |
(*>*) |