src/HOL/Auth/NS_Public_Bad.ML
changeset 2418 6b6a92d05fb2
parent 2374 4148aa5b00a2
child 2451 ce85a2aafc7a
equal deleted inserted replaced
2417:95f275c8476e 2418:6b6a92d05fb2
   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*)