104 qed_spec_mp "new_nonces_not_seen"; |
104 qed_spec_mp "new_nonces_not_seen"; |
105 Addsimps [new_nonces_not_seen]; |
105 Addsimps [new_nonces_not_seen]; |
106 |
106 |
107 val nonce_not_seen_now = le_refl RSN (2, new_nonces_not_seen) RSN (2,rev_notE); |
107 val nonce_not_seen_now = le_refl RSN (2, new_nonces_not_seen) RSN (2,rev_notE); |
108 |
108 |
|
109 fun analz_induct_tac i = |
|
110 etac ns_public.induct i THEN |
|
111 ALLGOALS (asm_simp_tac |
|
112 (!simpset addsimps ([not_parts_not_analz] @ pushes) |
|
113 setloop split_tac [expand_if])); |
|
114 |
109 |
115 |
110 (**** Authenticity properties obtained from NS2 ****) |
116 (**** Authenticity properties obtained from NS2 ****) |
111 |
117 |
112 (*It is impossible to re-use a nonce in both NS1 and NS2, provided the nonce |
118 (*It is impossible to re-use a nonce in both NS1 and NS2, provided the nonce |
113 is secret. (Honest users generate fresh nonces.)*) |
119 is secret. (Honest users generate fresh nonces.)*) |
114 goal thy |
120 goal thy |
115 "!!evs. evs : ns_public \ |
121 "!!evs. evs : ns_public \ |
116 \ ==> Nonce NA ~: analz (sees lost Spy evs) --> \ |
122 \ ==> Nonce NA ~: analz (sees lost Spy evs) --> \ |
117 \ Crypt (pubK B) {|Nonce NA, Agent A|} : parts (sees lost Spy evs) --> \ |
123 \ Crypt (pubK B) {|Nonce NA, Agent A|} : parts (sees lost Spy evs) --> \ |
118 \ Crypt (pubK C) {|NA', Nonce NA|} ~: parts (sees lost Spy evs)"; |
124 \ Crypt (pubK C) {|NA', Nonce NA|} ~: parts (sees lost Spy evs)"; |
119 by (etac ns_public.induct 1); |
125 by (analz_induct_tac 1); |
120 by (ALLGOALS |
|
121 (asm_simp_tac |
|
122 (!simpset addsimps ([not_parts_not_analz] @ pushes) |
|
123 setloop split_tac [expand_if]))); |
|
124 (*NS3*) |
126 (*NS3*) |
125 by (fast_tac (!claset addSEs partsEs |
127 by (fast_tac (!claset addSEs partsEs |
126 addEs [nonce_not_seen_now]) 4); |
128 addEs [nonce_not_seen_now]) 4); |
127 (*NS2*) |
129 (*NS2*) |
128 by (fast_tac (!claset addSEs partsEs |
130 by (fast_tac (!claset addSEs partsEs |
142 "!!evs. evs : ns_public \ |
144 "!!evs. evs : ns_public \ |
143 \ ==> Nonce NA ~: analz (sees lost Spy evs) --> \ |
145 \ ==> Nonce NA ~: analz (sees lost Spy evs) --> \ |
144 \ (EX A' B'. ALL A B. \ |
146 \ (EX A' B'. ALL A B. \ |
145 \ Crypt (pubK B) {|Nonce NA, Agent A|} : parts (sees lost Spy evs) --> \ |
147 \ Crypt (pubK B) {|Nonce NA, Agent A|} : parts (sees lost Spy evs) --> \ |
146 \ A=A' & B=B')"; |
148 \ A=A' & B=B')"; |
147 by (etac ns_public.induct 1); |
149 by (analz_induct_tac 1); |
148 by (ALLGOALS |
|
149 (asm_simp_tac |
|
150 (!simpset addsimps ([not_parts_not_analz] @ pushes) |
|
151 setloop split_tac [expand_if]))); |
|
152 (*NS1*) |
150 (*NS1*) |
153 by (expand_case_tac "NA = ?y" 3 THEN |
151 by (expand_case_tac "NA = ?y" 3 THEN |
154 REPEAT (fast_tac (!claset addSEs (nonce_not_seen_now::partsEs)) 3)); |
152 REPEAT (fast_tac (!claset addSEs (nonce_not_seen_now::partsEs)) 3)); |
155 (*Base*) |
153 (*Base*) |
156 by (fast_tac (!claset addss (!simpset)) 1); |
154 by (fast_tac (!claset addss (!simpset)) 1); |
168 "!!evs. [| Crypt(pubK B) {|Nonce NA, Agent A|} : parts(sees lost Spy evs); \ |
166 "!!evs. [| Crypt(pubK B) {|Nonce NA, Agent A|} : parts(sees lost Spy evs); \ |
169 \ Crypt(pubK B') {|Nonce NA, Agent A'|} : parts(sees lost Spy evs); \ |
167 \ Crypt(pubK B') {|Nonce NA, Agent A'|} : parts(sees lost Spy evs); \ |
170 \ Nonce NA ~: analz (sees lost Spy evs); \ |
168 \ Nonce NA ~: analz (sees lost Spy evs); \ |
171 \ evs : ns_public |] \ |
169 \ evs : ns_public |] \ |
172 \ ==> A=A' & B=B'"; |
170 \ ==> A=A' & B=B'"; |
173 by (dtac lemma 1); |
171 by (prove_unique_tac lemma 1); |
174 by (mp_tac 1); |
|
175 by (REPEAT (etac exE 1)); |
|
176 (*Duplicate the assumption*) |
|
177 by (forw_inst_tac [("psi", "ALL C.?P(C)")] asm_rl 1); |
|
178 by (fast_tac (!claset addSDs [spec]) 1); |
|
179 qed "unique_NA"; |
172 qed "unique_NA"; |
180 |
173 |
181 |
174 |
182 (*Secrecy: Spy does not see the nonce sent in msg NS1 if A and B are secure*) |
175 (*Secrecy: Spy does not see the nonce sent in msg NS1 if A and B are secure*) |
183 goal thy |
176 goal thy |
184 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
177 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
185 \ ==> Says A B (Crypt (pubK B) {|Nonce NA, Agent A|}) : set_of_list evs \ |
178 \ ==> Says A B (Crypt (pubK B) {|Nonce NA, Agent A|}) : set_of_list evs \ |
186 \ --> Nonce NA ~: analz (sees lost Spy evs)"; |
179 \ --> Nonce NA ~: analz (sees lost Spy evs)"; |
187 by (etac ns_public.induct 1); |
180 by (analz_induct_tac 1); |
188 by (ALLGOALS |
|
189 (asm_simp_tac |
|
190 (!simpset addsimps ([not_parts_not_analz] @ pushes) |
|
191 setloop split_tac [expand_if]))); |
|
192 (*NS3*) |
181 (*NS3*) |
193 by (fast_tac (!claset addSDs [Says_imp_sees_Spy' RS parts.Inj] |
182 by (fast_tac (!claset addSDs [Says_imp_sees_Spy' RS parts.Inj] |
194 addEs [no_nonce_NS1_NS2 RSN (2, rev_notE)]) 4); |
183 addEs [no_nonce_NS1_NS2 RSN (2, rev_notE)]) 4); |
195 (*NS1*) |
184 (*NS1*) |
196 by (fast_tac (!claset addSEs partsEs |
185 by (fast_tac (!claset addSEs partsEs |
213 goal thy |
202 goal thy |
214 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
203 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
215 \ ==> Crypt (pubK A) {|Nonce NA, Nonce NB|} : parts (sees lost Spy evs) \ |
204 \ ==> Crypt (pubK A) {|Nonce NA, Nonce NB|} : parts (sees lost Spy evs) \ |
216 \ --> Says A B (Crypt (pubK B) {|Nonce NA, Agent A|}) : set_of_list evs \ |
205 \ --> Says A B (Crypt (pubK B) {|Nonce NA, Agent A|}) : set_of_list evs \ |
217 \ --> Says B A (Crypt (pubK A) {|Nonce NA, Nonce NB|}) : set_of_list evs"; |
206 \ --> Says B A (Crypt (pubK A) {|Nonce NA, Nonce NB|}) : set_of_list evs"; |
218 by (etac ns_public.induct 1); |
207 by (analz_induct_tac 1); |
219 by (ALLGOALS Asm_simp_tac); |
208 by (ALLGOALS Asm_simp_tac); |
220 (*NS1*) |
209 (*NS1*) |
221 by (fast_tac (!claset addSEs partsEs |
210 by (fast_tac (!claset addSEs partsEs |
222 addSDs [new_nonces_not_seen, |
211 addSDs [new_nonces_not_seen, |
223 Says_imp_sees_Spy' RS parts.Inj]) 2); |
212 Says_imp_sees_Spy' RS parts.Inj]) 2); |
252 goal thy |
241 goal thy |
253 "!!evs. evs : ns_public \ |
242 "!!evs. evs : ns_public \ |
254 \ ==> Nonce NA ~: analz (sees lost Spy evs) --> \ |
243 \ ==> Nonce NA ~: analz (sees lost Spy evs) --> \ |
255 \ Crypt (pubK B) {|Nonce NA, Agent A|} : parts (sees lost Spy evs) --> \ |
244 \ Crypt (pubK B) {|Nonce NA, Agent A|} : parts (sees lost Spy evs) --> \ |
256 \ Says A B (Crypt (pubK B) {|Nonce NA, Agent A|}) : set_of_list evs"; |
245 \ Says A B (Crypt (pubK B) {|Nonce NA, Agent A|}) : set_of_list evs"; |
257 by (etac ns_public.induct 1); |
246 by (analz_induct_tac 1); |
258 by (ALLGOALS |
|
259 (asm_simp_tac |
|
260 (!simpset addsimps ([not_parts_not_analz] @ pushes) |
|
261 setloop split_tac [expand_if]))); |
|
262 (*Fake*) |
247 (*Fake*) |
263 by (best_tac (!claset addSIs [disjI2] |
248 by (best_tac (!claset addSIs [disjI2] |
264 addSDs [impOfSubs Fake_parts_insert] |
249 addSDs [impOfSubs Fake_parts_insert] |
265 addIs [analz_insertI] |
250 addIs [analz_insertI] |
266 addDs [impOfSubs analz_subset_parts] |
251 addDs [impOfSubs analz_subset_parts] |
279 "!!evs. evs : ns_public \ |
264 "!!evs. evs : ns_public \ |
280 \ ==> Nonce NB ~: analz (sees lost Spy evs) --> \ |
265 \ ==> Nonce NB ~: analz (sees lost Spy evs) --> \ |
281 \ (EX A' NA'. ALL A NA. \ |
266 \ (EX A' NA'. ALL A NA. \ |
282 \ Crypt (pubK A) {|Nonce NA, Nonce NB|} : parts (sees lost Spy evs) --> \ |
267 \ Crypt (pubK A) {|Nonce NA, Nonce NB|} : parts (sees lost Spy evs) --> \ |
283 \ A=A' & NA=NA')"; |
268 \ A=A' & NA=NA')"; |
284 by (etac ns_public.induct 1); |
269 by (analz_induct_tac 1); |
285 by (ALLGOALS |
|
286 (asm_simp_tac |
|
287 (!simpset addsimps ([not_parts_not_analz] @ pushes) |
|
288 setloop split_tac [expand_if]))); |
|
289 (*NS2*) |
270 (*NS2*) |
290 by (expand_case_tac "NB = ?y" 3 THEN |
271 by (expand_case_tac "NB = ?y" 3 THEN |
291 REPEAT (fast_tac (!claset addSEs (nonce_not_seen_now::partsEs)) 3)); |
272 REPEAT (fast_tac (!claset addSEs (nonce_not_seen_now::partsEs)) 3)); |
292 (*Base*) |
273 (*Base*) |
293 by (fast_tac (!claset addss (!simpset)) 1); |
274 by (fast_tac (!claset addss (!simpset)) 1); |
305 "!!evs. [| Crypt(pubK A) {|Nonce NA, Nonce NB|} : parts(sees lost Spy evs); \ |
286 "!!evs. [| Crypt(pubK A) {|Nonce NA, Nonce NB|} : parts(sees lost Spy evs); \ |
306 \ Crypt(pubK A'){|Nonce NA', Nonce NB|} : parts(sees lost Spy evs); \ |
287 \ Crypt(pubK A'){|Nonce NA', Nonce NB|} : parts(sees lost Spy evs); \ |
307 \ Nonce NB ~: analz (sees lost Spy evs); \ |
288 \ Nonce NB ~: analz (sees lost Spy evs); \ |
308 \ evs : ns_public |] \ |
289 \ evs : ns_public |] \ |
309 \ ==> A=A' & NA=NA'"; |
290 \ ==> A=A' & NA=NA'"; |
310 by (dtac lemma 1); |
291 by (prove_unique_tac lemma 1); |
311 by (mp_tac 1); |
|
312 by (REPEAT (etac exE 1)); |
|
313 (*Duplicate the assumption*) |
|
314 by (forw_inst_tac [("psi", "ALL C.?P(C)")] asm_rl 1); |
|
315 by (fast_tac (!claset addSDs [spec]) 1); |
|
316 qed "unique_NB"; |
292 qed "unique_NB"; |
317 |
293 |
318 |
294 |
319 (*NB remains secret PROVIDED Alice never responds with round 3*) |
295 (*NB remains secret PROVIDED Alice never responds with round 3*) |
320 goal thy |
296 goal thy |
321 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
297 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
322 \ ==> Says B A (Crypt (pubK A) {|Nonce NA, Nonce NB|}) : set_of_list evs --> \ |
298 \ ==> Says B A (Crypt (pubK A) {|Nonce NA, Nonce NB|}) : set_of_list evs --> \ |
323 \ (ALL C. Says A C (Crypt (pubK C) (Nonce NB)) ~: set_of_list evs) --> \ |
299 \ (ALL C. Says A C (Crypt (pubK C) (Nonce NB)) ~: set_of_list evs) --> \ |
324 \ Nonce NB ~: analz (sees lost Spy evs)"; |
300 \ Nonce NB ~: analz (sees lost Spy evs)"; |
325 by (etac ns_public.induct 1); |
301 by (analz_induct_tac 1); |
326 by (ALLGOALS |
|
327 (asm_simp_tac |
|
328 (!simpset addsimps ([not_parts_not_analz] @ pushes) |
|
329 setloop split_tac [expand_if]))); |
|
330 (*NS1*) |
302 (*NS1*) |
331 by (fast_tac (!claset addSEs partsEs |
303 by (fast_tac (!claset addSEs partsEs |
332 addSDs [new_nonces_not_seen, |
304 addSDs [new_nonces_not_seen, |
333 Says_imp_sees_Spy' RS parts.Inj]) 2); |
305 Says_imp_sees_Spy' RS parts.Inj]) 2); |
334 (*Fake*) |
306 (*Fake*) |
361 goal thy |
333 goal thy |
362 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
334 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
363 \ ==> Crypt (pubK B) (Nonce NB) : parts (sees lost Spy evs) \ |
335 \ ==> Crypt (pubK B) (Nonce NB) : parts (sees lost Spy evs) \ |
364 \ --> Says B A (Crypt (pubK A) {|Nonce NA, Nonce NB|}) : set_of_list evs \ |
336 \ --> Says B A (Crypt (pubK A) {|Nonce NA, Nonce NB|}) : set_of_list evs \ |
365 \ --> (EX C. Says A C (Crypt (pubK C) (Nonce NB)) : set_of_list evs)"; |
337 \ --> (EX C. Says A C (Crypt (pubK C) (Nonce NB)) : set_of_list evs)"; |
366 by (etac ns_public.induct 1); |
338 by (analz_induct_tac 1); |
367 by (ALLGOALS (asm_simp_tac (!simpset addsimps [ex_disj_distrib]))); |
339 by (ALLGOALS (asm_simp_tac (!simpset addsimps [ex_disj_distrib]))); |
368 by (ALLGOALS Asm_simp_tac); |
340 by (ALLGOALS Asm_simp_tac); |
369 (*NS1*) |
341 (*NS1*) |
370 by (fast_tac (!claset addSEs partsEs |
342 by (fast_tac (!claset addSEs partsEs |
371 addSDs [new_nonces_not_seen, |
343 addSDs [new_nonces_not_seen, |
405 (*Can we strengthen the secrecy theorem? NO*) |
377 (*Can we strengthen the secrecy theorem? NO*) |
406 goal thy |
378 goal thy |
407 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
379 "!!evs. [| A ~: lost; B ~: lost; evs : ns_public |] \ |
408 \ ==> Says B A (Crypt (pubK A) {|Nonce NA, Nonce NB|}) : set_of_list evs \ |
380 \ ==> Says B A (Crypt (pubK A) {|Nonce NA, Nonce NB|}) : set_of_list evs \ |
409 \ --> Nonce NB ~: analz (sees lost Spy evs)"; |
381 \ --> Nonce NB ~: analz (sees lost Spy evs)"; |
410 by (etac ns_public.induct 1); |
382 by (analz_induct_tac 1); |
411 by (ALLGOALS |
|
412 (asm_simp_tac |
|
413 (!simpset addsimps ([not_parts_not_analz] @ pushes) |
|
414 setloop split_tac [expand_if]))); |
|
415 (*NS1*) |
383 (*NS1*) |
416 by (fast_tac (!claset addSEs partsEs |
384 by (fast_tac (!claset addSEs partsEs |
417 addSDs [new_nonces_not_seen, |
385 addSDs [new_nonces_not_seen, |
418 Says_imp_sees_Spy' RS parts.Inj]) 2); |
386 Says_imp_sees_Spy' RS parts.Inj]) 2); |
419 (*Fake*) |
387 (*Fake*) |