src/HOL/Auth/TLS.ML
changeset 3683 aafe719dff14
parent 3677 f2569416d18b
child 3685 5b8c0c8f576e
equal deleted inserted replaced
3682:597efdb7decb 3683:aafe719dff14
   142 Addsimps [not_Says_to_self];
   142 Addsimps [not_Says_to_self];
   143 AddSEs   [not_Says_to_self RSN (2, rev_notE)];
   143 AddSEs   [not_Says_to_self RSN (2, rev_notE)];
   144 
   144 
   145 
   145 
   146 (*Induction for regularity theorems.  If induction formula has the form
   146 (*Induction for regularity theorems.  If induction formula has the form
   147    X ~: analz (sees Spy evs) --> ... then it shortens the proof by discarding
   147    X ~: analz (spies evs) --> ... then it shortens the proof by discarding
   148    needless information about analz (insert X (sees Spy evs))  *)
   148    needless information about analz (insert X (spies evs))  *)
   149 fun parts_induct_tac i = 
   149 fun parts_induct_tac i = 
   150     etac tls.induct i
   150     etac tls.induct i
   151     THEN 
   151     THEN 
   152     REPEAT (FIRSTGOAL analz_mono_contra_tac)
   152     REPEAT (FIRSTGOAL analz_mono_contra_tac)
   153     THEN 
   153     THEN 
   154     fast_tac (!claset addss (!simpset)) i THEN
   154     fast_tac (!claset addss (!simpset)) i THEN
   155     ALLGOALS (asm_full_simp_tac (!simpset setloop split_tac [expand_if]));
   155     ALLGOALS (asm_full_simp_tac (!simpset setloop split_tac [expand_if]));
   156 
   156 
   157 
   157 
   158 (** Theorems of the form X ~: parts (sees Spy evs) imply that NOBODY
   158 (** Theorems of the form X ~: parts (spies evs) imply that NOBODY
   159     sends messages containing X! **)
   159     sends messages containing X! **)
   160 
   160 
   161 (*Spy never sees another agent's private key! (unless it's lost at start)*)
   161 (*Spy never sees another agent's private key! (unless it's bad at start)*)
   162 goal thy 
   162 goal thy 
   163  "!!evs. evs : tls ==> (Key (priK A) : parts (sees Spy evs)) = (A : lost)";
   163  "!!evs. evs : tls ==> (Key (priK A) : parts (spies evs)) = (A : bad)";
   164 by (parts_induct_tac 1);
   164 by (parts_induct_tac 1);
   165 by (Fake_parts_insert_tac 1);
   165 by (Fake_parts_insert_tac 1);
   166 qed "Spy_see_priK";
   166 qed "Spy_see_priK";
   167 Addsimps [Spy_see_priK];
   167 Addsimps [Spy_see_priK];
   168 
   168 
   169 goal thy 
   169 goal thy 
   170  "!!evs. evs : tls ==> (Key (priK A) : analz (sees Spy evs)) = (A : lost)";
   170  "!!evs. evs : tls ==> (Key (priK A) : analz (spies evs)) = (A : bad)";
   171 by (auto_tac(!claset addDs [impOfSubs analz_subset_parts], !simpset));
   171 by (auto_tac(!claset addDs [impOfSubs analz_subset_parts], !simpset));
   172 qed "Spy_analz_priK";
   172 qed "Spy_analz_priK";
   173 Addsimps [Spy_analz_priK];
   173 Addsimps [Spy_analz_priK];
   174 
   174 
   175 goal thy  "!!A. [| Key (priK A) : parts (sees Spy evs);       \
   175 goal thy  "!!A. [| Key (priK A) : parts (spies evs);       \
   176 \                  evs : tls |] ==> A:lost";
   176 \                  evs : tls |] ==> A:bad";
   177 by (blast_tac (!claset addDs [Spy_see_priK]) 1);
   177 by (blast_tac (!claset addDs [Spy_see_priK]) 1);
   178 qed "Spy_see_priK_D";
   178 qed "Spy_see_priK_D";
   179 
   179 
   180 bind_thm ("Spy_analz_priK_D", analz_subset_parts RS subsetD RS Spy_see_priK_D);
   180 bind_thm ("Spy_analz_priK_D", analz_subset_parts RS subsetD RS Spy_see_priK_D);
   181 AddSDs [Spy_see_priK_D, Spy_analz_priK_D];
   181 AddSDs [Spy_see_priK_D, Spy_analz_priK_D];
   185   model to include bogus certificates for the agents, but there seems
   185   model to include bogus certificates for the agents, but there seems
   186   little point in doing so: the loss of their private keys is a worse
   186   little point in doing so: the loss of their private keys is a worse
   187   breach of security.*)
   187   breach of security.*)
   188 goalw thy [certificate_def]
   188 goalw thy [certificate_def]
   189  "!!evs. evs : tls     \
   189  "!!evs. evs : tls     \
   190 \        ==> certificate B KB : parts (sees Spy evs) --> KB = pubK B";
   190 \        ==> certificate B KB : parts (spies evs) --> KB = pubK B";
   191 by (parts_induct_tac 1);
   191 by (parts_induct_tac 1);
   192 by (Fake_parts_insert_tac 1);
   192 by (Fake_parts_insert_tac 1);
   193 bind_thm ("Server_cert_pubB", result() RSN (2, rev_mp));
   193 bind_thm ("Server_cert_pubB", result() RSN (2, rev_mp));
   194 
   194 
   195 
   195 
   196 (*Replace key KB in ClientCertKeyEx by (pubK B) *)
   196 (*Replace key KB in ClientCertKeyEx by (pubK B) *)
   197 val ClientCertKeyEx_tac = 
   197 val ClientCertKeyEx_tac = 
   198     forward_tac [Says_imp_sees_Spy RS parts.Inj RS 
   198     forward_tac [Says_imp_spies RS parts.Inj RS 
   199 		 parts.Snd RS parts.Snd RS parts.Snd RS Server_cert_pubB]
   199 		 parts.Snd RS parts.Snd RS parts.Snd RS Server_cert_pubB]
   200     THEN' assume_tac
   200     THEN' assume_tac
   201     THEN' hyp_subst_tac;
   201     THEN' hyp_subst_tac;
   202 
   202 
   203 fun analz_induct_tac i = 
   203 fun analz_induct_tac i = 
   218 
   218 
   219 (*** Hashing of nonces ***)
   219 (*** Hashing of nonces ***)
   220 
   220 
   221 (*Every Nonce that's hashed is already in past traffic.  
   221 (*Every Nonce that's hashed is already in past traffic.  
   222   This event occurs in CERTIFICATE VERIFY*)
   222   This event occurs in CERTIFICATE VERIFY*)
   223 goal thy "!!evs. [| Hash {|Nonce NB, X|} : parts (sees Spy evs);  \
   223 goal thy "!!evs. [| Hash {|Nonce NB, X|} : parts (spies evs);  \
   224 \                   NB ~: range PRF;  evs : tls |]  \
   224 \                   NB ~: range PRF;  evs : tls |]  \
   225 \                ==> Nonce NB : parts (sees Spy evs)";
   225 \                ==> Nonce NB : parts (spies evs)";
   226 by (etac rev_mp 1);
   226 by (etac rev_mp 1);
   227 by (etac rev_mp 1);
   227 by (etac rev_mp 1);
   228 by (parts_induct_tac 1);
   228 by (parts_induct_tac 1);
   229 by (ALLGOALS (asm_simp_tac (!simpset addsimps [parts_insert_sees])));
   229 by (ALLGOALS (asm_simp_tac (!simpset addsimps [parts_insert_spies])));
   230 by (Fake_parts_insert_tac 1);
   230 by (Fake_parts_insert_tac 1);
   231 (*FINISHED messages are trivial because M : range PRF*)
   231 (*FINISHED messages are trivial because M : range PRF*)
   232 by (REPEAT (Blast_tac 2));
   232 by (REPEAT (Blast_tac 2));
   233 (*CERTIFICATE VERIFY is the only interesting case*)
   233 (*CERTIFICATE VERIFY is the only interesting case*)
   234 by (blast_tac (!claset addSEs sees_Spy_partsEs) 1);
   234 by (blast_tac (!claset addSEs spies_partsEs) 1);
   235 qed "Hash_Nonce_CV";
   235 qed "Hash_Nonce_CV";
   236 
   236 
   237 
   237 
   238 goal thy "!!evs. [| Notes A {|Agent B, X|} : set evs;  evs : tls |]  \
   238 goal thy "!!evs. [| Notes A {|Agent B, X|} : set evs;  evs : tls |]  \
   239 \                ==> Crypt (pubK B) X : parts (sees Spy evs)";
   239 \                ==> Crypt (pubK B) X : parts (spies evs)";
   240 by (etac rev_mp 1);
   240 by (etac rev_mp 1);
   241 by (analz_induct_tac 1);
   241 by (analz_induct_tac 1);
   242 by (blast_tac (!claset addIs [parts_insertI]) 1);
   242 by (blast_tac (!claset addIs [parts_insertI]) 1);
   243 qed "Notes_Crypt_parts_sees";
   243 qed "Notes_Crypt_parts_spies";
   244 
   244 
   245 
   245 
   246 (*** Protocol goal: if B receives CERTIFICATE VERIFY, then A sent it ***)
   246 (*** Protocol goal: if B receives CERTIFICATE VERIFY, then A sent it ***)
   247 
   247 
   248 (*B can check A's signature if he has received A's certificate.
   248 (*B can check A's signature if he has received A's certificate.
   249   Perhaps B~=Spy is unnecessary, but there's no obvious proof if the first
   249   Perhaps B~=Spy is unnecessary, but there's no obvious proof if the first
   250   message is Fake.  We don't need guarantees for the Spy anyway.  We must
   250   message is Fake.  We don't need guarantees for the Spy anyway.  We must
   251   assume A~:lost; otherwise, the Spy can forge A's signature.*)
   251   assume A~:bad; otherwise, the Spy can forge A's signature.*)
   252 goal thy
   252 goal thy
   253  "!!evs. [| X = Crypt (priK A)                                        \
   253  "!!evs. [| X = Crypt (priK A)                                        \
   254 \                 (Hash{|Nonce NB, certificate B KB, Nonce PMS|});      \
   254 \                 (Hash{|Nonce NB, certificate B KB, Nonce PMS|});      \
   255 \           evs : tls;  A ~: lost;  B ~= Spy |]                       \
   255 \           evs : tls;  A ~: bad;  B ~= Spy |]                       \
   256 \    ==> Says B A {|Nonce NB, Number SID, Number XB, certificate B KB|}  \
   256 \    ==> Says B A {|Nonce NB, Number SID, Number XB, certificate B KB|}  \
   257 \          : set evs --> \
   257 \          : set evs --> \
   258 \        X : parts (sees Spy evs) --> Says A B X : set evs";
   258 \        X : parts (spies evs) --> Says A B X : set evs";
   259 by (hyp_subst_tac 1);
   259 by (hyp_subst_tac 1);
   260 by (parts_induct_tac 1);
   260 by (parts_induct_tac 1);
   261 by (Fake_parts_insert_tac 1);
   261 by (Fake_parts_insert_tac 1);
   262 (*ServerHello: nonce NB cannot be in X because it's fresh!*)
   262 (*ServerHello: nonce NB cannot be in X because it's fresh!*)
   263 by (blast_tac (!claset addSDs [Hash_Nonce_CV]
   263 by (blast_tac (!claset addSDs [Hash_Nonce_CV]
   264 	               addSEs sees_Spy_partsEs) 1);
   264 	               addSEs spies_partsEs) 1);
   265 qed_spec_mp "TrustCertVerify";
   265 qed_spec_mp "TrustCertVerify";
   266 
   266 
   267 
   267 
   268 (*If CERTIFICATE VERIFY is present then A has chosen PMS.*)
   268 (*If CERTIFICATE VERIFY is present then A has chosen PMS.*)
   269 goal thy
   269 goal thy
   270  "!!evs. [| Crypt (priK A) (Hash{|Nonce NB, certificate B KB, Nonce PMS|})  \
   270  "!!evs. [| Crypt (priK A) (Hash{|Nonce NB, certificate B KB, Nonce PMS|})  \
   271 \             : parts (sees Spy evs);                                \
   271 \             : parts (spies evs);                                \
   272 \           evs : tls;  A ~: lost |]                                      \
   272 \           evs : tls;  A ~: bad |]                                      \
   273 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs";
   273 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs";
   274 be rev_mp 1;
   274 be rev_mp 1;
   275 by (parts_induct_tac 1);
   275 by (parts_induct_tac 1);
   276 by (Fake_parts_insert_tac 1);
   276 by (Fake_parts_insert_tac 1);
   277 qed "UseCertVerify";
   277 qed "UseCertVerify";
   278 
   278 
   279 
   279 
   280 (*No collection of keys can help the spy get new private keys*)
   280 (*No collection of keys can help the spy get new private keys*)
   281 goal thy  
   281 goal thy  
   282  "!!evs. evs : tls ==>                                    \
   282  "!!evs. evs : tls ==>                                    \
   283 \  ALL KK. (Key(priK B) : analz (Key``KK Un (sees Spy evs))) =  \
   283 \  ALL KK. (Key(priK B) : analz (Key``KK Un (spies evs))) =  \
   284 \            (priK B : KK | B : lost)";
   284 \            (priK B : KK | B : bad)";
   285 by (etac tls.induct 1);
   285 by (etac tls.induct 1);
   286 by (ALLGOALS
   286 by (ALLGOALS
   287     (asm_simp_tac (analz_image_keys_ss
   287     (asm_simp_tac (analz_image_keys_ss
   288 		   addsimps (analz_insert_certificate::keys_distinct))));
   288 		   addsimps (analz_insert_certificate::keys_distinct))));
   289 (*Fake*) 
   289 (*Fake*) 
   307 
   307 
   308 (*Knowing some session keys is no help in getting new nonces*)
   308 (*Knowing some session keys is no help in getting new nonces*)
   309 goal thy  
   309 goal thy  
   310  "!!evs. evs : tls ==>                                 \
   310  "!!evs. evs : tls ==>                                 \
   311 \    ALL KK. KK <= range sessionK -->           \
   311 \    ALL KK. KK <= range sessionK -->           \
   312 \            (Nonce N : analz (Key``KK Un (sees Spy evs))) = \
   312 \            (Nonce N : analz (Key``KK Un (spies evs))) = \
   313 \            (Nonce N : analz (sees Spy evs))";
   313 \            (Nonce N : analz (spies evs))";
   314 by (etac tls.induct 1);
   314 by (etac tls.induct 1);
   315 by (ClientCertKeyEx_tac 6);
   315 by (ClientCertKeyEx_tac 6);
   316 by (REPEAT_FIRST (resolve_tac [allI, impI]));
   316 by (REPEAT_FIRST (resolve_tac [allI, impI]));
   317 by (REPEAT_FIRST (rtac lemma));
   317 by (REPEAT_FIRST (rtac lemma));
   318 writeln"SLOW simplification: 55 secs??";
   318 writeln"SLOW simplification: 55 secs??";
   319 (*ClientCertKeyEx is to blame, causing case splits for A, B: lost*)
   319 (*ClientCertKeyEx is to blame, causing case splits for A, B: bad*)
   320 by (ALLGOALS
   320 by (ALLGOALS
   321     (asm_simp_tac (analz_image_keys_ss 
   321     (asm_simp_tac (analz_image_keys_ss 
   322 		   addsimps [range_sessionkeys_not_priK, 
   322 		   addsimps [range_sessionkeys_not_priK, 
   323 			     analz_image_priK, analz_insert_certificate])));
   323 			     analz_image_priK, analz_insert_certificate])));
   324 by (ALLGOALS (asm_simp_tac (!simpset addsimps [insert_absorb])));
   324 by (ALLGOALS (asm_simp_tac (!simpset addsimps [insert_absorb])));
   335 by (Blast_tac 1);
   335 by (Blast_tac 1);
   336 qed "no_Notes_A_PRF";
   336 qed "no_Notes_A_PRF";
   337 Addsimps [no_Notes_A_PRF];
   337 Addsimps [no_Notes_A_PRF];
   338 
   338 
   339 
   339 
   340 goal thy "!!evs. [| Nonce (PRF (PMS,NA,NB)) : parts (sees Spy evs);  \
   340 goal thy "!!evs. [| Nonce (PRF (PMS,NA,NB)) : parts (spies evs);  \
   341 \                   evs : tls |]  \
   341 \                   evs : tls |]  \
   342 \                ==> Nonce PMS : parts (sees Spy evs)";
   342 \                ==> Nonce PMS : parts (spies evs)";
   343 by (etac rev_mp 1);
   343 by (etac rev_mp 1);
   344 by (parts_induct_tac 1);
   344 by (parts_induct_tac 1);
   345 by (ALLGOALS (asm_simp_tac (!simpset addsimps [parts_insert_sees])));
   345 by (ALLGOALS (asm_simp_tac (!simpset addsimps [parts_insert_spies])));
   346 by (Fake_parts_insert_tac 1);
   346 by (Fake_parts_insert_tac 1);
   347 (*Six others, all trivial or by freshness*)
   347 (*Six others, all trivial or by freshness*)
   348 by (REPEAT (blast_tac (!claset addSDs [Notes_Crypt_parts_sees]
   348 by (REPEAT (blast_tac (!claset addSDs [Notes_Crypt_parts_spies]
   349                                addSEs sees_Spy_partsEs) 1));
   349                                addSEs spies_partsEs) 1));
   350 qed "MS_imp_PMS";
   350 qed "MS_imp_PMS";
   351 AddSDs [MS_imp_PMS];
   351 AddSDs [MS_imp_PMS];
   352 
   352 
   353 
   353 
   354 
   354 
   358 
   358 
   359 (*Lemma: those write keys are never sent if M (MASTER SECRET) is secure.  
   359 (*Lemma: those write keys are never sent if M (MASTER SECRET) is secure.  
   360   Converse doesn't hold; betraying M doesn't force the keys to be sent!*)
   360   Converse doesn't hold; betraying M doesn't force the keys to be sent!*)
   361 
   361 
   362 goal thy 
   362 goal thy 
   363  "!!evs. [| Nonce M ~: analz (sees Spy evs);  evs : tls |]   \
   363  "!!evs. [| Nonce M ~: analz (spies evs);  evs : tls |]   \
   364 \        ==> Key (sessionK(b,NA,NB,M)) ~: parts (sees Spy evs)";
   364 \        ==> Key (sessionK(b,NA,NB,M)) ~: parts (spies evs)";
   365 by (etac rev_mp 1);
   365 by (etac rev_mp 1);
   366 by (analz_induct_tac 1);
   366 by (analz_induct_tac 1);
   367 (*SpyKeys*)
   367 (*SpyKeys*)
   368 by (asm_simp_tac (analz_image_keys_ss addsimps [analz_image_keys]) 3);
   368 by (asm_simp_tac (analz_image_keys_ss addsimps [analz_image_keys]) 3);
   369 by (blast_tac (!claset addDs [Says_imp_sees_Spy RS analz.Inj]) 3);
   369 by (blast_tac (!claset addDs [Says_imp_spies RS analz.Inj]) 3);
   370 (*Fake*) 
   370 (*Fake*) 
   371 by (spy_analz_tac 2);
   371 by (spy_analz_tac 2);
   372 (*Base*)
   372 (*Base*)
   373 by (Blast_tac 1);
   373 by (Blast_tac 1);
   374 qed "sessionK_notin_parts";
   374 qed "sessionK_notin_parts";
   383   Nonces don't have to agree, allowing session resumption.
   383   Nonces don't have to agree, allowing session resumption.
   384   Converse doesn't hold; revealing PMS doesn't force the keys to be sent.
   384   Converse doesn't hold; revealing PMS doesn't force the keys to be sent.
   385   They are NOT suitable as safe elim rules.*)
   385   They are NOT suitable as safe elim rules.*)
   386 
   386 
   387 goal thy 
   387 goal thy 
   388  "!!evs. [| Nonce PMS ~: parts (sees Spy evs);  evs : tls |]             \
   388  "!!evs. [| Nonce PMS ~: parts (spies evs);  evs : tls |]             \
   389 \  ==> Crypt (sessionK(b, Na, Nb, PRF(PMS,NA,NB))) Y ~: parts (sees Spy evs)";
   389 \  ==> Crypt (sessionK(b, Na, Nb, PRF(PMS,NA,NB))) Y ~: parts (spies evs)";
   390 by (etac rev_mp 1);
   390 by (etac rev_mp 1);
   391 by (analz_induct_tac 1);
   391 by (analz_induct_tac 1);
   392 (*Fake*)
   392 (*Fake*)
   393 by (asm_simp_tac (!simpset addsimps [parts_insert_sees]) 2);
   393 by (asm_simp_tac (!simpset addsimps [parts_insert_spies]) 2);
   394 by (Fake_parts_insert_tac 2);
   394 by (Fake_parts_insert_tac 2);
   395 (*Base, ClientFinished, ServerFinished: trivial, e.g. by freshness*)
   395 (*Base, ClientFinished, ServerFinished: trivial, e.g. by freshness*)
   396 by (REPEAT 
   396 by (REPEAT 
   397     (blast_tac (!claset addSDs [Notes_Crypt_parts_sees]
   397     (blast_tac (!claset addSDs [Notes_Crypt_parts_spies]
   398                         addSEs sees_Spy_partsEs) 1));
   398                         addSEs spies_partsEs) 1));
   399 qed "Crypt_sessionK_notin_parts";
   399 qed "Crypt_sessionK_notin_parts";
   400 
   400 
   401 Addsimps [Crypt_sessionK_notin_parts];
   401 Addsimps [Crypt_sessionK_notin_parts];
   402 AddEs [Crypt_sessionK_notin_parts RSN (2, rev_notE)];
   402 AddEs [Crypt_sessionK_notin_parts RSN (2, rev_notE)];
   403 
   403 
   413 
   413 
   414 (*** Unicity results for PMS, the pre-master-secret ***)
   414 (*** Unicity results for PMS, the pre-master-secret ***)
   415 
   415 
   416 (*PMS determines B.  Proof borrowed from NS_Public/unique_NA and from Yahalom*)
   416 (*PMS determines B.  Proof borrowed from NS_Public/unique_NA and from Yahalom*)
   417 goal thy 
   417 goal thy 
   418  "!!evs. [| Nonce PMS ~: analz (sees Spy evs);  evs : tls |]   \
   418  "!!evs. [| Nonce PMS ~: analz (spies evs);  evs : tls |]   \
   419 \        ==> EX B'. ALL B.   \
   419 \        ==> EX B'. ALL B.   \
   420 \              Crypt (pubK B) (Nonce PMS) : parts (sees Spy evs) --> B=B'";
   420 \              Crypt (pubK B) (Nonce PMS) : parts (spies evs) --> B=B'";
   421 by (etac rev_mp 1);
   421 by (etac rev_mp 1);
   422 by (parts_induct_tac 1);
   422 by (parts_induct_tac 1);
   423 by (Fake_parts_insert_tac 1);
   423 by (Fake_parts_insert_tac 1);
   424 (*ClientCertKeyEx*)
   424 (*ClientCertKeyEx*)
   425 by (ClientCertKeyEx_tac 1);
   425 by (ClientCertKeyEx_tac 1);
   427 by (expand_case_tac "PMS = ?y" 1 THEN
   427 by (expand_case_tac "PMS = ?y" 1 THEN
   428     blast_tac (!claset addSEs partsEs) 1);
   428     blast_tac (!claset addSEs partsEs) 1);
   429 val lemma = result();
   429 val lemma = result();
   430 
   430 
   431 goal thy 
   431 goal thy 
   432  "!!evs. [| Crypt(pubK B)  (Nonce PMS) : parts (sees Spy evs); \
   432  "!!evs. [| Crypt(pubK B)  (Nonce PMS) : parts (spies evs); \
   433 \           Crypt(pubK B') (Nonce PMS) : parts (sees Spy evs); \
   433 \           Crypt(pubK B') (Nonce PMS) : parts (spies evs); \
   434 \           Nonce PMS ~: analz (sees Spy evs);                 \
   434 \           Nonce PMS ~: analz (spies evs);                 \
   435 \           evs : tls |]                                          \
   435 \           evs : tls |]                                          \
   436 \        ==> B=B'";
   436 \        ==> B=B'";
   437 by (prove_unique_tac lemma 1);
   437 by (prove_unique_tac lemma 1);
   438 qed "unique_PMS";
   438 qed "unique_PMS";
   439 
   439 
   440 
   440 
   441 (*In A's internal Note, PMS determines A and B.*)
   441 (*In A's internal Note, PMS determines A and B.*)
   442 goal thy 
   442 goal thy 
   443  "!!evs. [| Nonce PMS ~: analz (sees Spy evs);  evs : tls |]            \
   443  "!!evs. [| Nonce PMS ~: analz (spies evs);  evs : tls |]            \
   444 \ ==> EX A' B'. ALL A B.                                                   \
   444 \ ==> EX A' B'. ALL A B.                                                   \
   445 \        Notes A {|Agent B, Nonce PMS|} : set evs --> A=A' & B=B'";
   445 \        Notes A {|Agent B, Nonce PMS|} : set evs --> A=A' & B=B'";
   446 by (etac rev_mp 1);
   446 by (etac rev_mp 1);
   447 by (parts_induct_tac 1);
   447 by (parts_induct_tac 1);
   448 by (asm_simp_tac (!simpset addsimps [all_conj_distrib]) 1);
   448 by (asm_simp_tac (!simpset addsimps [all_conj_distrib]) 1);
   449 (*ClientCertKeyEx: if PMS is fresh, then it can't appear in Notes A X.*)
   449 (*ClientCertKeyEx: if PMS is fresh, then it can't appear in Notes A X.*)
   450 by (expand_case_tac "PMS = ?y" 1 THEN
   450 by (expand_case_tac "PMS = ?y" 1 THEN
   451     blast_tac (!claset addSDs [Notes_Crypt_parts_sees] addSEs partsEs) 1);
   451     blast_tac (!claset addSDs [Notes_Crypt_parts_spies] addSEs partsEs) 1);
   452 val lemma = result();
   452 val lemma = result();
   453 
   453 
   454 goal thy 
   454 goal thy 
   455  "!!evs. [| Notes A  {|Agent B,  Nonce PMS|} : set evs;  \
   455  "!!evs. [| Notes A  {|Agent B,  Nonce PMS|} : set evs;  \
   456 \           Notes A' {|Agent B', Nonce PMS|} : set evs;  \
   456 \           Notes A' {|Agent B', Nonce PMS|} : set evs;  \
   457 \           Nonce PMS ~: analz (sees Spy evs);      \
   457 \           Nonce PMS ~: analz (spies evs);      \
   458 \           evs : tls |]                               \
   458 \           evs : tls |]                               \
   459 \        ==> A=A' & B=B'";
   459 \        ==> A=A' & B=B'";
   460 by (prove_unique_tac lemma 1);
   460 by (prove_unique_tac lemma 1);
   461 qed "Notes_unique_PMS";
   461 qed "Notes_unique_PMS";
   462 
   462 
   463 
   463 
   464 
   464 
   465 (*If A sends ClientCertKeyEx to an honest B, then the PMS will stay secret.*)
   465 (*If A sends ClientCertKeyEx to an honest B, then the PMS will stay secret.*)
   466 goal thy
   466 goal thy
   467  "!!evs. [| evs : tls;  A ~: lost;  B ~: lost |]           \
   467  "!!evs. [| evs : tls;  A ~: bad;  B ~: bad |]           \
   468 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs  -->   \
   468 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs  -->   \
   469 \            Nonce PMS ~: analz (sees Spy evs)";
   469 \            Nonce PMS ~: analz (spies evs)";
   470 by (analz_induct_tac 1);   (*30 seconds???*)
   470 by (analz_induct_tac 1);   (*30 seconds???*)
   471 (*ClientAccepts and ServerAccepts: because PMS ~: range PRF*)
   471 (*ClientAccepts and ServerAccepts: because PMS ~: range PRF*)
   472 by (REPEAT (fast_tac (!claset addss (!simpset)) 6));
   472 by (REPEAT (fast_tac (!claset addss (!simpset)) 6));
   473 (*ServerHello and ClientCertKeyEx: mostly freshness reasoning*)
   473 (*ServerHello and ClientCertKeyEx: mostly freshness reasoning*)
   474 by (REPEAT (blast_tac (!claset addSEs partsEs
   474 by (REPEAT (blast_tac (!claset addSEs partsEs
   475 			       addDs  [Notes_Crypt_parts_sees,
   475 			       addDs  [Notes_Crypt_parts_spies,
   476 				       impOfSubs analz_subset_parts,
   476 				       impOfSubs analz_subset_parts,
   477 				       Says_imp_sees_Spy RS analz.Inj]) 4));
   477 				       Says_imp_spies RS analz.Inj]) 4));
   478 (*ClientHello*)
   478 (*ClientHello*)
   479 by (blast_tac (!claset addSDs [Notes_Crypt_parts_sees]
   479 by (blast_tac (!claset addSDs [Notes_Crypt_parts_spies]
   480                                addSEs sees_Spy_partsEs) 3);
   480                                addSEs spies_partsEs) 3);
   481 (*SpyKeys*)
   481 (*SpyKeys*)
   482 by (asm_simp_tac (analz_image_keys_ss addsimps [analz_image_keys]) 2);
   482 by (asm_simp_tac (analz_image_keys_ss addsimps [analz_image_keys]) 2);
   483 by (fast_tac (!claset addss (!simpset)) 2);
   483 by (fast_tac (!claset addss (!simpset)) 2);
   484 (*Fake*)
   484 (*Fake*)
   485 by (spy_analz_tac 1);
   485 by (spy_analz_tac 1);
   490 
   490 
   491 
   491 
   492 (*If A sends ClientCertKeyEx to an honest B, then the MASTER SECRET
   492 (*If A sends ClientCertKeyEx to an honest B, then the MASTER SECRET
   493   will stay secret.*)
   493   will stay secret.*)
   494 goal thy
   494 goal thy
   495  "!!evs. [| evs : tls;  A ~: lost;  B ~: lost |]           \
   495  "!!evs. [| evs : tls;  A ~: bad;  B ~: bad |]           \
   496 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs  -->   \
   496 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs  -->   \
   497 \            Nonce (PRF(PMS,NA,NB)) ~: analz (sees Spy evs)";
   497 \            Nonce (PRF(PMS,NA,NB)) ~: analz (spies evs)";
   498 by (analz_induct_tac 1);   (*35 seconds*)
   498 by (analz_induct_tac 1);   (*35 seconds*)
   499 (*ClientAccepts and ServerAccepts: because PMS was already visible*)
   499 (*ClientAccepts and ServerAccepts: because PMS was already visible*)
   500 by (REPEAT (blast_tac (!claset addDs [Spy_not_see_PMS, 
   500 by (REPEAT (blast_tac (!claset addDs [Spy_not_see_PMS, 
   501 				      Says_imp_sees_Spy RS analz.Inj,
   501 				      Says_imp_spies RS analz.Inj,
   502 				      Notes_imp_sees_Spy RS analz.Inj]) 6));
   502 				      Notes_imp_spies RS analz.Inj]) 6));
   503 (*ClientHello*)
   503 (*ClientHello*)
   504 by (Blast_tac 3);
   504 by (Blast_tac 3);
   505 (*SpyKeys: by secrecy of the PMS, Spy cannot make the MS*)
   505 (*SpyKeys: by secrecy of the PMS, Spy cannot make the MS*)
   506 by (asm_simp_tac (analz_image_keys_ss addsimps [analz_image_keys]) 2);
   506 by (asm_simp_tac (analz_image_keys_ss addsimps [analz_image_keys]) 2);
   507 by (blast_tac (!claset addSDs [Spy_not_see_PMS, 
   507 by (blast_tac (!claset addSDs [Spy_not_see_PMS, 
   508 			       Says_imp_sees_Spy RS analz.Inj]) 2);
   508 			       Says_imp_spies RS analz.Inj]) 2);
   509 (*Fake*)
   509 (*Fake*)
   510 by (spy_analz_tac 1);
   510 by (spy_analz_tac 1);
   511 (*ServerHello and ClientCertKeyEx: mostly freshness reasoning*)
   511 (*ServerHello and ClientCertKeyEx: mostly freshness reasoning*)
   512 by (REPEAT (blast_tac (!claset addSEs partsEs
   512 by (REPEAT (blast_tac (!claset addSEs partsEs
   513 			       addDs  [Notes_Crypt_parts_sees,
   513 			       addDs  [Notes_Crypt_parts_spies,
   514 				       impOfSubs analz_subset_parts,
   514 				       impOfSubs analz_subset_parts,
   515 				       Says_imp_sees_Spy RS analz.Inj]) 1));
   515 				       Says_imp_spies RS analz.Inj]) 1));
   516 bind_thm ("Spy_not_see_MS", result() RSN (2, rev_mp));
   516 bind_thm ("Spy_not_see_MS", result() RSN (2, rev_mp));
   517 
   517 
   518 
   518 
   519 (*** Protocol goals: if A receives SERVER FINISHED, then B is present 
   519 (*** Protocol goals: if A receives SERVER FINISHED, then B is present 
   520      and has used the quoted values XA, XB, etc.  Note that it is up to A
   520      and has used the quoted values XA, XB, etc.  Note that it is up to A
   526  "!!evs. [| X = Crypt (serverK(Na,Nb,M))                  \
   526  "!!evs. [| X = Crypt (serverK(Na,Nb,M))                  \
   527 \                 (Hash{|Nonce M, Number SID,             \
   527 \                 (Hash{|Nonce M, Number SID,             \
   528 \                        Nonce NA, Number XA, Agent A,    \
   528 \                        Nonce NA, Number XA, Agent A,    \
   529 \                        Nonce NB, Number XB, Agent B|}); \
   529 \                        Nonce NB, Number XB, Agent B|}); \
   530 \           M = PRF(PMS,NA,NB);                           \
   530 \           M = PRF(PMS,NA,NB);                           \
   531 \           evs : tls;  A ~: lost;  B ~: lost |]          \
   531 \           evs : tls;  A ~: bad;  B ~: bad |]          \
   532 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs --> \
   532 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs --> \
   533 \        X : parts (sees Spy evs) --> Says B A X : set evs";
   533 \        X : parts (spies evs) --> Says B A X : set evs";
   534 by (hyp_subst_tac 1);
   534 by (hyp_subst_tac 1);
   535 by (analz_induct_tac 1);	(*16 seconds*)
   535 by (analz_induct_tac 1);	(*16 seconds*)
   536 (*ClientCertKeyEx*)
   536 (*ClientCertKeyEx*)
   537 by (Blast_tac 2);
   537 by (Blast_tac 2);
   538 (*Fake: the Spy doesn't have the critical session key!*)
   538 (*Fake: the Spy doesn't have the critical session key!*)
   539 by (REPEAT (rtac impI 1));
   539 by (REPEAT (rtac impI 1));
   540 by (subgoal_tac "Key (serverK(Na,Nb,PRF(PMS,NA,NB))) ~: analz(sees Spy evsa)" 1);
   540 by (subgoal_tac "Key (serverK(Na,Nb,PRF(PMS,NA,NB))) ~: analz(spies evsa)" 1);
   541 by (asm_simp_tac (!simpset addsimps [Spy_not_see_MS, 
   541 by (asm_simp_tac (!simpset addsimps [Spy_not_see_MS, 
   542 				     not_parts_not_analz]) 2);
   542 				     not_parts_not_analz]) 2);
   543 by (Fake_parts_insert_tac 1);
   543 by (Fake_parts_insert_tac 1);
   544 qed_spec_mp "TrustServerFinished";
   544 qed_spec_mp "TrustServerFinished";
   545 
   545 
   548   We don't assume B has received CERTIFICATE VERIFY, and an intruder could
   548   We don't assume B has received CERTIFICATE VERIFY, and an intruder could
   549   have changed A's identity in all other messages, so we can't be sure
   549   have changed A's identity in all other messages, so we can't be sure
   550   that B sends his message to A.  If CLIENT KEY EXCHANGE were augmented
   550   that B sends his message to A.  If CLIENT KEY EXCHANGE were augmented
   551   to bind A's identity with M, then we could replace A' by A below.*)
   551   to bind A's identity with M, then we could replace A' by A below.*)
   552 goal thy
   552 goal thy
   553  "!!evs. [| evs : tls;  A ~: lost;  B ~: lost;                 \
   553  "!!evs. [| evs : tls;  A ~: bad;  B ~: bad;                 \
   554 \           M = PRF(PMS,NA,NB) |]            \
   554 \           M = PRF(PMS,NA,NB) |]            \
   555 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs -->              \
   555 \        ==> Notes A {|Agent B, Nonce PMS|} : set evs -->              \
   556 \            Crypt (serverK(Na,Nb,M)) Y : parts (sees Spy evs)  -->  \
   556 \            Crypt (serverK(Na,Nb,M)) Y : parts (spies evs)  -->  \
   557 \            (EX A'. Says B A' (Crypt (serverK(Na,Nb,M)) Y) : set evs)";
   557 \            (EX A'. Says B A' (Crypt (serverK(Na,Nb,M)) Y) : set evs)";
   558 by (hyp_subst_tac 1);
   558 by (hyp_subst_tac 1);
   559 by (analz_induct_tac 1);	(*12 seconds*)
   559 by (analz_induct_tac 1);	(*12 seconds*)
   560 by (REPEAT_FIRST (rtac impI));
   560 by (REPEAT_FIRST (rtac impI));
   561 (*ClientCertKeyEx*)
   561 (*ClientCertKeyEx*)
   562 by (Blast_tac 2);
   562 by (Blast_tac 2);
   563 (*Fake: the Spy doesn't have the critical session key!*)
   563 (*Fake: the Spy doesn't have the critical session key!*)
   564 by (subgoal_tac "Key (serverK(Na,Nb,PRF(PMS,NA,NB))) ~: analz(sees Spy evsa)" 1);
   564 by (subgoal_tac "Key (serverK(Na,Nb,PRF(PMS,NA,NB))) ~: analz(spies evsa)" 1);
   565 by (asm_simp_tac (!simpset addsimps [Spy_not_see_MS, 
   565 by (asm_simp_tac (!simpset addsimps [Spy_not_see_MS, 
   566 				     not_parts_not_analz]) 2);
   566 				     not_parts_not_analz]) 2);
   567 by (Fake_parts_insert_tac 1);
   567 by (Fake_parts_insert_tac 1);
   568 (*ServerFinished.  If the message is old then apply induction hypothesis...*)
   568 (*ServerFinished.  If the message is old then apply induction hypothesis...*)
   569 by (rtac conjI 1 THEN Blast_tac 2);
   569 by (rtac conjI 1 THEN Blast_tac 2);
   570 (*...otherwise delete induction hyp and use unicity of PMS.*)
   570 (*...otherwise delete induction hyp and use unicity of PMS.*)
   571 by (thin_tac "?PP-->?QQ" 1);
   571 by (thin_tac "?PP-->?QQ" 1);
   572 by (Step_tac 1);
   572 by (Step_tac 1);
   573 by (subgoal_tac "Nonce PMS ~: analz(sees Spy evsSF)" 1);
   573 by (subgoal_tac "Nonce PMS ~: analz(spies evsSF)" 1);
   574 by (asm_simp_tac (!simpset addsimps [Spy_not_see_PMS]) 2);
   574 by (asm_simp_tac (!simpset addsimps [Spy_not_see_PMS]) 2);
   575 by (blast_tac (!claset addSEs [MPair_parts]
   575 by (blast_tac (!claset addSEs [MPair_parts]
   576 		       addDs  [Notes_Crypt_parts_sees,
   576 		       addDs  [Notes_Crypt_parts_spies,
   577 			       Says_imp_sees_Spy RS parts.Inj,
   577 			       Says_imp_spies RS parts.Inj,
   578 			       unique_PMS]) 1);
   578 			       unique_PMS]) 1);
   579 qed_spec_mp "TrustServerMsg";
   579 qed_spec_mp "TrustServerMsg";
   580 
   580 
   581 
   581 
   582 (*** Protocol goal: if B receives any message encrypted with clientK
   582 (*** Protocol goal: if B receives any message encrypted with clientK
   583      then A has sent it, ASSUMING that A chose PMS.  Authentication is
   583      then A has sent it, ASSUMING that A chose PMS.  Authentication is
   584      assumed here; B cannot verify it.  But if the message is
   584      assumed here; B cannot verify it.  But if the message is
   585      CLIENT FINISHED, then B can then check the quoted values XA, XB, etc.
   585      CLIENT FINISHED, then B can then check the quoted values XA, XB, etc.
   586 ***)
   586 ***)
   587 goal thy
   587 goal thy
   588  "!!evs. [| evs : tls;  A ~: lost;  B ~: lost |]                         \
   588  "!!evs. [| evs : tls;  A ~: bad;  B ~: bad |]                         \
   589 \  ==> Notes A {|Agent B, Nonce PMS|} : set evs -->                  \
   589 \  ==> Notes A {|Agent B, Nonce PMS|} : set evs -->                  \
   590 \      Crypt (clientK(Na,Nb,PRF(PMS,NA,NB))) Y : parts (sees Spy evs) -->  \
   590 \      Crypt (clientK(Na,Nb,PRF(PMS,NA,NB))) Y : parts (spies evs) -->  \
   591 \      Says A B (Crypt (clientK(Na,Nb,PRF(PMS,NA,NB))) Y) : set evs";
   591 \      Says A B (Crypt (clientK(Na,Nb,PRF(PMS,NA,NB))) Y) : set evs";
   592 by (analz_induct_tac 1);	(*13 seconds*)
   592 by (analz_induct_tac 1);	(*13 seconds*)
   593 by (REPEAT_FIRST (rtac impI));
   593 by (REPEAT_FIRST (rtac impI));
   594 (*ClientCertKeyEx*)
   594 (*ClientCertKeyEx*)
   595 by (Blast_tac 2);
   595 by (Blast_tac 2);
   596 (*Fake: the Spy doesn't have the critical session key!*)
   596 (*Fake: the Spy doesn't have the critical session key!*)
   597 by (subgoal_tac "Key (clientK(Na,Nb,PRF(PMS,NA,NB))) ~: analz(sees Spy evsa)" 1);
   597 by (subgoal_tac "Key (clientK(Na,Nb,PRF(PMS,NA,NB))) ~: analz(spies evsa)" 1);
   598 by (asm_simp_tac (!simpset addsimps [Spy_not_see_MS, 
   598 by (asm_simp_tac (!simpset addsimps [Spy_not_see_MS, 
   599 				     not_parts_not_analz]) 2);
   599 				     not_parts_not_analz]) 2);
   600 by (Fake_parts_insert_tac 1);
   600 by (Fake_parts_insert_tac 1);
   601 (*ClientFinished.  If the message is old then apply induction hypothesis...*)
   601 (*ClientFinished.  If the message is old then apply induction hypothesis...*)
   602 by (step_tac (!claset delrules [conjI]) 1);
   602 by (step_tac (!claset delrules [conjI]) 1);
   603 by (subgoal_tac "Nonce PMS ~: analz (sees Spy evsCF)" 1);
   603 by (subgoal_tac "Nonce PMS ~: analz (spies evsCF)" 1);
   604 by (asm_simp_tac (!simpset addsimps [Spy_not_see_PMS]) 2);
   604 by (asm_simp_tac (!simpset addsimps [Spy_not_see_PMS]) 2);
   605 by (blast_tac (!claset addSEs [MPair_parts]
   605 by (blast_tac (!claset addSEs [MPair_parts]
   606 		       addDs  [Notes_unique_PMS]) 1);
   606 		       addDs  [Notes_unique_PMS]) 1);
   607 qed_spec_mp "TrustClientMsg";
   607 qed_spec_mp "TrustClientMsg";
   608 
   608 
   616 \           Says B  A {|Nonce NB, Number SID, Number XB, certificate B KB|}  \
   616 \           Says B  A {|Nonce NB, Number SID, Number XB, certificate B KB|}  \
   617 \             : set evs;                                                  \
   617 \             : set evs;                                                  \
   618 \           Says A'' B (Crypt (priK A)                                    \
   618 \           Says A'' B (Crypt (priK A)                                    \
   619 \                       (Hash{|Nonce NB, certificate B KB, Nonce PMS|}))  \
   619 \                       (Hash{|Nonce NB, certificate B KB, Nonce PMS|}))  \
   620 \             : set evs;                                                  \
   620 \             : set evs;                                                  \
   621 \        evs : tls;  A ~: lost;  B ~: lost |]                             \
   621 \        evs : tls;  A ~: bad;  B ~: bad |]                             \
   622 \     ==> Says A B (Crypt (clientK(Na,Nb,PRF(PMS,NA,NB))) Y) : set evs";
   622 \     ==> Says A B (Crypt (clientK(Na,Nb,PRF(PMS,NA,NB))) Y) : set evs";
   623 by (blast_tac (!claset addSIs [TrustClientMsg, UseCertVerify]
   623 by (blast_tac (!claset addSIs [TrustClientMsg, UseCertVerify]
   624                        addDs  [Says_imp_sees_Spy RS parts.Inj]) 1);
   624                        addDs  [Says_imp_spies RS parts.Inj]) 1);
   625 qed "AuthClientFinished";
   625 qed "AuthClientFinished";