src/HOL/Auth/Yahalom2.ML
changeset 4091 771b1f6422a8
parent 3961 6a8996fb7d99
child 4153 e534c4c32d54
equal deleted inserted replaced
4090:9f1eaab75e8c 4091:771b1f6422a8
    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";