src/HOL/Auth/Yahalom.thy
changeset 69597 ff784d5a5bfb
parent 67613 ce654b0e6d69
child 76288 b82ac7ef65ec
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
    53                 # evs3 \<in> yahalom"
    53                 # evs3 \<in> yahalom"
    54 
    54 
    55  | YM4:  
    55  | YM4:  
    56        \<comment> \<open>Alice receives the Server's (?) message, checks her Nonce, and
    56        \<comment> \<open>Alice receives the Server's (?) message, checks her Nonce, and
    57            uses the new session key to send Bob his Nonce.  The premise
    57            uses the new session key to send Bob his Nonce.  The premise
    58            @{term "A \<noteq> Server"} is needed for \<open>Says_Server_not_range\<close>.
    58            \<^term>\<open>A \<noteq> Server\<close> is needed for \<open>Says_Server_not_range\<close>.
    59            Alice can check that K is symmetric by its length.\<close>
    59            Alice can check that K is symmetric by its length.\<close>
    60          "\<lbrakk>evs4 \<in> yahalom;  A \<noteq> Server;  K \<in> symKeys;
    60          "\<lbrakk>evs4 \<in> yahalom;  A \<noteq> Server;  K \<in> symKeys;
    61              Gets A \<lbrace>Crypt(shrK A) \<lbrace>Agent B, Key K, Nonce NA, Nonce NB\<rbrace>, X\<rbrace>
    61              Gets A \<lbrace>Crypt(shrK A) \<lbrace>Agent B, Key K, Nonce NA, Nonce NB\<rbrace>, X\<rbrace>
    62                 \<in> set evs4;
    62                 \<in> set evs4;
    63              Says A B \<lbrace>Agent A, Nonce NA\<rbrace> \<in> set evs4\<rbrakk>
    63              Says A B \<lbrace>Agent A, Nonce NA\<rbrace> \<in> set evs4\<rbrakk>
   127 lemma YM4_Key_parts_knows_Spy:
   127 lemma YM4_Key_parts_knows_Spy:
   128      "Says Server A \<lbrace>Crypt (shrK A) \<lbrace>B,K,NA,NB\<rbrace>, X\<rbrace> \<in> set evs
   128      "Says Server A \<lbrace>Crypt (shrK A) \<lbrace>B,K,NA,NB\<rbrace>, X\<rbrace> \<in> set evs
   129       \<Longrightarrow> K \<in> parts (knows Spy evs)"
   129       \<Longrightarrow> K \<in> parts (knows Spy evs)"
   130   by (metis parts.Body parts.Fst parts.Snd  Says_imp_knows_Spy parts.Inj)
   130   by (metis parts.Body parts.Fst parts.Snd  Says_imp_knows_Spy parts.Inj)
   131 
   131 
   132 text\<open>Theorems of the form @{term "X \<notin> parts (knows Spy evs)"} imply 
   132 text\<open>Theorems of the form \<^term>\<open>X \<notin> parts (knows Spy evs)\<close> imply 
   133 that NOBODY sends messages containing X!\<close>
   133 that NOBODY sends messages containing X!\<close>
   134 
   134 
   135 text\<open>Spy never sees a good agent's shared key!\<close>
   135 text\<open>Spy never sees a good agent's shared key!\<close>
   136 lemma Spy_see_shrK [simp]:
   136 lemma Spy_see_shrK [simp]:
   137      "evs \<in> yahalom \<Longrightarrow> (Key (shrK A) \<in> parts (knows Spy evs)) = (A \<in> bad)"
   137      "evs \<in> yahalom \<Longrightarrow> (Key (shrK A) \<in> parts (knows Spy evs)) = (A \<in> bad)"
   297 apply blast+
   297 apply blast+
   298 done
   298 done
   299 
   299 
   300 text\<open>B knows, by the second part of A's message, that the Server
   300 text\<open>B knows, by the second part of A's message, that the Server
   301   distributed the key quoting nonce NB.  This part says nothing about
   301   distributed the key quoting nonce NB.  This part says nothing about
   302   agent names.  Secrecy of NB is crucial.  Note that @{term "Nonce NB
   302   agent names.  Secrecy of NB is crucial.  Note that \<^term>\<open>Nonce NB
   303   \<notin> analz(knows Spy evs)"} must be the FIRST antecedent of the
   303   \<notin> analz(knows Spy evs)\<close> must be the FIRST antecedent of the
   304   induction formula.\<close>
   304   induction formula.\<close>
   305 
   305 
   306 lemma B_trusts_YM4_newK [rule_format]:
   306 lemma B_trusts_YM4_newK [rule_format]:
   307      "\<lbrakk>Crypt K (Nonce NB) \<in> parts (knows Spy evs);
   307      "\<lbrakk>Crypt K (Nonce NB) \<in> parts (knows Spy evs);
   308         Nonce NB \<notin> analz (knows Spy evs);  evs \<in> yahalom\<rbrakk>
   308         Nonce NB \<notin> analz (knows Spy evs);  evs \<in> yahalom\<rbrakk>
   391        add: analz_image_freshK_simps split_ifs
   391        add: analz_image_freshK_simps split_ifs
   392             all_conj_distrib ball_conj_distrib
   392             all_conj_distrib ball_conj_distrib
   393             analz_image_freshK fresh_not_KeyWithNonce
   393             analz_image_freshK fresh_not_KeyWithNonce
   394             imp_disj_not1               (*Moves NBa\<noteq>NB to the front*)
   394             imp_disj_not1               (*Moves NBa\<noteq>NB to the front*)
   395             Says_Server_KeyWithNonce)
   395             Says_Server_KeyWithNonce)
   396 txt\<open>For Oops, simplification proves @{prop "NBa\<noteq>NB"}.  By
   396 txt\<open>For Oops, simplification proves \<^prop>\<open>NBa\<noteq>NB\<close>.  By
   397   @{term Says_Server_KeyWithNonce}, we get @{prop "\<not> KeyWithNonce K NB
   397   \<^term>\<open>Says_Server_KeyWithNonce\<close>, we get \<^prop>\<open>\<not> KeyWithNonce K NB
   398   evs"}; then simplification can apply the induction hypothesis with
   398   evs\<close>; then simplification can apply the induction hypothesis with
   399   @{term "KK = {K}"}.\<close>
   399   \<^term>\<open>KK = {K}\<close>.\<close>
   400   subgoal \<comment> \<open>Fake\<close> by spy_analz
   400   subgoal \<comment> \<open>Fake\<close> by spy_analz
   401   subgoal \<comment> \<open>YM2\<close> by blast
   401   subgoal \<comment> \<open>YM2\<close> by blast
   402   subgoal \<comment> \<open>YM3\<close> by blast
   402   subgoal \<comment> \<open>YM3\<close> by blast
   403   subgoal \<comment> \<open>YM4: If @{prop "A \<in> bad"} then @{term NBa} is known, therefore @{prop "NBa \<noteq> NB"}.\<close>
   403   subgoal \<comment> \<open>YM4: If \<^prop>\<open>A \<in> bad\<close> then \<^term>\<open>NBa\<close> is known, therefore \<^prop>\<open>NBa \<noteq> NB\<close>.\<close>
   404     by (metis A_trusts_YM3 Gets_imp_analz_Spy Gets_imp_knows_Spy KeyWithNonce_def
   404     by (metis A_trusts_YM3 Gets_imp_analz_Spy Gets_imp_knows_Spy KeyWithNonce_def
   405         Spy_analz_shrK analz.Fst analz.Snd analz_shrK_Decrypt parts.Fst parts.Inj)
   405         Spy_analz_shrK analz.Fst analz.Snd analz_shrK_Decrypt parts.Fst parts.Inj)
   406 done
   406 done
   407 
   407 
   408 
   408 
   489   subgoal \<comment> \<open>YM2\<close> by blast
   489   subgoal \<comment> \<open>YM2\<close> by blast
   490   subgoal \<comment> \<open>YM3: because no NB can also be an NA\<close> 
   490   subgoal \<comment> \<open>YM3: because no NB can also be an NA\<close> 
   491     by (blast dest!: no_nonce_YM1_YM2 dest: Gets_imp_Says Says_unique_NB)
   491     by (blast dest!: no_nonce_YM1_YM2 dest: Gets_imp_Says Says_unique_NB)
   492   subgoal \<comment> \<open>YM4: key K is visible to Spy, contradicting session key secrecy theorem\<close>
   492   subgoal \<comment> \<open>YM4: key K is visible to Spy, contradicting session key secrecy theorem\<close>
   493     \<comment> \<open>Case analysis on whether Aa is bad;
   493     \<comment> \<open>Case analysis on whether Aa is bad;
   494             use \<open>Says_unique_NB\<close> to identify message components: @{term "Aa=A"}, @{term "Ba=B"}\<close>
   494             use \<open>Says_unique_NB\<close> to identify message components: \<^term>\<open>Aa=A\<close>, \<^term>\<open>Ba=B\<close>\<close>
   495     apply clarify
   495     apply clarify
   496     apply (blast dest!: Says_unique_NB analz_shrK_Decrypt
   496     apply (blast dest!: Says_unique_NB analz_shrK_Decrypt
   497                         parts.Inj [THEN parts.Fst, THEN A_trusts_YM3]
   497                         parts.Inj [THEN parts.Fst, THEN A_trusts_YM3]
   498                  dest: Gets_imp_Says Says_imp_spies Says_Server_imp_YM2
   498                  dest: Gets_imp_Says Says_imp_spies Says_Server_imp_YM2
   499                        Spy_not_see_encrypted_key)
   499                        Spy_not_see_encrypted_key)
   579   by (metis A_trusts_YM3 Gets_imp_analz_Spy YM3_auth_B_to_A_lemma analz.Fst
   579   by (metis A_trusts_YM3 Gets_imp_analz_Spy YM3_auth_B_to_A_lemma analz.Fst
   580          not_parts_not_analz)
   580          not_parts_not_analz)
   581 
   581 
   582 
   582 
   583 subsection\<open>Authenticating A to B using the certificate 
   583 subsection\<open>Authenticating A to B using the certificate 
   584   @{term "Crypt K (Nonce NB)"}\<close>
   584   \<^term>\<open>Crypt K (Nonce NB)\<close>\<close>
   585 
   585 
   586 text\<open>Assuming the session key is secure, if both certificates are present then
   586 text\<open>Assuming the session key is secure, if both certificates are present then
   587   A has said NB.  We can't be sure about the rest of A's message, but only
   587   A has said NB.  We can't be sure about the rest of A's message, but only
   588   NB matters for freshness.\<close>
   588   NB matters for freshness.\<close>
   589 theorem A_Said_YM3_lemma [rule_format]:
   589 theorem A_Said_YM3_lemma [rule_format]:
   595           (\<exists>X. Says A B \<lbrace>X, Crypt K (Nonce NB)\<rbrace> \<in> set evs)"
   595           (\<exists>X. Says A B \<lbrace>X, Crypt K (Nonce NB)\<rbrace> \<in> set evs)"
   596 apply (erule yahalom.induct, force,
   596 apply (erule yahalom.induct, force,
   597        frule_tac [6] YM4_parts_knows_Spy)
   597        frule_tac [6] YM4_parts_knows_Spy)
   598 apply (analz_mono_contra, simp_all)
   598 apply (analz_mono_contra, simp_all)
   599   subgoal \<comment> \<open>Fake\<close> by blast
   599   subgoal \<comment> \<open>Fake\<close> by blast
   600   subgoal \<comment> \<open>YM3 because the message @{term "Crypt K (Nonce NB)"} could not exist\<close>
   600   subgoal \<comment> \<open>YM3 because the message \<^term>\<open>Crypt K (Nonce NB)\<close> could not exist\<close>
   601      by (force dest!: Crypt_imp_keysFor)
   601      by (force dest!: Crypt_imp_keysFor)
   602    subgoal \<comment> \<open>YM4: was @{term "Crypt K (Nonce NB)"} the very last message? If not, use the induction hypothesis,
   602    subgoal \<comment> \<open>YM4: was \<^term>\<open>Crypt K (Nonce NB)\<close> the very last message? If not, use the induction hypothesis,
   603                otherwise by unicity of session keys\<close>
   603                otherwise by unicity of session keys\<close>
   604      by (blast dest!: Gets_imp_Says A_trusts_YM3 B_trusts_YM4_shrK Crypt_Spy_analz_bad
   604      by (blast dest!: Gets_imp_Says A_trusts_YM3 B_trusts_YM4_shrK Crypt_Spy_analz_bad
   605              dest: Says_imp_knows_Spy [THEN parts.Inj] unique_session_keys)
   605              dest: Says_imp_knows_Spy [THEN parts.Inj] unique_session_keys)
   606 done
   606 done
   607 
   607