|
1 (****************************************************************************** |
|
2 date: april 2002 |
|
3 author: Frederic Blanqui |
|
4 email: blanqui@lri.fr |
|
5 webpage: http://www.lri.fr/~blanqui/ |
|
6 |
|
7 University of Cambridge, Computer Laboratory |
|
8 William Gates Building, JJ Thomson Avenue |
|
9 Cambridge CB3 0FD, United Kingdom |
|
10 ******************************************************************************) |
|
11 |
|
12 header{*Other Protocol-Independent Results*} |
|
13 |
|
14 theory Proto = Guard_Public: |
|
15 |
|
16 subsection{*protocols*} |
|
17 |
|
18 types rule = "event set * event" |
|
19 |
|
20 syntax msg' :: "rule => msg" |
|
21 |
|
22 translations "msg' R" == "msg (snd R)" |
|
23 |
|
24 types proto = "rule set" |
|
25 |
|
26 constdefs wdef :: "proto => bool" |
|
27 "wdef p == ALL R k. R:p --> Number k:parts {msg' R} |
|
28 --> Number k:parts (msg`(fst R))" |
|
29 |
|
30 subsection{*substitutions*} |
|
31 |
|
32 record subs = |
|
33 agent :: "agent => agent" |
|
34 nonce :: "nat => nat" |
|
35 nb :: "nat => msg" |
|
36 key :: "key => key" |
|
37 |
|
38 consts apm :: "subs => msg => msg" |
|
39 |
|
40 primrec |
|
41 "apm s (Agent A) = Agent (agent s A)" |
|
42 "apm s (Nonce n) = Nonce (nonce s n)" |
|
43 "apm s (Number n) = nb s n" |
|
44 "apm s (Key K) = Key (key s K)" |
|
45 "apm s (Hash X) = Hash (apm s X)" |
|
46 "apm s (Crypt K X) = ( |
|
47 if (EX A. K = pubK A) then Crypt (pubK (agent s (agt K))) (apm s X) |
|
48 else if (EX A. K = priK A) then Crypt (priK (agent s (agt K))) (apm s X) |
|
49 else Crypt (key s K) (apm s X))" |
|
50 "apm s {|X,Y|} = {|apm s X, apm s Y|}" |
|
51 |
|
52 lemma apm_parts: "X:parts {Y} ==> apm s X:parts {apm s Y}" |
|
53 apply (erule parts.induct, simp_all, blast) |
|
54 apply (erule parts.Fst) |
|
55 apply (erule parts.Snd) |
|
56 by (erule parts.Body)+ |
|
57 |
|
58 lemma Nonce_apm [rule_format]: "Nonce n:parts {apm s X} ==> |
|
59 (ALL k. Number k:parts {X} --> Nonce n ~:parts {nb s k}) --> |
|
60 (EX k. Nonce k:parts {X} & nonce s k = n)" |
|
61 by (induct X, simp_all, blast) |
|
62 |
|
63 lemma wdef_Nonce: "[| Nonce n:parts {apm s X}; R:p; msg' R = X; wdef p; |
|
64 Nonce n ~:parts (apm s `(msg `(fst R))) |] ==> |
|
65 (EX k. Nonce k:parts {X} & nonce s k = n)" |
|
66 apply (erule Nonce_apm, unfold wdef_def) |
|
67 apply (drule_tac x=R in spec, drule_tac x=k in spec, clarsimp) |
|
68 apply (drule_tac x=x in bspec, simp) |
|
69 apply (drule_tac Y="msg x" and s=s in apm_parts, simp) |
|
70 by (blast dest: parts_parts) |
|
71 |
|
72 consts ap :: "subs => event => event" |
|
73 |
|
74 primrec |
|
75 "ap s (Says A B X) = Says (agent s A) (agent s B) (apm s X)" |
|
76 "ap s (Gets A X) = Gets (agent s A) (apm s X)" |
|
77 "ap s (Notes A X) = Notes (agent s A) (apm s X)" |
|
78 |
|
79 syntax |
|
80 ap' :: "rule => msg" |
|
81 apm' :: "rule => msg" |
|
82 priK' :: "subs => agent => key" |
|
83 pubK' :: "subs => agent => key" |
|
84 |
|
85 translations |
|
86 "ap' s R" == "ap s (snd R)" |
|
87 "apm' s R" == "apm s (msg' R)" |
|
88 "priK' s A" == "priK (agent s A)" |
|
89 "pubK' s A" == "pubK (agent s A)" |
|
90 |
|
91 subsection{*nonces generated by a rule*} |
|
92 |
|
93 constdefs newn :: "rule => nat set" |
|
94 "newn R == {n. Nonce n:parts {msg (snd R)} & Nonce n ~:parts (msg`(fst R))}" |
|
95 |
|
96 lemma newn_parts: "n:newn R ==> Nonce (nonce s n):parts {apm' s R}" |
|
97 by (auto simp: newn_def dest: apm_parts) |
|
98 |
|
99 subsection{*traces generated by a protocol*} |
|
100 |
|
101 constdefs ok :: "event list => rule => subs => bool" |
|
102 "ok evs R s == ((ALL x. x:fst R --> ap s x:set evs) |
|
103 & (ALL n. n:newn R --> Nonce (nonce s n) ~:used evs))" |
|
104 |
|
105 consts tr :: "proto => event list set" |
|
106 |
|
107 inductive "tr p" intros |
|
108 |
|
109 Nil [intro]: "[]:tr p" |
|
110 |
|
111 Fake [intro]: "[| evsf:tr p; X:synth (analz (spies evsf)) |] |
|
112 ==> Says Spy B X # evsf:tr p" |
|
113 |
|
114 Proto [intro]: "[| evs:tr p; R:p; ok evs R s |] ==> ap' s R # evs:tr p" |
|
115 |
|
116 subsection{*general properties*} |
|
117 |
|
118 lemma one_step_tr [iff]: "one_step (tr p)" |
|
119 apply (unfold one_step_def, clarify) |
|
120 by (ind_cases "ev # evs:tr p", auto) |
|
121 |
|
122 constdefs has_only_Says' :: "proto => bool" |
|
123 "has_only_Says' p == ALL R. R:p --> is_Says (snd R)" |
|
124 |
|
125 lemma has_only_Says'D: "[| R:p; has_only_Says' p |] |
|
126 ==> (EX A B X. snd R = Says A B X)" |
|
127 by (unfold has_only_Says'_def is_Says_def, blast) |
|
128 |
|
129 lemma has_only_Says_tr [simp]: "has_only_Says' p ==> has_only_Says (tr p)" |
|
130 apply (unfold has_only_Says_def) |
|
131 apply (rule allI, rule allI, rule impI) |
|
132 apply (erule tr.induct) |
|
133 apply (auto simp: has_only_Says'_def ok_def) |
|
134 by (drule_tac x=a in spec, auto simp: is_Says_def) |
|
135 |
|
136 lemma has_only_Says'_in_trD: "[| has_only_Says' p; list @ ev # evs1 \<in> tr p |] |
|
137 ==> (EX A B X. ev = Says A B X)" |
|
138 by (drule has_only_Says_tr, auto) |
|
139 |
|
140 lemma ok_not_used: "[| Nonce n ~:used evs; ok evs R s; |
|
141 ALL x. x:fst R --> is_Says x |] ==> Nonce n ~:parts (apm s `(msg `(fst R)))" |
|
142 apply (unfold ok_def, clarsimp) |
|
143 apply (drule_tac x=x in spec, drule_tac x=x in spec) |
|
144 by (auto simp: is_Says_def dest: Says_imp_spies not_used_not_spied parts_parts) |
|
145 |
|
146 lemma ok_is_Says: "[| evs' @ ev # evs:tr p; ok evs R s; has_only_Says' p; |
|
147 R:p; x:fst R |] ==> is_Says x" |
|
148 apply (unfold ok_def is_Says_def, clarify) |
|
149 apply (drule_tac x=x in spec, simp) |
|
150 apply (subgoal_tac "one_step (tr p)") |
|
151 apply (drule trunc, simp, drule one_step_Cons, simp) |
|
152 apply (drule has_only_SaysD, simp+) |
|
153 by (clarify, case_tac x, auto) |
|
154 |
|
155 subsection{*types*} |
|
156 |
|
157 types keyfun = "rule => subs => nat => event list => key set" |
|
158 |
|
159 types secfun = "rule => nat => subs => key set => msg" |
|
160 |
|
161 subsection{*introduction of a fresh guarded nonce*} |
|
162 |
|
163 constdefs fresh :: "proto => rule => subs => nat => key set => event list |
|
164 => bool" |
|
165 "fresh p R s n Ks evs == (EX evs1 evs2. evs = evs2 @ ap' s R # evs1 |
|
166 & Nonce n ~:used evs1 & R:p & ok evs1 R s & Nonce n:parts {apm' s R} |
|
167 & apm' s R:guard n Ks)" |
|
168 |
|
169 lemma freshD: "fresh p R s n Ks evs ==> (EX evs1 evs2. |
|
170 evs = evs2 @ ap' s R # evs1 & Nonce n ~:used evs1 & R:p & ok evs1 R s |
|
171 & Nonce n:parts {apm' s R} & apm' s R:guard n Ks)" |
|
172 by (unfold fresh_def, blast) |
|
173 |
|
174 lemma freshI [intro]: "[| Nonce n ~:used evs1; R:p; Nonce n:parts {apm' s R}; |
|
175 ok evs1 R s; apm' s R:guard n Ks |] |
|
176 ==> fresh p R s n Ks (list @ ap' s R # evs1)" |
|
177 by (unfold fresh_def, blast) |
|
178 |
|
179 lemma freshI': "[| Nonce n ~:used evs1; (l,r):p; |
|
180 Nonce n:parts {apm s (msg r)}; ok evs1 (l,r) s; apm s (msg r):guard n Ks |] |
|
181 ==> fresh p (l,r) s n Ks (evs2 @ ap s r # evs1)" |
|
182 by (drule freshI, simp+) |
|
183 |
|
184 lemma fresh_used: "[| fresh p R' s' n Ks evs; has_only_Says' p |] |
|
185 ==> Nonce n:used evs" |
|
186 apply (unfold fresh_def, clarify) |
|
187 apply (drule has_only_Says'D) |
|
188 by (auto intro: parts_used_app) |
|
189 |
|
190 lemma fresh_newn: "[| evs' @ ap' s R # evs:tr p; wdef p; has_only_Says' p; |
|
191 Nonce n ~:used evs; R:p; ok evs R s; Nonce n:parts {apm' s R} |] |
|
192 ==> EX k. k:newn R & nonce s k = n" |
|
193 apply (drule wdef_Nonce, simp+) |
|
194 apply (frule ok_not_used, simp+) |
|
195 apply (clarify, erule ok_is_Says, simp+) |
|
196 apply (clarify, rule_tac x=k in exI, simp add: newn_def) |
|
197 apply (clarify, drule_tac Y="msg x" and s=s in apm_parts) |
|
198 apply (drule ok_not_used, simp+) |
|
199 apply (clarify, erule ok_is_Says, simp+) |
|
200 by blast |
|
201 |
|
202 lemma fresh_rule: "[| evs' @ ev # evs:tr p; wdef p; Nonce n ~:used evs; |
|
203 Nonce n:parts {msg ev} |] ==> EX R s. R:p & ap' s R = ev" |
|
204 apply (drule trunc, simp, ind_cases "ev # evs:tr p", simp) |
|
205 by (drule_tac x=X in in_sub, drule parts_sub, simp, simp, blast+) |
|
206 |
|
207 lemma fresh_ruleD: "[| fresh p R' s' n Ks evs; keys R' s' n evs <= Ks; wdef p; |
|
208 has_only_Says' p; evs:tr p; ALL R k s. nonce s k = n --> Nonce n:used evs --> |
|
209 R:p --> k:newn R --> Nonce n:parts {apm' s R} --> apm' s R:guard n Ks --> |
|
210 apm' s R:parts (spies evs) --> keys R s n evs <= Ks --> P |] ==> P" |
|
211 apply (frule fresh_used, simp) |
|
212 apply (unfold fresh_def, clarify) |
|
213 apply (drule_tac x=R' in spec) |
|
214 apply (drule fresh_newn, simp+, clarify) |
|
215 apply (drule_tac x=k in spec) |
|
216 apply (drule_tac x=s' in spec) |
|
217 apply (subgoal_tac "apm' s' R':parts (spies (evs2 @ ap' s' R' # evs1))") |
|
218 apply (case_tac R', drule has_only_Says'D, simp, clarsimp) |
|
219 apply (case_tac R', drule has_only_Says'D, simp, clarsimp) |
|
220 apply (rule_tac Y="apm s' X" in parts_parts, blast) |
|
221 by (rule parts.Inj, rule Says_imp_spies, simp, blast) |
|
222 |
|
223 subsection{*safe keys*} |
|
224 |
|
225 constdefs safe :: "key set => msg set => bool" |
|
226 "safe Ks G == ALL K. K:Ks --> Key K ~:analz G" |
|
227 |
|
228 lemma safeD [dest]: "[| safe Ks G; K:Ks |] ==> Key K ~:analz G" |
|
229 by (unfold safe_def, blast) |
|
230 |
|
231 lemma safe_insert: "safe Ks (insert X G) ==> safe Ks G" |
|
232 by (unfold safe_def, blast) |
|
233 |
|
234 lemma Guard_safe: "[| Guard n Ks G; safe Ks G |] ==> Nonce n ~:analz G" |
|
235 by (blast dest: Guard_invKey) |
|
236 |
|
237 subsection{*guardedness preservation*} |
|
238 |
|
239 constdefs preserv :: "proto => keyfun => nat => key set => bool" |
|
240 "preserv p keys n Ks == (ALL evs R' s' R s. evs:tr p --> |
|
241 Guard n Ks (spies evs) --> safe Ks (spies evs) --> fresh p R' s' n Ks evs --> |
|
242 keys R' s' n evs <= Ks --> R:p --> ok evs R s --> apm' s R:guard n Ks)" |
|
243 |
|
244 lemma preservD: "[| preserv p keys n Ks; evs:tr p; Guard n Ks (spies evs); |
|
245 safe Ks (spies evs); fresh p R' s' n Ks evs; R:p; ok evs R s; |
|
246 keys R' s' n evs <= Ks |] ==> apm' s R:guard n Ks" |
|
247 by (unfold preserv_def, blast) |
|
248 |
|
249 lemma preservD': "[| preserv p keys n Ks; evs:tr p; Guard n Ks (spies evs); |
|
250 safe Ks (spies evs); fresh p R' s' n Ks evs; (l,Says A B X):p; |
|
251 ok evs (l,Says A B X) s; keys R' s' n evs <= Ks |] ==> apm s X:guard n Ks" |
|
252 by (drule preservD, simp+) |
|
253 |
|
254 subsection{*monotonic keyfun*} |
|
255 |
|
256 constdefs monoton :: "proto => keyfun => bool" |
|
257 "monoton p keys == ALL R' s' n ev evs. ev # evs:tr p --> |
|
258 keys R' s' n evs <= keys R' s' n (ev # evs)" |
|
259 |
|
260 lemma monotonD [dest]: "[| keys R' s' n (ev # evs) <= Ks; monoton p keys; |
|
261 ev # evs:tr p |] ==> keys R' s' n evs <= Ks" |
|
262 by (unfold monoton_def, blast) |
|
263 |
|
264 subsection{*guardedness theorem*} |
|
265 |
|
266 lemma Guard_tr [rule_format]: "[| evs:tr p; has_only_Says' p; |
|
267 preserv p keys n Ks; monoton p keys; Guard n Ks (initState Spy) |] ==> |
|
268 safe Ks (spies evs) --> fresh p R' s' n Ks evs --> keys R' s' n evs <= Ks --> |
|
269 Guard n Ks (spies evs)" |
|
270 apply (erule tr.induct) |
|
271 (* Nil *) |
|
272 apply simp |
|
273 (* Fake *) |
|
274 apply (clarify, drule freshD, clarsimp) |
|
275 apply (case_tac evs2) |
|
276 (* evs2 = [] *) |
|
277 apply (frule has_only_Says'D, simp) |
|
278 apply (clarsimp, blast) |
|
279 (* evs2 = aa # list *) |
|
280 apply (clarsimp, rule conjI) |
|
281 apply (blast dest: safe_insert) |
|
282 (* X:guard n Ks *) |
|
283 apply (rule in_synth_Guard, simp, rule Guard_analz) |
|
284 apply (blast dest: safe_insert) |
|
285 apply (drule safe_insert, simp add: safe_def) |
|
286 (* Proto *) |
|
287 apply (clarify, drule freshD, clarify) |
|
288 apply (case_tac evs2) |
|
289 (* evs2 = [] *) |
|
290 apply (frule has_only_Says'D, simp) |
|
291 apply (frule_tac R=R' in has_only_Says'D, simp) |
|
292 apply (case_tac R', clarsimp, blast) |
|
293 (* evs2 = ab # list *) |
|
294 apply (frule has_only_Says'D, simp) |
|
295 apply (clarsimp, rule conjI) |
|
296 apply (drule Proto, simp+, blast dest: safe_insert) |
|
297 (* apm s X:guard n Ks *) |
|
298 apply (frule Proto, simp+) |
|
299 apply (erule preservD', simp+) |
|
300 apply (blast dest: safe_insert) |
|
301 apply (blast dest: safe_insert) |
|
302 by (blast, simp, simp, blast) |
|
303 |
|
304 subsection{*useful properties for guardedness*} |
|
305 |
|
306 lemma newn_neq_used: "[| Nonce n:used evs; ok evs R s; k:newn R |] |
|
307 ==> n ~= nonce s k" |
|
308 by (auto simp: ok_def) |
|
309 |
|
310 lemma ok_Guard: "[| ok evs R s; Guard n Ks (spies evs); x:fst R; is_Says x |] |
|
311 ==> apm s (msg x):parts (spies evs) & apm s (msg x):guard n Ks" |
|
312 apply (unfold ok_def is_Says_def, clarify) |
|
313 apply (drule_tac x="Says A B X" in spec, simp) |
|
314 by (drule Says_imp_spies, auto intro: parts_parts) |
|
315 |
|
316 lemma ok_parts_not_new: "[| Y:parts (spies evs); Nonce (nonce s n):parts {Y}; |
|
317 ok evs R s |] ==> n ~:newn R" |
|
318 by (auto simp: ok_def dest: not_used_not_spied parts_parts) |
|
319 |
|
320 subsection{*unicity*} |
|
321 |
|
322 constdefs uniq :: "proto => secfun => bool" |
|
323 "uniq p secret == ALL evs R R' n n' Ks s s'. R:p --> R':p --> |
|
324 n:newn R --> n':newn R' --> nonce s n = nonce s' n' --> |
|
325 Nonce (nonce s n):parts {apm' s R} --> Nonce (nonce s n):parts {apm' s' R'} --> |
|
326 apm' s R:guard (nonce s n) Ks --> apm' s' R':guard (nonce s n) Ks --> |
|
327 evs:tr p --> Nonce (nonce s n) ~:analz (spies evs) --> |
|
328 secret R n s Ks:parts (spies evs) --> secret R' n' s' Ks:parts (spies evs) --> |
|
329 secret R n s Ks = secret R' n' s' Ks" |
|
330 |
|
331 lemma uniqD: "[| uniq p secret; evs: tr p; R:p; R':p; n:newn R; n':newn R'; |
|
332 nonce s n = nonce s' n'; Nonce (nonce s n) ~:analz (spies evs); |
|
333 Nonce (nonce s n):parts {apm' s R}; Nonce (nonce s n):parts {apm' s' R'}; |
|
334 secret R n s Ks:parts (spies evs); secret R' n' s' Ks:parts (spies evs); |
|
335 apm' s R:guard (nonce s n) Ks; apm' s' R':guard (nonce s n) Ks |] ==> |
|
336 secret R n s Ks = secret R' n' s' Ks" |
|
337 by (unfold uniq_def, blast) |
|
338 |
|
339 constdefs ord :: "proto => (rule => rule => bool) => bool" |
|
340 "ord p inf == ALL R R'. R:p --> R':p --> ~ inf R R' --> inf R' R" |
|
341 |
|
342 lemma ordD: "[| ord p inf; ~ inf R R'; R:p; R':p |] ==> inf R' R" |
|
343 by (unfold ord_def, blast) |
|
344 |
|
345 constdefs uniq' :: "proto => (rule => rule => bool) => secfun => bool" |
|
346 "uniq' p inf secret == ALL evs R R' n n' Ks s s'. R:p --> R':p --> |
|
347 inf R R' --> n:newn R --> n':newn R' --> nonce s n = nonce s' n' --> |
|
348 Nonce (nonce s n):parts {apm' s R} --> Nonce (nonce s n):parts {apm' s' R'} --> |
|
349 apm' s R:guard (nonce s n) Ks --> apm' s' R':guard (nonce s n) Ks --> |
|
350 evs:tr p --> Nonce (nonce s n) ~:analz (spies evs) --> |
|
351 secret R n s Ks:parts (spies evs) --> secret R' n' s' Ks:parts (spies evs) --> |
|
352 secret R n s Ks = secret R' n' s' Ks" |
|
353 |
|
354 lemma uniq'D: "[| uniq' p inf secret; evs: tr p; inf R R'; R:p; R':p; n:newn R; |
|
355 n':newn R'; nonce s n = nonce s' n'; Nonce (nonce s n) ~:analz (spies evs); |
|
356 Nonce (nonce s n):parts {apm' s R}; Nonce (nonce s n):parts {apm' s' R'}; |
|
357 secret R n s Ks:parts (spies evs); secret R' n' s' Ks:parts (spies evs); |
|
358 apm' s R:guard (nonce s n) Ks; apm' s' R':guard (nonce s n) Ks |] ==> |
|
359 secret R n s Ks = secret R' n' s' Ks" |
|
360 by (unfold uniq'_def, blast) |
|
361 |
|
362 lemma uniq'_imp_uniq: "[| uniq' p inf secret; ord p inf |] ==> uniq p secret" |
|
363 apply (unfold uniq_def) |
|
364 apply (rule allI)+ |
|
365 apply (case_tac "inf R R'") |
|
366 apply (blast dest: uniq'D) |
|
367 by (auto dest: ordD uniq'D intro: sym) |
|
368 |
|
369 subsection{*Needham-Schroeder-Lowe*} |
|
370 |
|
371 constdefs |
|
372 a :: agent "a == Friend 0" |
|
373 b :: agent "b == Friend 1" |
|
374 a' :: agent "a' == Friend 2" |
|
375 b' :: agent "b' == Friend 3" |
|
376 Na :: nat "Na == 0" |
|
377 Nb :: nat "Nb == 1" |
|
378 |
|
379 consts |
|
380 ns :: proto |
|
381 ns1 :: rule |
|
382 ns2 :: rule |
|
383 ns3 :: rule |
|
384 |
|
385 translations |
|
386 "ns1" == "({}, Says a b (Crypt (pubK b) {|Nonce Na, Agent a|}))" |
|
387 |
|
388 "ns2" == "({Says a' b (Crypt (pubK b) {|Nonce Na, Agent a|})}, |
|
389 Says b a (Crypt (pubK a) {|Nonce Na, Nonce Nb, Agent b|}))" |
|
390 |
|
391 "ns3" == "({Says a b (Crypt (pubK b) {|Nonce Na, Agent a|}), |
|
392 Says b' a (Crypt (pubK a) {|Nonce Na, Nonce Nb, Agent b|})}, |
|
393 Says a b (Crypt (pubK b) (Nonce Nb)))" |
|
394 |
|
395 inductive ns intros |
|
396 [iff]: "ns1:ns" |
|
397 [iff]: "ns2:ns" |
|
398 [iff]: "ns3:ns" |
|
399 |
|
400 syntax |
|
401 ns3a :: msg |
|
402 ns3b :: msg |
|
403 |
|
404 translations |
|
405 "ns3a" => "Says a b (Crypt (pubK b) {|Nonce Na, Agent a|})" |
|
406 "ns3b" => "Says b' a (Crypt (pubK a) {|Nonce Na, Nonce Nb, Agent b|})" |
|
407 |
|
408 constdefs keys :: "keyfun" |
|
409 "keys R' s' n evs == {priK' s' a, priK' s' b}" |
|
410 |
|
411 lemma "monoton ns keys" |
|
412 by (simp add: keys_def monoton_def) |
|
413 |
|
414 constdefs secret :: "secfun" |
|
415 "secret R n s Ks == |
|
416 (if R=ns1 then apm s (Crypt (pubK b) {|Nonce Na, Agent a|}) |
|
417 else if R=ns2 then apm s (Crypt (pubK a) {|Nonce Na, Nonce Nb, Agent b|}) |
|
418 else Number 0)" |
|
419 |
|
420 constdefs inf :: "rule => rule => bool" |
|
421 "inf R R' == (R=ns1 | (R=ns2 & R'~=ns1) | (R=ns3 & R'=ns3))" |
|
422 |
|
423 lemma inf_is_ord [iff]: "ord ns inf" |
|
424 apply (unfold ord_def inf_def) |
|
425 apply (rule allI)+ |
|
426 by (rule impI, erule ns.cases, simp_all)+ |
|
427 |
|
428 subsection{*general properties*} |
|
429 |
|
430 lemma ns_has_only_Says' [iff]: "has_only_Says' ns" |
|
431 apply (unfold has_only_Says'_def) |
|
432 apply (rule allI, rule impI) |
|
433 by (erule ns.cases, auto) |
|
434 |
|
435 lemma newn_ns1 [iff]: "newn ns1 = {Na}" |
|
436 by (simp add: newn_def) |
|
437 |
|
438 lemma newn_ns2 [iff]: "newn ns2 = {Nb}" |
|
439 by (auto simp: newn_def Na_def Nb_def) |
|
440 |
|
441 lemma newn_ns3 [iff]: "newn ns3 = {}" |
|
442 by (auto simp: newn_def) |
|
443 |
|
444 lemma ns_wdef [iff]: "wdef ns" |
|
445 by (auto simp: wdef_def elim: ns.cases) |
|
446 |
|
447 subsection{*guardedness for NSL*} |
|
448 |
|
449 lemma "uniq ns secret ==> preserv ns keys n Ks" |
|
450 apply (unfold preserv_def) |
|
451 apply (rule allI)+ |
|
452 apply (rule impI, rule impI, rule impI, rule impI, rule impI) |
|
453 apply (erule fresh_ruleD, simp, simp, simp, simp) |
|
454 apply (rule allI)+ |
|
455 apply (rule impI, rule impI, rule impI) |
|
456 apply (erule ns.cases) |
|
457 (* fresh with NS1 *) |
|
458 apply (rule impI, rule impI, rule impI, rule impI, rule impI, rule impI) |
|
459 apply (erule ns.cases) |
|
460 (* NS1 *) |
|
461 apply clarsimp |
|
462 apply (frule newn_neq_used, simp, simp) |
|
463 apply (rule No_Nonce, simp) |
|
464 (* NS2 *) |
|
465 apply clarsimp |
|
466 apply (frule newn_neq_used, simp, simp) |
|
467 apply (case_tac "nonce sa Na = nonce s Na") |
|
468 apply (frule Guard_safe, simp) |
|
469 apply (frule Crypt_guard_invKey, simp) |
|
470 apply (frule ok_Guard, simp, simp, simp, clarsimp) |
|
471 apply (frule_tac K="pubK' s b" in Crypt_guard_invKey, simp) |
|
472 apply (frule_tac R=ns1 and R'=ns1 and Ks=Ks and s=sa and s'=s in uniqD, simp+) |
|
473 apply (simp add: secret_def, simp add: secret_def, force, force) |
|
474 apply (simp add: secret_def keys_def, blast) |
|
475 apply (rule No_Nonce, simp) |
|
476 (* NS3 *) |
|
477 apply clarsimp |
|
478 apply (case_tac "nonce sa Na = nonce s Nb") |
|
479 apply (frule Guard_safe, simp) |
|
480 apply (frule Crypt_guard_invKey, simp) |
|
481 apply (frule_tac x=ns3b in ok_Guard, simp, simp, simp, clarsimp) |
|
482 apply (frule_tac K="pubK' s a" in Crypt_guard_invKey, simp) |
|
483 apply (frule_tac R=ns1 and R'=ns2 and Ks=Ks and s=sa and s'=s in uniqD, simp+) |
|
484 apply (simp add: secret_def, simp add: secret_def, force, force) |
|
485 apply (simp add: secret_def, rule No_Nonce, simp) |
|
486 (* fresh with NS2 *) |
|
487 apply (rule impI, rule impI, rule impI, rule impI, rule impI, rule impI) |
|
488 apply (erule ns.cases) |
|
489 (* NS1 *) |
|
490 apply clarsimp |
|
491 apply (frule newn_neq_used, simp, simp) |
|
492 apply (rule No_Nonce, simp) |
|
493 (* NS2 *) |
|
494 apply clarsimp |
|
495 apply (frule newn_neq_used, simp, simp) |
|
496 apply (case_tac "nonce sa Nb = nonce s Na") |
|
497 apply (frule Guard_safe, simp) |
|
498 apply (frule Crypt_guard_invKey, simp) |
|
499 apply (frule ok_Guard, simp, simp, simp, clarsimp) |
|
500 apply (frule_tac K="pubK' s b" in Crypt_guard_invKey, simp) |
|
501 apply (frule_tac R=ns2 and R'=ns1 and Ks=Ks and s=sa and s'=s in uniqD, simp+) |
|
502 apply (simp add: secret_def, simp add: secret_def, force, force) |
|
503 apply (simp add: secret_def, rule No_Nonce, simp) |
|
504 (* NS3 *) |
|
505 apply clarsimp |
|
506 apply (case_tac "nonce sa Nb = nonce s Nb") |
|
507 apply (frule Guard_safe, simp) |
|
508 apply (frule Crypt_guard_invKey, simp) |
|
509 apply (frule_tac x=ns3b in ok_Guard, simp, simp, simp, clarsimp) |
|
510 apply (frule_tac K="pubK' s a" in Crypt_guard_invKey, simp) |
|
511 apply (frule_tac R=ns2 and R'=ns2 and Ks=Ks and s=sa and s'=s in uniqD, simp+) |
|
512 apply (simp add: secret_def, simp add: secret_def, force, force) |
|
513 apply (simp add: secret_def keys_def, blast) |
|
514 apply (rule No_Nonce, simp) |
|
515 (* fresh with NS3 *) |
|
516 by simp |
|
517 |
|
518 subsection{*unicity for NSL*} |
|
519 |
|
520 lemma "uniq' ns inf secret" |
|
521 apply (unfold uniq'_def) |
|
522 apply (rule allI)+ |
|
523 apply (rule impI, erule ns.cases) |
|
524 (* R = ns1 *) |
|
525 apply (rule impI, erule ns.cases) |
|
526 (* R' = ns1 *) |
|
527 apply (rule impI, rule impI, rule impI, rule impI) |
|
528 apply (rule impI, rule impI, rule impI, rule impI) |
|
529 apply (rule impI, erule tr.induct) |
|
530 (* Nil *) |
|
531 apply (simp add: secret_def) |
|
532 (* Fake *) |
|
533 apply (clarify, simp add: secret_def) |
|
534 apply (drule notin_analz_insert) |
|
535 apply (drule Crypt_insert_synth, simp, simp, simp) |
|
536 apply (drule Crypt_insert_synth, simp, simp, simp, simp) |
|
537 (* Proto *) |
|
538 apply (erule_tac P="ok evsa Ra sa" in rev_mp) |
|
539 apply (erule ns.cases) |
|
540 (* ns1 *) |
|
541 apply (clarify, simp add: secret_def) |
|
542 apply (erule disjE, erule disjE, clarsimp) |
|
543 apply (drule ok_parts_not_new, simp, simp, simp) |
|
544 apply (clarify, drule ok_parts_not_new, simp, simp, simp) |
|
545 (* ns2 *) |
|
546 apply (simp add: secret_def) |
|
547 (* ns3 *) |
|
548 apply (simp add: secret_def) |
|
549 (* R' = ns2 *) |
|
550 apply (rule impI, rule impI, rule impI, rule impI) |
|
551 apply (rule impI, rule impI, rule impI, rule impI) |
|
552 apply (rule impI, erule tr.induct) |
|
553 (* Nil *) |
|
554 apply (simp add: secret_def) |
|
555 (* Fake *) |
|
556 apply (clarify, simp add: secret_def) |
|
557 apply (drule notin_analz_insert) |
|
558 apply (drule Crypt_insert_synth, simp, simp, simp) |
|
559 apply (drule_tac n="nonce s' Nb" in Crypt_insert_synth, simp, simp, simp, simp) |
|
560 (* Proto *) |
|
561 apply (erule_tac P="ok evsa Ra sa" in rev_mp) |
|
562 apply (erule ns.cases) |
|
563 (* ns1 *) |
|
564 apply (clarify, simp add: secret_def) |
|
565 apply (drule_tac s=sa and n=Na in ok_parts_not_new, simp, simp, simp) |
|
566 (* ns2 *) |
|
567 apply (clarify, simp add: secret_def) |
|
568 apply (drule_tac s=sa and n=Nb in ok_parts_not_new, simp, simp, simp) |
|
569 (* ns3 *) |
|
570 apply (simp add: secret_def) |
|
571 (* R' = ns3 *) |
|
572 apply simp |
|
573 (* R = ns2 *) |
|
574 apply (rule impI, erule ns.cases) |
|
575 (* R' = ns1 *) |
|
576 apply (simp only: inf_def, blast) |
|
577 (* R' = ns2 *) |
|
578 apply (rule impI, rule impI, rule impI, rule impI) |
|
579 apply (rule impI, rule impI, rule impI, rule impI) |
|
580 apply (rule impI, erule tr.induct) |
|
581 (* Nil *) |
|
582 apply (simp add: secret_def) |
|
583 (* Fake *) |
|
584 apply (clarify, simp add: secret_def) |
|
585 apply (drule notin_analz_insert) |
|
586 apply (drule_tac n="nonce s' Nb" in Crypt_insert_synth, simp, simp, simp) |
|
587 apply (drule_tac n="nonce s' Nb" in Crypt_insert_synth, simp, simp, simp, simp) |
|
588 (* Proto *) |
|
589 apply (erule_tac P="ok evsa Ra sa" in rev_mp) |
|
590 apply (erule ns.cases) |
|
591 (* ns1 *) |
|
592 apply (simp add: secret_def) |
|
593 (* ns2 *) |
|
594 apply (clarify, simp add: secret_def) |
|
595 apply (erule disjE, erule disjE, clarsimp, clarsimp) |
|
596 apply (drule_tac s=sa and n=Nb in ok_parts_not_new, simp, simp, simp) |
|
597 apply (erule disjE, clarsimp) |
|
598 apply (drule_tac s=sa and n=Nb in ok_parts_not_new, simp, simp, simp) |
|
599 by (simp_all add: secret_def) |
|
600 |
|
601 end |