43 (** For reasoning about the encrypted portion of messages **) |
43 (** For reasoning about the encrypted portion of messages **) |
44 |
44 |
45 (*Lets us treat YM4 using a similar argument as for the Fake case.*) |
45 (*Lets us treat YM4 using a similar argument as for the Fake case.*) |
46 goal thy "!!evs. Says S A {|NB, Crypt (shrK A) Y, X|} : set evs ==> \ |
46 goal thy "!!evs. Says S A {|NB, Crypt (shrK A) Y, X|} : set evs ==> \ |
47 \ X : analz (spies evs)"; |
47 \ X : analz (spies evs)"; |
48 by (blast_tac (!claset addSDs [Says_imp_spies RS analz.Inj]) 1); |
48 by (blast_tac (claset() addSDs [Says_imp_spies RS analz.Inj]) 1); |
49 qed "YM4_analz_spies"; |
49 qed "YM4_analz_spies"; |
50 |
50 |
51 bind_thm ("YM4_parts_spies", |
51 bind_thm ("YM4_parts_spies", |
52 YM4_analz_spies RS (impOfSubs analz_subset_parts)); |
52 YM4_analz_spies RS (impOfSubs analz_subset_parts)); |
53 |
53 |
54 (*Relates to both YM4 and Oops*) |
54 (*Relates to both YM4 and Oops*) |
55 goal thy "!!evs. Says S A {|NB, Crypt (shrK A) {|B,K,NA|}, X|} : set evs ==> \ |
55 goal thy "!!evs. Says S A {|NB, Crypt (shrK A) {|B,K,NA|}, X|} : set evs ==> \ |
56 \ K : parts (spies evs)"; |
56 \ K : parts (spies evs)"; |
57 by (blast_tac (!claset addSEs partsEs |
57 by (blast_tac (claset() addSEs partsEs |
58 addSDs [Says_imp_spies RS parts.Inj]) 1); |
58 addSDs [Says_imp_spies RS parts.Inj]) 1); |
59 qed "YM4_Key_parts_spies"; |
59 qed "YM4_Key_parts_spies"; |
60 |
60 |
61 (*For proving the easier theorems about X ~: parts (spies evs).*) |
61 (*For proving the easier theorems about X ~: parts (spies evs).*) |
62 fun parts_spies_tac i = |
62 fun parts_spies_tac i = |
86 qed "Spy_see_shrK"; |
86 qed "Spy_see_shrK"; |
87 Addsimps [Spy_see_shrK]; |
87 Addsimps [Spy_see_shrK]; |
88 |
88 |
89 goal thy |
89 goal thy |
90 "!!evs. evs : yahalom ==> (Key (shrK A) : analz (spies evs)) = (A : bad)"; |
90 "!!evs. evs : yahalom ==> (Key (shrK A) : analz (spies evs)) = (A : bad)"; |
91 by (auto_tac(!claset addDs [impOfSubs analz_subset_parts], !simpset)); |
91 by (auto_tac(claset() addDs [impOfSubs analz_subset_parts], simpset())); |
92 qed "Spy_analz_shrK"; |
92 qed "Spy_analz_shrK"; |
93 Addsimps [Spy_analz_shrK]; |
93 Addsimps [Spy_analz_shrK]; |
94 |
94 |
95 goal thy "!!A. [| Key (shrK A) : parts (spies evs); \ |
95 goal thy "!!A. [| Key (shrK A) : parts (spies evs); \ |
96 \ evs : yahalom |] ==> A:bad"; |
96 \ evs : yahalom |] ==> A:bad"; |
97 by (blast_tac (!claset addDs [Spy_see_shrK]) 1); |
97 by (blast_tac (claset() addDs [Spy_see_shrK]) 1); |
98 qed "Spy_see_shrK_D"; |
98 qed "Spy_see_shrK_D"; |
99 |
99 |
100 bind_thm ("Spy_analz_shrK_D", analz_subset_parts RS subsetD RS Spy_see_shrK_D); |
100 bind_thm ("Spy_analz_shrK_D", analz_subset_parts RS subsetD RS Spy_see_shrK_D); |
101 AddSDs [Spy_see_shrK_D, Spy_analz_shrK_D]; |
101 AddSDs [Spy_see_shrK_D, Spy_analz_shrK_D]; |
102 |
102 |
104 (*Nobody can have used non-existent keys! Needed to apply analz_insert_Key*) |
104 (*Nobody can have used non-existent keys! Needed to apply analz_insert_Key*) |
105 goal thy "!!evs. evs : yahalom ==> \ |
105 goal thy "!!evs. evs : yahalom ==> \ |
106 \ Key K ~: used evs --> K ~: keysFor (parts (spies evs))"; |
106 \ Key K ~: used evs --> K ~: keysFor (parts (spies evs))"; |
107 by (parts_induct_tac 1); |
107 by (parts_induct_tac 1); |
108 (*YM4: Key K is not fresh!*) |
108 (*YM4: Key K is not fresh!*) |
109 by (blast_tac (!claset addSEs spies_partsEs) 3); |
109 by (blast_tac (claset() addSEs spies_partsEs) 3); |
110 (*YM3*) |
110 (*YM3*) |
111 by (blast_tac (!claset addss (!simpset)) 2); |
111 by (blast_tac (claset() addss (simpset())) 2); |
112 (*Fake*) |
112 (*Fake*) |
113 by (best_tac |
113 by (best_tac |
114 (!claset addSDs [impOfSubs (parts_insert_subset_Un RS keysFor_mono)] |
114 (claset() addSDs [impOfSubs (parts_insert_subset_Un RS keysFor_mono)] |
115 addIs [impOfSubs analz_subset_parts] |
115 addIs [impOfSubs analz_subset_parts] |
116 addDs [impOfSubs (analz_subset_parts RS keysFor_mono)] |
116 addDs [impOfSubs (analz_subset_parts RS keysFor_mono)] |
117 addss (!simpset)) 1); |
117 addss (simpset())) 1); |
118 qed_spec_mp "new_keys_not_used"; |
118 qed_spec_mp "new_keys_not_used"; |
119 |
119 |
120 bind_thm ("new_keys_not_analzd", |
120 bind_thm ("new_keys_not_analzd", |
121 [analz_subset_parts RS keysFor_mono, |
121 [analz_subset_parts RS keysFor_mono, |
122 new_keys_not_used] MRS contra_subsetD); |
122 new_keys_not_used] MRS contra_subsetD); |
187 \ EX A' B' na' nb' X'. ALL A B na nb X. \ |
187 \ EX A' B' na' nb' X'. ALL A B na nb X. \ |
188 \ Says Server A \ |
188 \ Says Server A \ |
189 \ {|nb, Crypt (shrK A) {|Agent B, Key K, na|}, X|} \ |
189 \ {|nb, Crypt (shrK A) {|Agent B, Key K, na|}, X|} \ |
190 \ : set evs --> A=A' & B=B' & na=na' & nb=nb' & X=X'"; |
190 \ : set evs --> A=A' & B=B' & na=na' & nb=nb' & X=X'"; |
191 by (etac yahalom.induct 1); |
191 by (etac yahalom.induct 1); |
192 by (ALLGOALS (asm_simp_tac (!simpset addsimps [all_conj_distrib]))); |
192 by (ALLGOALS (asm_simp_tac (simpset() addsimps [all_conj_distrib]))); |
193 by (Clarify_tac 1); |
193 by (Clarify_tac 1); |
194 (*Remaining case: YM3*) |
194 (*Remaining case: YM3*) |
195 by (expand_case_tac "K = ?y" 1); |
195 by (expand_case_tac "K = ?y" 1); |
196 by (REPEAT (ares_tac [refl,exI,impI,conjI] 2)); |
196 by (REPEAT (ares_tac [refl,exI,impI,conjI] 2)); |
197 (*...we assume X is a recent message and handle this case by contradiction*) |
197 (*...we assume X is a recent message and handle this case by contradiction*) |
198 by (blast_tac (!claset addSEs spies_partsEs |
198 by (blast_tac (claset() addSEs spies_partsEs |
199 delrules [conjI] (*prevent split-up into 4 subgoals*) |
199 delrules [conjI] (*prevent split-up into 4 subgoals*) |
200 addss (!simpset addsimps [parts_insertI])) 1); |
200 addss (simpset() addsimps [parts_insertI])) 1); |
201 val lemma = result(); |
201 val lemma = result(); |
202 |
202 |
203 goal thy |
203 goal thy |
204 "!!evs. [| Says Server A \ |
204 "!!evs. [| Says Server A \ |
205 \ {|nb, Crypt (shrK A) {|Agent B, Key K, na|}, X|} : set evs; \ |
205 \ {|nb, Crypt (shrK A) {|Agent B, Key K, na|}, X|} : set evs; \ |
224 \ Key K ~: analz (spies evs)"; |
224 \ Key K ~: analz (spies evs)"; |
225 by (etac yahalom.induct 1); |
225 by (etac yahalom.induct 1); |
226 by analz_spies_tac; |
226 by analz_spies_tac; |
227 by (ALLGOALS |
227 by (ALLGOALS |
228 (asm_simp_tac |
228 (asm_simp_tac |
229 (!simpset addsimps expand_ifs |
229 (simpset() addsimps expand_ifs |
230 addsimps [analz_insert_eq, analz_insert_freshK] |
230 addsimps [analz_insert_eq, analz_insert_freshK] |
231 addsplits [expand_if]))); |
231 addsplits [expand_if]))); |
232 (*Oops*) |
232 (*Oops*) |
233 by (blast_tac (!claset addDs [unique_session_keys]) 3); |
233 by (blast_tac (claset() addDs [unique_session_keys]) 3); |
234 (*YM3*) |
234 (*YM3*) |
235 by (blast_tac (!claset delrules [impCE] |
235 by (blast_tac (claset() delrules [impCE] |
236 addSEs spies_partsEs |
236 addSEs spies_partsEs |
237 addIs [impOfSubs analz_subset_parts]) 2); |
237 addIs [impOfSubs analz_subset_parts]) 2); |
238 (*Fake*) |
238 (*Fake*) |
239 by (spy_analz_tac 1); |
239 by (spy_analz_tac 1); |
240 val lemma = result() RS mp RS mp RSN(2,rev_notE); |
240 val lemma = result() RS mp RS mp RSN(2,rev_notE); |
248 \ : set evs; \ |
248 \ : set evs; \ |
249 \ Says A Spy {|na, nb, Key K|} ~: set evs; \ |
249 \ Says A Spy {|na, nb, Key K|} ~: set evs; \ |
250 \ A ~: bad; B ~: bad; evs : yahalom |] \ |
250 \ A ~: bad; B ~: bad; evs : yahalom |] \ |
251 \ ==> Key K ~: analz (spies evs)"; |
251 \ ==> Key K ~: analz (spies evs)"; |
252 by (forward_tac [Says_Server_message_form] 1 THEN assume_tac 1); |
252 by (forward_tac [Says_Server_message_form] 1 THEN assume_tac 1); |
253 by (blast_tac (!claset addSEs [lemma]) 1); |
253 by (blast_tac (claset() addSEs [lemma]) 1); |
254 qed "Spy_not_see_encrypted_key"; |
254 qed "Spy_not_see_encrypted_key"; |
255 |
255 |
256 |
256 |
257 (** Security Guarantee for A upon receiving YM3 **) |
257 (** Security Guarantee for A upon receiving YM3 **) |
258 |
258 |
306 \ {|Nonce NB, \ |
306 \ {|Nonce NB, \ |
307 \ Crypt (shrK A) {|Agent B, Key K, Nonce NA|}, \ |
307 \ Crypt (shrK A) {|Agent B, Key K, Nonce NA|}, \ |
308 \ Crypt (shrK B) {|Nonce NB, Key K, Agent A|}|} \ |
308 \ Crypt (shrK B) {|Nonce NB, Key K, Agent A|}|} \ |
309 \ : set evs"; |
309 \ : set evs"; |
310 by (etac (Says_imp_spies RS parts.Inj RS MPair_parts) 1); |
310 by (etac (Says_imp_spies RS parts.Inj RS MPair_parts) 1); |
311 by (blast_tac (!claset addSDs [B_trusts_YM4_shrK]) 1); |
311 by (blast_tac (claset() addSDs [B_trusts_YM4_shrK]) 1); |
312 qed "B_trusts_YM4"; |
312 qed "B_trusts_YM4"; |
313 |
313 |
314 |
314 |
315 |
315 |
316 (*** Authenticating B to A ***) |
316 (*** Authenticating B to A ***) |
339 \ Crypt (shrK B) {|Agent A, Nonce NA|}|} \ |
339 \ Crypt (shrK B) {|Agent A, Nonce NA|}|} \ |
340 \ : set evs)"; |
340 \ : set evs)"; |
341 by (etac yahalom.induct 1); |
341 by (etac yahalom.induct 1); |
342 by (ALLGOALS Asm_simp_tac); |
342 by (ALLGOALS Asm_simp_tac); |
343 (*YM3*) |
343 (*YM3*) |
344 by (blast_tac (!claset addSDs [B_Said_YM2] |
344 by (blast_tac (claset() addSDs [B_Said_YM2] |
345 addSEs [MPair_parts] |
345 addSEs [MPair_parts] |
346 addDs [Says_imp_spies RS parts.Inj]) 3); |
346 addDs [Says_imp_spies RS parts.Inj]) 3); |
347 (*Fake, YM2*) |
347 (*Fake, YM2*) |
348 by (ALLGOALS Blast_tac); |
348 by (ALLGOALS Blast_tac); |
349 val lemma = result() RSN (2, rev_mp) RS mp |> standard; |
349 val lemma = result() RSN (2, rev_mp) RS mp |> standard; |
354 \ : set evs; \ |
354 \ : set evs; \ |
355 \ A ~: bad; B ~: bad; evs : yahalom |] \ |
355 \ A ~: bad; B ~: bad; evs : yahalom |] \ |
356 \ ==> EX nb'. Says B Server \ |
356 \ ==> EX nb'. Says B Server \ |
357 \ {|Agent B, nb', Crypt (shrK B) {|Agent A, Nonce NA|}|} \ |
357 \ {|Agent B, nb', Crypt (shrK B) {|Agent A, Nonce NA|}|} \ |
358 \ : set evs"; |
358 \ : set evs"; |
359 by (blast_tac (!claset addSDs [A_trusts_YM3, lemma] |
359 by (blast_tac (claset() addSDs [A_trusts_YM3, lemma] |
360 addEs spies_partsEs) 1); |
360 addEs spies_partsEs) 1); |
361 qed "YM3_auth_B_to_A"; |
361 qed "YM3_auth_B_to_A"; |
362 |
362 |
363 |
363 |
364 (*** Authenticating A to B using the certificate Crypt K (Nonce NB) ***) |
364 (*** Authenticating A to B using the certificate Crypt K (Nonce NB) ***) |
376 \ (EX X. Says A B {|X, Crypt K (Nonce NB)|} : set evs)"; |
376 \ (EX X. Says A B {|X, Crypt K (Nonce NB)|} : set evs)"; |
377 by (parts_induct_tac 1); |
377 by (parts_induct_tac 1); |
378 (*Fake*) |
378 (*Fake*) |
379 by (Fake_parts_insert_tac 1); |
379 by (Fake_parts_insert_tac 1); |
380 (*YM3: by new_keys_not_used we note that Crypt K (Nonce NB) could not exist*) |
380 (*YM3: by new_keys_not_used we note that Crypt K (Nonce NB) could not exist*) |
381 by (fast_tac (!claset addSDs [Crypt_imp_invKey_keysFor] addss (!simpset)) 1); |
381 by (fast_tac (claset() addSDs [Crypt_imp_invKey_keysFor] addss (simpset())) 1); |
382 (*YM4: was Crypt K (Nonce NB) the very last message? If not, use ind. hyp.*) |
382 (*YM4: was Crypt K (Nonce NB) the very last message? If not, use ind. hyp.*) |
383 by (asm_simp_tac (!simpset addsimps [ex_disj_distrib]) 1); |
383 by (asm_simp_tac (simpset() addsimps [ex_disj_distrib]) 1); |
384 (*yes: apply unicity of session keys*) |
384 (*yes: apply unicity of session keys*) |
385 by (not_bad_tac "Aa" 1); |
385 by (not_bad_tac "Aa" 1); |
386 by (blast_tac (!claset addSEs [MPair_parts] |
386 by (blast_tac (claset() addSEs [MPair_parts] |
387 addSDs [A_trusts_YM3, B_trusts_YM4_shrK] |
387 addSDs [A_trusts_YM3, B_trusts_YM4_shrK] |
388 addDs [Says_imp_spies RS parts.Inj, |
388 addDs [Says_imp_spies RS parts.Inj, |
389 unique_session_keys]) 1); |
389 unique_session_keys]) 1); |
390 val lemma = normalize_thm [RSspec, RSmp] (result()) |> standard; |
390 val lemma = normalize_thm [RSspec, RSmp] (result()) |> standard; |
391 |
391 |
398 \ (ALL NA. Says A Spy {|Nonce NA, Nonce NB, Key K|} ~: set evs); \ |
398 \ (ALL NA. Says A Spy {|Nonce NA, Nonce NB, Key K|} ~: set evs); \ |
399 \ A ~: bad; B ~: bad; evs : yahalom |] \ |
399 \ A ~: bad; B ~: bad; evs : yahalom |] \ |
400 \ ==> EX X. Says A B {|X, Crypt K (Nonce NB)|} : set evs"; |
400 \ ==> EX X. Says A B {|X, Crypt K (Nonce NB)|} : set evs"; |
401 by (etac (Says_imp_spies RS parts.Inj RS MPair_parts) 1); |
401 by (etac (Says_imp_spies RS parts.Inj RS MPair_parts) 1); |
402 by (dtac B_trusts_YM4_shrK 1); |
402 by (dtac B_trusts_YM4_shrK 1); |
403 by (safe_tac (!claset)); |
403 by (safe_tac (claset())); |
404 by (rtac lemma 1); |
404 by (rtac lemma 1); |
405 by (rtac Spy_not_see_encrypted_key 2); |
405 by (rtac Spy_not_see_encrypted_key 2); |
406 by (REPEAT_FIRST assume_tac); |
406 by (REPEAT_FIRST assume_tac); |
407 by (ALLGOALS (blast_tac (!claset addSEs [MPair_parts] |
407 by (ALLGOALS (blast_tac (claset() addSEs [MPair_parts] |
408 addDs [Says_imp_spies RS parts.Inj]))); |
408 addDs [Says_imp_spies RS parts.Inj]))); |
409 qed_spec_mp "YM4_imp_A_Said_YM3"; |
409 qed_spec_mp "YM4_imp_A_Said_YM3"; |