src/HOL/Auth/Public.ML
changeset 5076 fbc9d95b62ba
parent 4686 74a12e86b20b
child 5114 c729d4c299c1
equal deleted inserted replaced
5075:9a3d48fa28ca 5076:fbc9d95b62ba
    13 
    13 
    14 (*** Basic properties of pubK & priK ***)
    14 (*** Basic properties of pubK & priK ***)
    15 
    15 
    16 AddIffs [inj_pubK RS inj_eq];
    16 AddIffs [inj_pubK RS inj_eq];
    17 
    17 
    18 goal thy "!!A B. (priK A = priK B) = (A=B)";
    18 Goal "!!A B. (priK A = priK B) = (A=B)";
    19 by Safe_tac;
    19 by Safe_tac;
    20 by (dres_inst_tac [("f","invKey")] arg_cong 1);
    20 by (dres_inst_tac [("f","invKey")] arg_cong 1);
    21 by (Full_simp_tac 1);
    21 by (Full_simp_tac 1);
    22 qed "priK_inj_eq";
    22 qed "priK_inj_eq";
    23 
    23 
    24 AddIffs [priK_inj_eq];
    24 AddIffs [priK_inj_eq];
    25 AddIffs [priK_neq_pubK, priK_neq_pubK RS not_sym];
    25 AddIffs [priK_neq_pubK, priK_neq_pubK RS not_sym];
    26 
    26 
    27 goalw thy [isSymKey_def] "~ isSymKey (pubK A)";
    27 Goalw [isSymKey_def] "~ isSymKey (pubK A)";
    28 by (Simp_tac 1);
    28 by (Simp_tac 1);
    29 qed "not_isSymKey_pubK";
    29 qed "not_isSymKey_pubK";
    30 
    30 
    31 goalw thy [isSymKey_def] "~ isSymKey (priK A)";
    31 Goalw [isSymKey_def] "~ isSymKey (priK A)";
    32 by (Simp_tac 1);
    32 by (Simp_tac 1);
    33 qed "not_isSymKey_priK";
    33 qed "not_isSymKey_priK";
    34 
    34 
    35 AddIffs [not_isSymKey_pubK, not_isSymKey_priK];
    35 AddIffs [not_isSymKey_pubK, not_isSymKey_priK];
    36 
    36 
    37 
    37 
    38 (** "Image" equations that hold for injective functions **)
    38 (** "Image" equations that hold for injective functions **)
    39 
    39 
    40 goal thy "(invKey x : invKey``A) = (x:A)";
    40 Goal "(invKey x : invKey``A) = (x:A)";
    41 by Auto_tac;
    41 by Auto_tac;
    42 qed "invKey_image_eq";
    42 qed "invKey_image_eq";
    43 
    43 
    44 (*holds because invKey is injective*)
    44 (*holds because invKey is injective*)
    45 goal thy "(pubK x : pubK``A) = (x:A)";
    45 Goal "(pubK x : pubK``A) = (x:A)";
    46 by Auto_tac;
    46 by Auto_tac;
    47 qed "pubK_image_eq";
    47 qed "pubK_image_eq";
    48 
    48 
    49 goal thy "(priK x ~: pubK``A)";
    49 Goal "(priK x ~: pubK``A)";
    50 by Auto_tac;
    50 by Auto_tac;
    51 qed "priK_pubK_image_eq";
    51 qed "priK_pubK_image_eq";
    52 Addsimps [invKey_image_eq, pubK_image_eq, priK_pubK_image_eq];
    52 Addsimps [invKey_image_eq, pubK_image_eq, priK_pubK_image_eq];
    53 
    53 
    54 
    54 
    55 (** Rewrites should not refer to  initState(Friend i) 
    55 (** Rewrites should not refer to  initState(Friend i) 
    56     -- not in normal form! **)
    56     -- not in normal form! **)
    57 
    57 
    58 goalw thy [keysFor_def] "keysFor (parts (initState C)) = {}";
    58 Goalw [keysFor_def] "keysFor (parts (initState C)) = {}";
    59 by (induct_tac "C" 1);
    59 by (induct_tac "C" 1);
    60 by (auto_tac (claset() addIs [range_eqI], simpset()));
    60 by (auto_tac (claset() addIs [range_eqI], simpset()));
    61 qed "keysFor_parts_initState";
    61 qed "keysFor_parts_initState";
    62 Addsimps [keysFor_parts_initState];
    62 Addsimps [keysFor_parts_initState];
    63 
    63 
    64 
    64 
    65 (*** Function "spies" ***)
    65 (*** Function "spies" ***)
    66 
    66 
    67 (*Agents see their own private keys!*)
    67 (*Agents see their own private keys!*)
    68 goal thy "Key (priK A) : initState A";
    68 Goal "Key (priK A) : initState A";
    69 by (induct_tac "A" 1);
    69 by (induct_tac "A" 1);
    70 by Auto_tac;
    70 by Auto_tac;
    71 qed "priK_in_initState";
    71 qed "priK_in_initState";
    72 AddIffs [priK_in_initState];
    72 AddIffs [priK_in_initState];
    73 
    73 
    74 (*All public keys are visible*)
    74 (*All public keys are visible*)
    75 goal thy "Key (pubK A) : spies evs";
    75 Goal "Key (pubK A) : spies evs";
    76 by (induct_tac "evs" 1);
    76 by (induct_tac "evs" 1);
    77 by (ALLGOALS (asm_simp_tac
    77 by (ALLGOALS (asm_simp_tac
    78 	      (simpset() addsimps [imageI, spies_Cons]
    78 	      (simpset() addsimps [imageI, spies_Cons]
    79 	                addsplits [expand_event_case])));
    79 	                addsplits [expand_event_case])));
    80 qed_spec_mp "spies_pubK";
    80 qed_spec_mp "spies_pubK";
    81 
    81 
    82 (*Spy sees private keys of bad agents!*)
    82 (*Spy sees private keys of bad agents!*)
    83 goal thy "!!A. A: bad ==> Key (priK A) : spies evs";
    83 Goal "!!A. A: bad ==> Key (priK A) : spies evs";
    84 by (induct_tac "evs" 1);
    84 by (induct_tac "evs" 1);
    85 by (ALLGOALS (asm_simp_tac
    85 by (ALLGOALS (asm_simp_tac
    86 	      (simpset() addsimps [imageI, spies_Cons]
    86 	      (simpset() addsimps [imageI, spies_Cons]
    87 	                addsplits [expand_event_case])));
    87 	                addsplits [expand_event_case])));
    88 qed "Spy_spies_bad";
    88 qed "Spy_spies_bad";
    90 AddIffs [spies_pubK, spies_pubK RS analz.Inj];
    90 AddIffs [spies_pubK, spies_pubK RS analz.Inj];
    91 AddSIs  [Spy_spies_bad];
    91 AddSIs  [Spy_spies_bad];
    92 
    92 
    93 
    93 
    94 (*For not_bad_tac*)
    94 (*For not_bad_tac*)
    95 goal thy "!!A. [| Crypt (pubK A) X : analz (spies evs);  A: bad |] \
    95 Goal "!!A. [| Crypt (pubK A) X : analz (spies evs);  A: bad |] \
    96 \              ==> X : analz (spies evs)";
    96 \              ==> X : analz (spies evs)";
    97 by (blast_tac (claset() addSDs [analz.Decrypt]) 1);
    97 by (blast_tac (claset() addSDs [analz.Decrypt]) 1);
    98 qed "Crypt_Spy_analz_bad";
    98 qed "Crypt_Spy_analz_bad";
    99 
    99 
   100 (*Prove that the agent is uncompromised by the confidentiality of 
   100 (*Prove that the agent is uncompromised by the confidentiality of 
   110          Safe_tac);
   110          Safe_tac);
   111 
   111 
   112 
   112 
   113 (*** Fresh nonces ***)
   113 (*** Fresh nonces ***)
   114 
   114 
   115 goal thy "Nonce N ~: parts (initState B)";
   115 Goal "Nonce N ~: parts (initState B)";
   116 by (induct_tac "B" 1);
   116 by (induct_tac "B" 1);
   117 by Auto_tac;
   117 by Auto_tac;
   118 qed "Nonce_notin_initState";
   118 qed "Nonce_notin_initState";
   119 AddIffs [Nonce_notin_initState];
   119 AddIffs [Nonce_notin_initState];
   120 
   120 
   121 goal thy "Nonce N ~: used []";
   121 Goal "Nonce N ~: used []";
   122 by (simp_tac (simpset() addsimps [used_Nil]) 1);
   122 by (simp_tac (simpset() addsimps [used_Nil]) 1);
   123 qed "Nonce_notin_used_empty";
   123 qed "Nonce_notin_used_empty";
   124 Addsimps [Nonce_notin_used_empty];
   124 Addsimps [Nonce_notin_used_empty];
   125 
   125 
   126 
   126 
   127 (*** Supply fresh nonces for possibility theorems. ***)
   127 (*** Supply fresh nonces for possibility theorems. ***)
   128 
   128 
   129 (*In any trace, there is an upper bound N on the greatest nonce in use.*)
   129 (*In any trace, there is an upper bound N on the greatest nonce in use.*)
   130 goal thy "EX N. ALL n. N<=n --> Nonce n ~: used evs";
   130 Goal "EX N. ALL n. N<=n --> Nonce n ~: used evs";
   131 by (induct_tac "evs" 1);
   131 by (induct_tac "evs" 1);
   132 by (res_inst_tac [("x","0")] exI 1);
   132 by (res_inst_tac [("x","0")] exI 1);
   133 by (ALLGOALS (asm_simp_tac
   133 by (ALLGOALS (asm_simp_tac
   134 	      (simpset() addsimps [used_Cons]
   134 	      (simpset() addsimps [used_Cons]
   135 			addsplits [expand_event_case])));
   135 			addsplits [expand_event_case])));
   136 by Safe_tac;
   136 by Safe_tac;
   137 by (ALLGOALS (rtac (msg_Nonce_supply RS exE)));
   137 by (ALLGOALS (rtac (msg_Nonce_supply RS exE)));
   138 by (ALLGOALS (blast_tac (claset() addSEs [add_leE])));
   138 by (ALLGOALS (blast_tac (claset() addSEs [add_leE])));
   139 val lemma = result();
   139 val lemma = result();
   140 
   140 
   141 goal thy "EX N. Nonce N ~: used evs";
   141 Goal "EX N. Nonce N ~: used evs";
   142 by (rtac (lemma RS exE) 1);
   142 by (rtac (lemma RS exE) 1);
   143 by (Blast_tac 1);
   143 by (Blast_tac 1);
   144 qed "Nonce_supply1";
   144 qed "Nonce_supply1";
   145 
   145 
   146 goal thy "Nonce (@ N. Nonce N ~: used evs) ~: used evs";
   146 Goal "Nonce (@ N. Nonce N ~: used evs) ~: used evs";
   147 by (rtac (lemma RS exE) 1);
   147 by (rtac (lemma RS exE) 1);
   148 by (rtac selectI 1);
   148 by (rtac selectI 1);
   149 by (Fast_tac 1);
   149 by (Fast_tac 1);
   150 qed "Nonce_supply";
   150 qed "Nonce_supply";
   151 
   151 
   158                    resolve_tac [refl, conjI, Nonce_supply]));
   158                    resolve_tac [refl, conjI, Nonce_supply]));
   159 
   159 
   160 
   160 
   161 (*** Specialized rewriting for the analz_image_... theorems ***)
   161 (*** Specialized rewriting for the analz_image_... theorems ***)
   162 
   162 
   163 goal thy "insert (Key K) H = Key `` {K} Un H";
   163 Goal "insert (Key K) H = Key `` {K} Un H";
   164 by (Blast_tac 1);
   164 by (Blast_tac 1);
   165 qed "insert_Key_singleton";
   165 qed "insert_Key_singleton";
   166 
   166 
   167 goal thy "insert (Key K) (Key``KK Un C) = Key `` (insert K KK) Un C";
   167 Goal "insert (Key K) (Key``KK Un C) = Key `` (insert K KK) Un C";
   168 by (Blast_tac 1);
   168 by (Blast_tac 1);
   169 qed "insert_Key_image";
   169 qed "insert_Key_image";
   170 
   170 
   171 (*Reverse the normal simplification of "image" to build up (not break down)
   171 (*Reverse the normal simplification of "image" to build up (not break down)
   172   the set of keys.  Based on analz_image_freshK_ss, but simpler.*)
   172   the set of keys.  Based on analz_image_freshK_ss, but simpler.*)