src/HOL/Auth/WooLam.ML
changeset 3465 e85c24717cad
parent 3121 cbb6c0c1c58a
child 3466 30791e5a69c4
equal deleted inserted replaced
3464:315694e22856 3465:e85c24717cad
    20 (*A "possibility property": there are traces that reach the end*)
    20 (*A "possibility property": there are traces that reach the end*)
    21 goal thy 
    21 goal thy 
    22  "!!A B. [| A ~= B; A ~= Server; B ~= Server |]   \
    22  "!!A B. [| A ~= B; A ~= Server; B ~= Server |]   \
    23 \        ==> EX NB. EX evs: woolam.               \
    23 \        ==> EX NB. EX evs: woolam.               \
    24 \               Says Server B (Crypt (shrK B) {|Agent A, Nonce NB|}) \
    24 \               Says Server B (Crypt (shrK B) {|Agent A, Nonce NB|}) \
    25 \                 : set_of_list evs";
    25 \                 : set evs";
    26 by (REPEAT (resolve_tac [exI,bexI] 1));
    26 by (REPEAT (resolve_tac [exI,bexI] 1));
    27 by (rtac (woolam.Nil RS woolam.WL1 RS woolam.WL2 RS woolam.WL3 RS 
    27 by (rtac (woolam.Nil RS woolam.WL1 RS woolam.WL2 RS woolam.WL3 RS 
    28           woolam.WL4 RS woolam.WL5) 2);
    28           woolam.WL4 RS woolam.WL5) 2);
    29 by (ALLGOALS (simp_tac (!simpset setSolver safe_solver)));
    29 by (ALLGOALS (simp_tac (!simpset setSolver safe_solver)));
    30 by (REPEAT_FIRST (resolve_tac [refl, conjI]));
    30 by (REPEAT_FIRST (resolve_tac [refl, conjI]));
    33 
    33 
    34 
    34 
    35 (**** Inductive proofs about woolam ****)
    35 (**** Inductive proofs about woolam ****)
    36 
    36 
    37 (*Nobody sends themselves messages*)
    37 (*Nobody sends themselves messages*)
    38 goal thy "!!evs. evs : woolam ==> ALL A X. Says A A X ~: set_of_list evs";
    38 goal thy "!!evs. evs : woolam ==> ALL A X. Says A A X ~: set evs";
    39 by (etac woolam.induct 1);
    39 by (etac woolam.induct 1);
    40 by (Auto_tac());
    40 by (Auto_tac());
    41 qed_spec_mp "not_Says_to_self";
    41 qed_spec_mp "not_Says_to_self";
    42 Addsimps [not_Says_to_self];
    42 Addsimps [not_Says_to_self];
    43 AddSEs   [not_Says_to_self RSN (2, rev_notE)];
    43 AddSEs   [not_Says_to_self RSN (2, rev_notE)];
    44 
    44 
    45 
    45 
    46 (** For reasoning about the encrypted portion of messages **)
    46 (** For reasoning about the encrypted portion of messages **)
    47 
    47 
    48 goal thy "!!evs. Says A' B X : set_of_list evs \
    48 goal thy "!!evs. Says A' B X : set evs \
    49 \                ==> X : analz (sees lost Spy evs)";
    49 \                ==> X : analz (sees lost Spy evs)";
    50 by (etac (Says_imp_sees_Spy RS analz.Inj) 1);
    50 by (etac (Says_imp_sees_Spy RS analz.Inj) 1);
    51 qed "WL4_analz_sees_Spy";
    51 qed "WL4_analz_sees_Spy";
    52 
    52 
    53 bind_thm ("WL4_parts_sees_Spy",
    53 bind_thm ("WL4_parts_sees_Spy",
    95 
    95 
    96 (*If the encrypted message appears then it originated with Alice*)
    96 (*If the encrypted message appears then it originated with Alice*)
    97 goal thy 
    97 goal thy 
    98  "!!evs. [| A ~: lost;  evs : woolam |]                   \
    98  "!!evs. [| A ~: lost;  evs : woolam |]                   \
    99 \    ==> Crypt (shrK A) (Nonce NB) : parts (sees lost Spy evs)        \
    99 \    ==> Crypt (shrK A) (Nonce NB) : parts (sees lost Spy evs)        \
   100 \        --> (EX B. Says A B (Crypt (shrK A) (Nonce NB)) : set_of_list evs)";
   100 \        --> (EX B. Says A B (Crypt (shrK A) (Nonce NB)) : set evs)";
   101 by parts_induct_tac;
   101 by parts_induct_tac;
   102 by (Fake_parts_insert_tac 1);
   102 by (Fake_parts_insert_tac 1);
   103 by (Blast_tac 1);
   103 by (Blast_tac 1);
   104 qed_spec_mp "NB_Crypt_imp_Alice_msg";
   104 qed_spec_mp "NB_Crypt_imp_Alice_msg";
   105 
   105 
   107   Alice, then she originated that certificate.  But we DO NOT know that B
   107   Alice, then she originated that certificate.  But we DO NOT know that B
   108   ever saw it: the Spy may have rerouted the message to the Server.*)
   108   ever saw it: the Spy may have rerouted the message to the Server.*)
   109 goal thy 
   109 goal thy 
   110  "!!evs. [| A ~: lost;  evs : woolam;               \
   110  "!!evs. [| A ~: lost;  evs : woolam;               \
   111 \           Says B' Server {|Agent A, Agent B, Crypt (shrK A) (Nonce NB)|} \
   111 \           Says B' Server {|Agent A, Agent B, Crypt (shrK A) (Nonce NB)|} \
   112 \            : set_of_list evs |]                                  \
   112 \            : set evs |]                                  \
   113 \        ==> EX B. Says A B (Crypt (shrK A) (Nonce NB)) : set_of_list evs";
   113 \        ==> EX B. Says A B (Crypt (shrK A) (Nonce NB)) : set evs";
   114 by (blast_tac (!claset addSIs [NB_Crypt_imp_Alice_msg]
   114 by (blast_tac (!claset addSIs [NB_Crypt_imp_Alice_msg]
   115                       addSEs [MPair_parts]
   115                       addSEs [MPair_parts]
   116                       addDs  [Says_imp_sees_Spy RS parts.Inj]) 1);
   116                       addDs  [Says_imp_sees_Spy RS parts.Inj]) 1);
   117 qed "Server_trusts_WL4";
   117 qed "Server_trusts_WL4";
   118 
   118 
   120 (*** WL5 ***)
   120 (*** WL5 ***)
   121 
   121 
   122 (*Server sent WL5 only if it received the right sort of message*)
   122 (*Server sent WL5 only if it received the right sort of message*)
   123 goal thy 
   123 goal thy 
   124  "!!evs. evs : woolam ==>                                              \
   124  "!!evs. evs : woolam ==>                                              \
   125 \        Says Server B (Crypt (shrK B) {|Agent A, NB|}) : set_of_list evs   \
   125 \        Says Server B (Crypt (shrK B) {|Agent A, NB|}) : set evs   \
   126 \        --> (EX B'. Says B' Server {|Agent A, Agent B, Crypt (shrK A) NB|} \
   126 \        --> (EX B'. Says B' Server {|Agent A, Agent B, Crypt (shrK A) NB|} \
   127 \               : set_of_list evs)";
   127 \               : set evs)";
   128 by parts_induct_tac;
   128 by parts_induct_tac;
   129 by (Fake_parts_insert_tac 1);
   129 by (Fake_parts_insert_tac 1);
   130 by (ALLGOALS Blast_tac);
   130 by (ALLGOALS Blast_tac);
   131 bind_thm ("Server_sent_WL5", result() RSN (2, rev_mp));
   131 bind_thm ("Server_sent_WL5", result() RSN (2, rev_mp));
   132 
   132 
   133 
   133 
   134 (*If the encrypted message appears then it originated with the Server!*)
   134 (*If the encrypted message appears then it originated with the Server!*)
   135 goal thy 
   135 goal thy 
   136  "!!evs. [| B ~: lost;  evs : woolam |]                   \
   136  "!!evs. [| B ~: lost;  evs : woolam |]                   \
   137 \    ==> Crypt (shrK B) {|Agent A, NB|} : parts (sees lost Spy evs)        \
   137 \    ==> Crypt (shrK B) {|Agent A, NB|} : parts (sees lost Spy evs)        \
   138 \        --> Says Server B (Crypt (shrK B) {|Agent A, NB|}) : set_of_list evs";
   138 \        --> Says Server B (Crypt (shrK B) {|Agent A, NB|}) : set evs";
   139 by parts_induct_tac;
   139 by parts_induct_tac;
   140 by (Fake_parts_insert_tac 1);
   140 by (Fake_parts_insert_tac 1);
   141 qed_spec_mp "NB_Crypt_imp_Server_msg";
   141 qed_spec_mp "NB_Crypt_imp_Server_msg";
   142 
   142 
   143 (*Partial guarantee for B: if it gets a message of correct form then the Server
   143 (*Partial guarantee for B: if it gets a message of correct form then the Server
   144   sent the same message.*)
   144   sent the same message.*)
   145 goal thy 
   145 goal thy 
   146  "!!evs. [| Says S B (Crypt (shrK B) {|Agent A, NB|}) : set_of_list evs; \
   146  "!!evs. [| Says S B (Crypt (shrK B) {|Agent A, NB|}) : set evs; \
   147 \           B ~: lost;  evs : woolam |]                                  \
   147 \           B ~: lost;  evs : woolam |]                                  \
   148 \        ==> Says Server B (Crypt (shrK B) {|Agent A, NB|}) : set_of_list evs";
   148 \        ==> Says Server B (Crypt (shrK B) {|Agent A, NB|}) : set evs";
   149 by (blast_tac (!claset addSIs [NB_Crypt_imp_Server_msg]
   149 by (blast_tac (!claset addSIs [NB_Crypt_imp_Server_msg]
   150                       addDs  [Says_imp_sees_Spy RS parts.Inj]) 1);
   150                       addDs  [Says_imp_sees_Spy RS parts.Inj]) 1);
   151 qed "B_got_WL5";
   151 qed "B_got_WL5";
   152 
   152 
   153 (*Guarantee for B.  If B gets the Server's certificate then A has encrypted
   153 (*Guarantee for B.  If B gets the Server's certificate then A has encrypted
   154   the nonce using her key.  This event can be no older than the nonce itself.
   154   the nonce using her key.  This event can be no older than the nonce itself.
   155   But A may have sent the nonce to some other agent and it could have reached
   155   But A may have sent the nonce to some other agent and it could have reached
   156   the Server via the Spy.*)
   156   the Server via the Spy.*)
   157 goal thy 
   157 goal thy 
   158  "!!evs. [| Says S B (Crypt (shrK B) {|Agent A, Nonce NB|}): set_of_list evs; \
   158  "!!evs. [| Says S B (Crypt (shrK B) {|Agent A, Nonce NB|}): set evs; \
   159 \           A ~: lost;  B ~: lost;  evs : woolam  |] \
   159 \           A ~: lost;  B ~: lost;  evs : woolam  |] \
   160 \        ==> EX B. Says A B (Crypt (shrK A) (Nonce NB)) : set_of_list evs";
   160 \        ==> EX B. Says A B (Crypt (shrK A) (Nonce NB)) : set evs";
   161 by (blast_tac (!claset addIs  [Server_trusts_WL4]
   161 by (blast_tac (!claset addIs  [Server_trusts_WL4]
   162                       addSDs [B_got_WL5 RS Server_sent_WL5]) 1);
   162                       addSDs [B_got_WL5 RS Server_sent_WL5]) 1);
   163 qed "B_trusts_WL5";
   163 qed "B_trusts_WL5";
   164 
   164 
   165 
   165 
   166 (*B only issues challenges in response to WL1.  Useful??*)
   166 (*B only issues challenges in response to WL1.  Useful??*)
   167 goal thy 
   167 goal thy 
   168  "!!evs. [| B ~= Spy;  evs : woolam |]                   \
   168  "!!evs. [| B ~= Spy;  evs : woolam |]                   \
   169 \    ==> Says B A (Nonce NB) : set_of_list evs        \
   169 \    ==> Says B A (Nonce NB) : set evs        \
   170 \        --> (EX A'. Says A' B (Agent A) : set_of_list evs)";
   170 \        --> (EX A'. Says A' B (Agent A) : set evs)";
   171 by parts_induct_tac;
   171 by parts_induct_tac;
   172 by (Fake_parts_insert_tac 1);
   172 by (Fake_parts_insert_tac 1);
   173 by (ALLGOALS Blast_tac);
   173 by (ALLGOALS Blast_tac);
   174 bind_thm ("B_said_WL2", result() RSN (2, rev_mp));
   174 bind_thm ("B_said_WL2", result() RSN (2, rev_mp));
   175 
   175 
   176 
   176 
   177 (**CANNOT be proved because A doesn't know where challenges come from...
   177 (**CANNOT be proved because A doesn't know where challenges come from...
   178 goal thy 
   178 goal thy 
   179  "!!evs. [| A ~: lost;  B ~= Spy;  evs : woolam |]                   \
   179  "!!evs. [| A ~: lost;  B ~= Spy;  evs : woolam |]                   \
   180 \    ==> Crypt (shrK A) (Nonce NB) : parts (sees lost Spy evs) &  \
   180 \    ==> Crypt (shrK A) (Nonce NB) : parts (sees lost Spy evs) &  \
   181 \        Says B A (Nonce NB) : set_of_list evs        \
   181 \        Says B A (Nonce NB) : set evs        \
   182 \        --> Says A B (Crypt (shrK A) (Nonce NB)) : set_of_list evs";
   182 \        --> Says A B (Crypt (shrK A) (Nonce NB)) : set evs";
   183 by parts_induct_tac;
   183 by parts_induct_tac;
   184 by (Fake_parts_insert_tac 1);
   184 by (Fake_parts_insert_tac 1);
   185 by (Step_tac 1);
   185 by (Step_tac 1);
   186 by (blast_tac (!claset addSEs partsEs) 1);
   186 by (blast_tac (!claset addSEs partsEs) 1);
   187 **)
   187 **)