src/HOL/Auth/TLS.ML
author paulson
Thu Sep 23 13:06:31 1999 +0200 (1999-09-23)
changeset 7584 5be4bb8e4e3f
parent 7057 b9ddbb925939
child 8054 2ce57ef2a4aa
permissions -rw-r--r--
tidied; added lemma restrict_to_left
paulson@3474
     1
(*  Title:      HOL/Auth/TLS
paulson@3474
     2
    ID:         $Id$
paulson@3474
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
paulson@3474
     4
    Copyright   1997  University of Cambridge
paulson@3474
     5
paulson@3480
     6
Protocol goals: 
paulson@3480
     7
* M, serverK(NA,NB,M) and clientK(NA,NB,M) will be known only to the two
paulson@3480
     8
     parties (though A is not necessarily authenticated).
paulson@3480
     9
paulson@3685
    10
* B upon receiving CertVerify knows that A is present (But this
paulson@3480
    11
    message is optional!)
paulson@3474
    12
paulson@3685
    13
* A upon receiving ServerFinished knows that B is present
paulson@3480
    14
paulson@3480
    15
* Each party who has received a FINISHED message can trust that the other
paulson@3729
    16
  party agrees on all message components, including PA and PB (thus foiling
paulson@3480
    17
  rollback attacks).
paulson@3474
    18
*)
paulson@3474
    19
paulson@5433
    20
AddEs spies_partsEs;
paulson@5433
    21
AddDs [impOfSubs analz_subset_parts];
paulson@5433
    22
AddDs [impOfSubs Fake_parts_insert];
paulson@5433
    23
paulson@3772
    24
(*Automatically unfold the definition of "certificate"*)
paulson@3772
    25
Addsimps [certificate_def];
paulson@3480
    26
paulson@3474
    27
(*Injectiveness of key-generating functions*)
paulson@3677
    28
AddIffs [inj_PRF RS inj_eq, inj_sessionK RS inj_eq];
paulson@3474
    29
paulson@3677
    30
(* invKey(sessionK x) = sessionK x*)
paulson@3677
    31
Addsimps [isSym_sessionK, rewrite_rule [isSymKey_def] isSym_sessionK];
paulson@3480
    32
paulson@3474
    33
paulson@3474
    34
(*** clientK and serverK make symmetric keys; no clashes with pubK or priK ***)
paulson@3474
    35
paulson@5076
    36
Goal "pubK A ~= sessionK arg";
wenzelm@4423
    37
by (rtac notI 1);
paulson@3474
    38
by (dres_inst_tac [("f","isSymKey")] arg_cong 1);
paulson@3474
    39
by (Full_simp_tac 1);
paulson@3677
    40
qed "pubK_neq_sessionK";
paulson@3474
    41
paulson@5076
    42
Goal "priK A ~= sessionK arg";
wenzelm@4423
    43
by (rtac notI 1);
paulson@3474
    44
by (dres_inst_tac [("f","isSymKey")] arg_cong 1);
paulson@3474
    45
by (Full_simp_tac 1);
paulson@3677
    46
qed "priK_neq_sessionK";
paulson@3474
    47
paulson@3677
    48
val keys_distinct = [pubK_neq_sessionK, priK_neq_sessionK];
paulson@3515
    49
AddIffs (keys_distinct @ (keys_distinct RL [not_sym]));
paulson@3474
    50
paulson@3474
    51
paulson@3474
    52
(**** Protocol Proofs ****)
paulson@3474
    53
paulson@3772
    54
(*Possibility properties state that some traces run the protocol to the end.
paulson@3772
    55
  Four paths and 12 rules are considered.*)
paulson@3474
    56
paulson@3672
    57
paulson@3772
    58
(** These proofs assume that the Nonce_supply nonces 
paulson@3672
    59
	(which have the form  @ N. Nonce N ~: used evs)
paulson@3772
    60
    lie outside the range of PRF.  It seems reasonable, but as it is needed
paulson@3772
    61
    only for the possibility theorems, it is not taken as an axiom.
paulson@3672
    62
**)
paulson@3672
    63
paulson@3672
    64
paulson@3685
    65
(*Possibility property ending with ClientAccepts.*)
paulson@5114
    66
Goal "[| ALL evs. (@ N. Nonce N ~: used evs) ~: range PRF;  \
paulson@5114
    67
\        A ~= B |]            \
paulson@5433
    68
\     ==> EX SID M. EX evs: tls.    \
paulson@5433
    69
\          Notes A {|Number SID, Agent A, Agent B, Nonce M|} : set evs";
paulson@3474
    70
by (REPEAT (resolve_tac [exI,bexI] 1));
paulson@3745
    71
by (rtac (tls.Nil RS tls.ClientHello RS tls.ServerHello RS tls.Certificate RS
paulson@3745
    72
	  tls.ClientKeyExch RS tls.ClientFinished RS tls.ServerFinished RS
paulson@3745
    73
	  tls.ClientAccepts) 2);
paulson@3474
    74
by possibility_tac;
paulson@3672
    75
by (REPEAT (Blast_tac 1));
paulson@3474
    76
result();
paulson@3474
    77
paulson@3685
    78
(*And one for ServerAccepts.  Either FINISHED message may come first.*)
paulson@5114
    79
Goal "[| ALL evs. (@ N. Nonce N ~: used evs) ~: range PRF;  \
paulson@5114
    80
\        A ~= B |]                        \
paulson@5433
    81
\     ==> EX SID NA PA NB PB M. EX evs: tls.    \
paulson@5433
    82
\          Notes B {|Number SID, Agent A, Agent B, Nonce M|} : set evs";
paulson@3474
    83
by (REPEAT (resolve_tac [exI,bexI] 1));
paulson@3745
    84
by (rtac (tls.Nil RS tls.ClientHello RS tls.ServerHello RS tls.Certificate RS
paulson@3745
    85
	  tls.ClientKeyExch RS tls.ServerFinished RS tls.ClientFinished RS
paulson@3745
    86
	  tls.ServerAccepts) 2);
paulson@3474
    87
by possibility_tac;
paulson@3672
    88
by (REPEAT (Blast_tac 1));
paulson@3474
    89
result();
paulson@3474
    90
paulson@3474
    91
(*Another one, for CertVerify (which is optional)*)
paulson@5114
    92
Goal "[| ALL evs. (@ N. Nonce N ~: used evs) ~: range PRF;  \
paulson@5114
    93
\        A ~= B |]                       \
paulson@3760
    94
\  ==> EX NB PMS. EX evs: tls.   \
paulson@3729
    95
\  Says A B (Crypt (priK A) (Hash{|Nonce NB, Agent B, Nonce PMS|})) : set evs";
paulson@3474
    96
by (REPEAT (resolve_tac [exI,bexI] 1));
paulson@3745
    97
by (rtac (tls.Nil RS tls.ClientHello RS tls.ServerHello RS tls.Certificate RS
paulson@3745
    98
	  tls.ClientKeyExch RS tls.CertVerify) 2);
paulson@3474
    99
by possibility_tac;
paulson@3672
   100
by (REPEAT (Blast_tac 1));
paulson@3474
   101
result();
paulson@3474
   102
paulson@3685
   103
(*Another one, for session resumption (both ServerResume and ClientResume) *)
paulson@5114
   104
Goal "[| evs0 : tls;     \
paulson@5114
   105
\        Notes A {|Number SID, Agent A, Agent B, Nonce M|} : set evs0; \
paulson@5114
   106
\        Notes B {|Number SID, Agent A, Agent B, Nonce M|} : set evs0; \
paulson@5114
   107
\        ALL evs. (@ N. Nonce N ~: used evs) ~: range PRF;  \
paulson@5433
   108
\        A ~= B |] \
paulson@5433
   109
\     ==> EX NA PA NB PB X. EX evs: tls.    \
paulson@5433
   110
\           X = Hash{|Number SID, Nonce M,             \
paulson@5433
   111
\                     Nonce NA, Number PA, Agent A,      \
paulson@5433
   112
\                     Nonce NB, Number PB, Agent B|}  &  \
paulson@5433
   113
\           Says A B (Crypt (clientK(NA,NB,M)) X) : set evs  &  \
paulson@5433
   114
\           Says B A (Crypt (serverK(NA,NB,M)) X) : set evs";
paulson@3685
   115
by (REPEAT (resolve_tac [exI,bexI] 1));
paulson@3745
   116
by (etac (tls.ClientHello RS tls.ServerHello RS tls.ServerResume RS 
paulson@3745
   117
	  tls.ClientResume) 2);
paulson@3685
   118
by possibility_tac;
paulson@3685
   119
by (REPEAT (Blast_tac 1));
paulson@3685
   120
result();
paulson@3685
   121
paulson@3685
   122
paulson@3474
   123
paulson@3474
   124
(**** Inductive proofs about tls ****)
paulson@3474
   125
paulson@3474
   126
paulson@3519
   127
(*Induction for regularity theorems.  If induction formula has the form
paulson@3683
   128
   X ~: analz (spies evs) --> ... then it shortens the proof by discarding
paulson@3683
   129
   needless information about analz (insert X (spies evs))  *)
paulson@3519
   130
fun parts_induct_tac i = 
paulson@3519
   131
    etac tls.induct i
paulson@3519
   132
    THEN 
paulson@3519
   133
    REPEAT (FIRSTGOAL analz_mono_contra_tac)
paulson@3519
   134
    THEN 
wenzelm@4091
   135
    fast_tac (claset() addss (simpset())) i THEN
nipkow@4686
   136
    ALLGOALS Asm_simp_tac;
paulson@3519
   137
paulson@3519
   138
paulson@3683
   139
(** Theorems of the form X ~: parts (spies evs) imply that NOBODY
paulson@3474
   140
    sends messages containing X! **)
paulson@3474
   141
paulson@3683
   142
(*Spy never sees another agent's private key! (unless it's bad at start)*)
paulson@5114
   143
Goal "evs : tls ==> (Key (priK A) : parts (spies evs)) = (A : bad)";
paulson@3519
   144
by (parts_induct_tac 1);
paulson@5433
   145
by (Blast_tac 1);
paulson@3474
   146
qed "Spy_see_priK";
paulson@3474
   147
Addsimps [Spy_see_priK];
paulson@3474
   148
paulson@5114
   149
Goal "evs : tls ==> (Key (priK A) : analz (spies evs)) = (A : bad)";
paulson@5433
   150
by Auto_tac;
paulson@3474
   151
qed "Spy_analz_priK";
paulson@3474
   152
Addsimps [Spy_analz_priK];
paulson@3474
   153
paulson@4472
   154
AddSDs [Spy_see_priK RSN (2, rev_iffD1), 
paulson@4472
   155
	Spy_analz_priK RSN (2, rev_iffD1)];
paulson@3474
   156
paulson@3474
   157
paulson@3515
   158
(*This lemma says that no false certificates exist.  One might extend the
paulson@3519
   159
  model to include bogus certificates for the agents, but there seems
paulson@3515
   160
  little point in doing so: the loss of their private keys is a worse
paulson@3515
   161
  breach of security.*)
paulson@5076
   162
Goalw [certificate_def]
paulson@5359
   163
    "[| certificate B KB : parts (spies evs);  evs : tls |] ==> pubK B = KB";
paulson@3772
   164
by (etac rev_mp 1);
paulson@3519
   165
by (parts_induct_tac 1);
paulson@5433
   166
by (Blast_tac 1);
paulson@3772
   167
qed "certificate_valid";
paulson@3515
   168
paulson@3515
   169
paulson@3745
   170
(*Replace key KB in ClientKeyExch by (pubK B) *)
paulson@3745
   171
val ClientKeyExch_tac = 
paulson@3772
   172
    forward_tac [Says_imp_spies RS parts.Inj RS certificate_valid]
paulson@3515
   173
    THEN' assume_tac
paulson@3515
   174
    THEN' hyp_subst_tac;
paulson@3515
   175
paulson@3515
   176
fun analz_induct_tac i = 
paulson@3515
   177
    etac tls.induct i   THEN
paulson@3745
   178
    ClientKeyExch_tac  (i+6)  THEN	(*ClientKeyExch*)
paulson@6915
   179
    ALLGOALS (asm_simp_tac (simpset() addsimps split_ifs @ pushes))  THEN
paulson@3515
   180
    (*Remove instances of pubK B:  the Spy already knows all public keys.
paulson@3515
   181
      Combining the two simplifier calls makes them run extremely slowly.*)
paulson@6915
   182
    ALLGOALS (asm_simp_tac (simpset() addsimps [insert_absorb]));
paulson@3515
   183
paulson@3515
   184
paulson@3758
   185
(*** Properties of items found in Notes ***)
paulson@3515
   186
paulson@5114
   187
Goal "[| Notes A {|Agent B, X|} : set evs;  evs : tls |]  \
paulson@5359
   188
\     ==> Crypt (pubK B) X : parts (spies evs)";
paulson@3515
   189
by (etac rev_mp 1);
paulson@3515
   190
by (analz_induct_tac 1);
wenzelm@4091
   191
by (blast_tac (claset() addIs [parts_insertI]) 1);
paulson@3683
   192
qed "Notes_Crypt_parts_spies";
paulson@3515
   193
paulson@3758
   194
(*C may be either A or B*)
paulson@5114
   195
Goal "[| Notes C {|s, Agent A, Agent B, Nonce(PRF(PMS,NA,NB))|} : set evs; \
paulson@5359
   196
\        evs : tls |]    \
paulson@5359
   197
\     ==> Crypt (pubK B) (Nonce PMS) : parts (spies evs)";
paulson@3685
   198
by (etac rev_mp 1);
paulson@3685
   199
by (parts_induct_tac 1);
paulson@3711
   200
by (ALLGOALS Clarify_tac);
paulson@3685
   201
(*Fake*)
wenzelm@4091
   202
by (blast_tac (claset() addIs [parts_insertI]) 1);
paulson@3685
   203
(*Client, Server Accept*)
paulson@5433
   204
by (REPEAT (blast_tac (claset() addSDs [Notes_Crypt_parts_spies]) 1));
paulson@3685
   205
qed "Notes_master_imp_Crypt_PMS";
paulson@3685
   206
paulson@3685
   207
(*Compared with the theorem above, both premise and conclusion are stronger*)
paulson@5114
   208
Goal "[| Notes A {|s, Agent A, Agent B, Nonce(PRF(PMS,NA,NB))|} : set evs;\
paulson@5359
   209
\        evs : tls |]    \
paulson@5359
   210
\     ==> Notes A {|Agent B, Nonce PMS|} : set evs";
paulson@3685
   211
by (etac rev_mp 1);
paulson@3685
   212
by (parts_induct_tac 1);
paulson@3685
   213
(*ServerAccepts*)
paulson@6284
   214
by (Fast_tac 1);
paulson@3685
   215
qed "Notes_master_imp_Notes_PMS";
paulson@3685
   216
paulson@3685
   217
paulson@3685
   218
(*** Protocol goal: if B receives CertVerify, then A sent it ***)
paulson@3474
   219
paulson@3745
   220
(*B can check A's signature if he has received A's certificate.*)
paulson@5114
   221
Goal "[| X : parts (spies evs);                          \
paulson@5114
   222
\        X = Crypt (priK A) (Hash{|nb, Agent B, pms|});  \
paulson@5114
   223
\        evs : tls;  A ~: bad |]                         \
paulson@5359
   224
\     ==> Says A B X : set evs";
paulson@3745
   225
by (etac rev_mp 1);
paulson@3480
   226
by (hyp_subst_tac 1);
paulson@3519
   227
by (parts_induct_tac 1);
paulson@5433
   228
by (Blast_tac 1);
paulson@3745
   229
val lemma = result();
paulson@3745
   230
paulson@3745
   231
(*Final version: B checks X using the distributed KA instead of priK A*)
paulson@5114
   232
Goal "[| X : parts (spies evs);                            \
paulson@5114
   233
\        X = Crypt (invKey KA) (Hash{|nb, Agent B, pms|}); \
paulson@5114
   234
\        certificate A KA : parts (spies evs);             \
paulson@5114
   235
\        evs : tls;  A ~: bad |]                           \
paulson@5359
   236
\     ==> Says A B X : set evs";
wenzelm@4091
   237
by (blast_tac (claset() addSDs [certificate_valid] addSIs [lemma]) 1);
paulson@3745
   238
qed "TrustCertVerify";
paulson@3474
   239
paulson@3474
   240
paulson@3685
   241
(*If CertVerify is present then A has chosen PMS.*)
paulson@5114
   242
Goal "[| Crypt (priK A) (Hash{|nb, Agent B, Nonce PMS|}) \
paulson@5114
   243
\          : parts (spies evs);                          \
paulson@5114
   244
\        evs : tls;  A ~: bad |]                         \
paulson@5114
   245
\     ==> Notes A {|Agent B, Nonce PMS|} : set evs";
wenzelm@4423
   246
by (etac rev_mp 1);
paulson@3519
   247
by (parts_induct_tac 1);
paulson@5433
   248
by (Blast_tac 1);
paulson@3745
   249
val lemma = result();
paulson@3745
   250
paulson@3745
   251
(*Final version using the distributed KA instead of priK A*)
paulson@5114
   252
Goal "[| Crypt (invKey KA) (Hash{|nb, Agent B, Nonce PMS|}) \
paulson@5114
   253
\          : parts (spies evs);                             \
paulson@5114
   254
\        certificate A KA : parts (spies evs);              \
paulson@5114
   255
\        evs : tls;  A ~: bad |]                            \
paulson@5114
   256
\     ==> Notes A {|Agent B, Nonce PMS|} : set evs";
wenzelm@4091
   257
by (blast_tac (claset() addSDs [certificate_valid] addSIs [lemma]) 1);
paulson@3515
   258
qed "UseCertVerify";
paulson@3474
   259
paulson@3480
   260
paulson@5114
   261
Goal "evs : tls ==> Notes A {|Agent B, Nonce (PRF x)|} ~: set evs";
paulson@3672
   262
by (parts_induct_tac 1);
paulson@3745
   263
(*ClientKeyExch: PMS is assumed to differ from any PRF.*)
paulson@3672
   264
by (Blast_tac 1);
paulson@3672
   265
qed "no_Notes_A_PRF";
paulson@3672
   266
Addsimps [no_Notes_A_PRF];
paulson@3672
   267
paulson@3672
   268
paulson@5359
   269
Goal "[| Nonce (PRF (PMS,NA,NB)) : parts (spies evs);  evs : tls |]  \
paulson@5359
   270
\     ==> Nonce PMS : parts (spies evs)";
paulson@3672
   271
by (etac rev_mp 1);
paulson@3672
   272
by (parts_induct_tac 1);
paulson@5433
   273
(*Easy, e.g. by freshness*)
paulson@5433
   274
by (REPEAT (blast_tac (claset() addDs [Notes_Crypt_parts_spies]) 2));
paulson@5433
   275
(*Fake*)
paulson@5433
   276
by (blast_tac (claset() addIs [parts_insertI]) 1);
paulson@3672
   277
qed "MS_imp_PMS";
paulson@3672
   278
AddSDs [MS_imp_PMS];
paulson@3672
   279
paulson@3672
   280
paulson@3474
   281
paulson@3672
   282
(*** Unicity results for PMS, the pre-master-secret ***)
paulson@3515
   283
paulson@3672
   284
(*PMS determines B.  Proof borrowed from NS_Public/unique_NA and from Yahalom*)
paulson@5114
   285
Goal "[| Nonce PMS ~: analz (spies evs);  evs : tls |]   \
paulson@5114
   286
\     ==> EX B'. ALL B.   \
paulson@5114
   287
\           Crypt (pubK B) (Nonce PMS) : parts (spies evs) --> B=B'";
paulson@3515
   288
by (etac rev_mp 1);
paulson@3519
   289
by (parts_induct_tac 1);
paulson@5433
   290
by (Blast_tac 1);
paulson@3745
   291
(*ClientKeyExch*)
paulson@3745
   292
by (ClientKeyExch_tac 1);
wenzelm@4091
   293
by (asm_simp_tac (simpset() addsimps [all_conj_distrib]) 1);
paulson@3672
   294
by (expand_case_tac "PMS = ?y" 1 THEN
wenzelm@4091
   295
    blast_tac (claset() addSEs partsEs) 1);
paulson@3515
   296
val lemma = result();
paulson@3515
   297
paulson@5114
   298
Goal "[| Crypt(pubK B)  (Nonce PMS) : parts (spies evs); \
paulson@5114
   299
\        Crypt(pubK B') (Nonce PMS) : parts (spies evs); \
paulson@5114
   300
\        Nonce PMS ~: analz (spies evs);                 \
paulson@5114
   301
\        evs : tls |]                                          \
paulson@5114
   302
\     ==> B=B'";
paulson@3515
   303
by (prove_unique_tac lemma 1);
paulson@3704
   304
qed "Crypt_unique_PMS";
paulson@3704
   305
paulson@3515
   306
paulson@3685
   307
(** It is frustrating that we need two versions of the unicity results.
paulson@3704
   308
    But Notes A {|Agent B, Nonce PMS|} determines both A and B.  Sometimes
paulson@3704
   309
    we have only the weaker assertion Crypt(pubK B) (Nonce PMS), which 
paulson@3704
   310
    determines B alone, and only if PMS is secret.
paulson@3685
   311
**)
paulson@3515
   312
paulson@3677
   313
(*In A's internal Note, PMS determines A and B.*)
paulson@5359
   314
Goal "evs : tls ==> EX A' B'. ALL A B.  \
paulson@5359
   315
\                   Notes A {|Agent B, Nonce PMS|} : set evs --> A=A' & B=B'";
paulson@3519
   316
by (parts_induct_tac 1);
wenzelm@4091
   317
by (asm_simp_tac (simpset() addsimps [all_conj_distrib]) 1);
paulson@3745
   318
(*ClientKeyExch: if PMS is fresh, then it can't appear in Notes A X.*)
paulson@3672
   319
by (expand_case_tac "PMS = ?y" 1 THEN
wenzelm@4091
   320
    blast_tac (claset() addSDs [Notes_Crypt_parts_spies] addSEs partsEs) 1);
paulson@3515
   321
val lemma = result();
paulson@3515
   322
paulson@5114
   323
Goal "[| Notes A  {|Agent B,  Nonce PMS|} : set evs;  \
paulson@5114
   324
\        Notes A' {|Agent B', Nonce PMS|} : set evs;  \
paulson@5114
   325
\        evs : tls |]                               \
paulson@5114
   326
\     ==> A=A' & B=B'";
paulson@3515
   327
by (prove_unique_tac lemma 1);
paulson@3672
   328
qed "Notes_unique_PMS";
paulson@3515
   329
paulson@3515
   330
paulson@3474
   331
paulson@3772
   332
(**** Secrecy Theorems ****)
paulson@3772
   333
paulson@3772
   334
(*Key compromise lemma needed to prove analz_image_keys.
paulson@3772
   335
  No collection of keys can help the spy get new private keys.*)
paulson@5359
   336
Goal "evs : tls                                      \
paulson@5359
   337
\     ==> ALL KK. (Key(priK B) : analz (Key``KK Un (spies evs))) = \
paulson@5359
   338
\         (priK B : KK | B : bad)";
paulson@3772
   339
by (etac tls.induct 1);
paulson@3772
   340
by (ALLGOALS
paulson@3772
   341
    (asm_simp_tac (analz_image_keys_ss
paulson@5535
   342
		   addsimps certificate_def::keys_distinct)));
paulson@3772
   343
(*Fake*) 
paulson@4422
   344
by (spy_analz_tac 1);
paulson@3772
   345
qed_spec_mp "analz_image_priK";
paulson@3772
   346
paulson@3772
   347
paulson@3772
   348
(*slightly speeds up the big simplification below*)
paulson@5114
   349
Goal "KK <= range sessionK ==> priK B ~: KK";
paulson@3772
   350
by (Blast_tac 1);
paulson@3772
   351
val range_sessionkeys_not_priK = result();
paulson@3772
   352
paulson@3772
   353
(*Lemma for the trivial direction of the if-and-only-if*)
paulson@5114
   354
Goal "(X : analz (G Un H)) --> (X : analz H)  ==> \
paulson@5114
   355
\     (X : analz (G Un H))  =  (X : analz H)";
wenzelm@4091
   356
by (blast_tac (claset() addIs [impOfSubs analz_mono]) 1);
paulson@3961
   357
val analz_image_keys_lemma = result();
paulson@3772
   358
paulson@3772
   359
(** Strangely, the following version doesn't work:
paulson@5114
   360
\ ALL Z. (Nonce N : analz (Key``(sessionK``Z) Un (spies evs))) = \
paulson@5114
   361
\        (Nonce N : analz (spies evs))";
paulson@3772
   362
**)
paulson@3772
   363
paulson@5114
   364
Goal "evs : tls ==>                                    \
paulson@5114
   365
\ ALL KK. KK <= range sessionK -->                     \
paulson@5114
   366
\         (Nonce N : analz (Key``KK Un (spies evs))) = \
paulson@5114
   367
\         (Nonce N : analz (spies evs))";
paulson@3772
   368
by (etac tls.induct 1);
paulson@3772
   369
by (ClientKeyExch_tac 7);
paulson@3772
   370
by (REPEAT_FIRST (resolve_tac [allI, impI]));
paulson@3961
   371
by (REPEAT_FIRST (rtac analz_image_keys_lemma));
paulson@5076
   372
by (ALLGOALS    (*4.5 seconds*)
paulson@3772
   373
    (asm_simp_tac (analz_image_keys_ss 
paulson@5535
   374
		   addsimps split_ifs @ pushes @
paulson@5535
   375
		            [range_sessionkeys_not_priK, 
paulson@5535
   376
			     analz_image_priK, certificate_def])));
wenzelm@4091
   377
by (ALLGOALS (asm_simp_tac (simpset() addsimps [insert_absorb])));
paulson@3772
   378
(*Fake*) 
paulson@4422
   379
by (spy_analz_tac 1);
paulson@3772
   380
qed_spec_mp "analz_image_keys";
paulson@3772
   381
paulson@3772
   382
(*Knowing some session keys is no help in getting new nonces*)
paulson@5114
   383
Goal "evs : tls ==>          \
paulson@5114
   384
\     Nonce N : analz (insert (Key (sessionK z)) (spies evs)) =  \
paulson@5114
   385
\     (Nonce N : analz (spies evs))";
paulson@3772
   386
by (asm_simp_tac (analz_image_keys_ss addsimps [analz_image_keys]) 1);
paulson@3772
   387
qed "analz_insert_key";
paulson@3772
   388
Addsimps [analz_insert_key];
paulson@3772
   389
paulson@3772
   390
paulson@3772
   391
(*** Protocol goal: serverK(Na,Nb,M) and clientK(Na,Nb,M) remain secure ***)
paulson@3772
   392
paulson@3772
   393
(** Some lemmas about session keys, comprising clientK and serverK **)
paulson@3772
   394
paulson@3772
   395
paulson@3772
   396
(*Lemma: session keys are never used if PMS is fresh.  
paulson@3772
   397
  Nonces don't have to agree, allowing session resumption.
paulson@3772
   398
  Converse doesn't hold; revealing PMS doesn't force the keys to be sent.
paulson@3772
   399
  THEY ARE NOT SUITABLE AS SAFE ELIM RULES.*)
paulson@5114
   400
Goal "[| Nonce PMS ~: parts (spies evs);  \
paulson@6284
   401
\        K = sessionK((Na, Nb, PRF(PMS,NA,NB)), role);  \
paulson@5114
   402
\        evs : tls |]             \
paulson@3772
   403
\  ==> Key K ~: parts (spies evs) & (ALL Y. Crypt K Y ~: parts (spies evs))";
paulson@3772
   404
by (etac rev_mp 1);
paulson@3772
   405
by (hyp_subst_tac 1);
paulson@3772
   406
by (analz_induct_tac 1);
paulson@3772
   407
(*SpyKeys*)
paulson@5433
   408
by (Blast_tac 3);
paulson@3772
   409
(*Fake*)
paulson@5433
   410
by (blast_tac (claset() addIs [parts_insertI]) 2);
paulson@3772
   411
(** LEVEL 6 **)
paulson@3772
   412
(*Oops*)
paulson@3772
   413
by (REPEAT 
paulson@7057
   414
    (force_tac (claset() addSDs [Notes_Crypt_parts_spies, 
paulson@7057
   415
				 Notes_master_imp_Crypt_PMS],
paulson@7057
   416
		simpset()) 1));
paulson@3772
   417
val lemma = result();
paulson@3772
   418
paulson@6284
   419
Goal "[| Key (sessionK((Na, Nb, PRF(PMS,NA,NB)), role)) : parts (spies evs); \
paulson@5114
   420
\        evs : tls |]             \
paulson@5114
   421
\     ==> Nonce PMS : parts (spies evs)";
wenzelm@4091
   422
by (blast_tac (claset() addDs [lemma]) 1);
paulson@3772
   423
qed "PMS_sessionK_not_spied";
paulson@3772
   424
paulson@6284
   425
Goal "[| Crypt (sessionK((Na, Nb, PRF(PMS,NA,NB)), role)) Y  \
paulson@5114
   426
\          : parts (spies evs);  evs : tls |]             \
paulson@5114
   427
\     ==> Nonce PMS : parts (spies evs)";
wenzelm@4091
   428
by (blast_tac (claset() addDs [lemma]) 1);
paulson@3772
   429
qed "PMS_Crypt_sessionK_not_spied";
paulson@3772
   430
paulson@5433
   431
(*Write keys are never sent if M (MASTER SECRET) is secure.  
paulson@5433
   432
  Converse fails; betraying M doesn't force the keys to be sent!
paulson@3772
   433
  The strong Oops condition can be weakened later by unicity reasoning, 
paulson@5433
   434
  with some effort.  
paulson@5433
   435
  NO LONGER USED: see clientK_not_spied and serverK_not_spied*)
paulson@6284
   436
Goal "[| ALL A. Says A Spy (Key (sessionK((NA,NB,M),role))) ~: set evs; \
paulson@5114
   437
\        Nonce M ~: analz (spies evs);  evs : tls |]   \
paulson@6284
   438
\     ==> Key (sessionK((NA,NB,M),role)) ~: parts (spies evs)";
paulson@3772
   439
by (etac rev_mp 1);
paulson@3772
   440
by (etac rev_mp 1);
paulson@6284
   441
by (analz_induct_tac 1);        (*5 seconds*)
paulson@3772
   442
(*SpyKeys*)
wenzelm@4091
   443
by (blast_tac (claset() addDs [Says_imp_spies RS analz.Inj]) 3);
paulson@3772
   444
(*Fake*) 
paulson@3772
   445
by (spy_analz_tac 2);
paulson@3772
   446
(*Base*)
paulson@3772
   447
by (Blast_tac 1);
paulson@3772
   448
qed "sessionK_not_spied";
paulson@3772
   449
paulson@3772
   450
paulson@3745
   451
(*If A sends ClientKeyExch to an honest B, then the PMS will stay secret.*)
paulson@5114
   452
Goal "[| evs : tls;  A ~: bad;  B ~: bad |]           \
paulson@5114
   453
\     ==> Notes A {|Agent B, Nonce PMS|} : set evs  -->   \
paulson@5114
   454
\         Nonce PMS ~: analz (spies evs)";
paulson@6284
   455
by (analz_induct_tac 1);   (*4 seconds*)
paulson@3677
   456
(*ClientAccepts and ServerAccepts: because PMS ~: range PRF*)
wenzelm@4091
   457
by (REPEAT (fast_tac (claset() addss (simpset())) 6));
paulson@3745
   458
(*ClientHello, ServerHello, ClientKeyExch, ServerResume: 
paulson@3687
   459
  mostly freshness reasoning*)
wenzelm@4091
   460
by (REPEAT (blast_tac (claset() addSEs partsEs
paulson@4201
   461
				addDs  [Notes_Crypt_parts_spies,
paulson@4201
   462
					Says_imp_spies RS analz.Inj]) 3));
paulson@3677
   463
(*SpyKeys*)
wenzelm@4091
   464
by (fast_tac (claset() addss (simpset())) 2);
paulson@3677
   465
(*Fake*)
paulson@3677
   466
by (spy_analz_tac 1);
paulson@3677
   467
bind_thm ("Spy_not_see_PMS", result() RSN (2, rev_mp));
paulson@3677
   468
paulson@3677
   469
paulson@3745
   470
(*If A sends ClientKeyExch to an honest B, then the MASTER SECRET
paulson@3677
   471
  will stay secret.*)
paulson@5114
   472
Goal "[| evs : tls;  A ~: bad;  B ~: bad |]           \
paulson@5114
   473
\     ==> Notes A {|Agent B, Nonce PMS|} : set evs  -->   \
paulson@5114
   474
\         Nonce (PRF(PMS,NA,NB)) ~: analz (spies evs)";
paulson@6284
   475
by (analz_induct_tac 1);   (*4 seconds*)
paulson@3677
   476
(*ClientAccepts and ServerAccepts: because PMS was already visible*)
wenzelm@4091
   477
by (REPEAT (blast_tac (claset() addDs [Spy_not_see_PMS, 
paulson@4201
   478
				       Says_imp_spies RS analz.Inj,
paulson@6308
   479
				       Notes_imp_knows_Spy RS analz.Inj]) 6));
paulson@3677
   480
(*ClientHello*)
paulson@3677
   481
by (Blast_tac 3);
paulson@3677
   482
(*SpyKeys: by secrecy of the PMS, Spy cannot make the MS*)
wenzelm@4091
   483
by (blast_tac (claset() addSDs [Spy_not_see_PMS, 
paulson@4422
   484
				Says_imp_spies RS analz.Inj]) 2);
paulson@3677
   485
(*Fake*)
paulson@3677
   486
by (spy_analz_tac 1);
paulson@3745
   487
(*ServerHello and ClientKeyExch: mostly freshness reasoning*)
wenzelm@4091
   488
by (REPEAT (blast_tac (claset() addSEs partsEs
paulson@4201
   489
				addDs  [Notes_Crypt_parts_spies,
paulson@4201
   490
					Says_imp_spies RS analz.Inj]) 1));
paulson@3677
   491
bind_thm ("Spy_not_see_MS", result() RSN (2, rev_mp));
paulson@3677
   492
paulson@3677
   493
paulson@3704
   494
(*** Weakening the Oops conditions for leakage of clientK ***)
paulson@3704
   495
paulson@5433
   496
(*If A created PMS then nobody else (except the Spy in replays) 
paulson@5433
   497
  would send a message using a clientK generated from that PMS.*)
paulson@5433
   498
Goal "[| Says A' B' (Crypt (clientK(Na,Nb,PRF(PMS,NA,NB))) Y) : set evs;  \
paulson@5433
   499
\        Notes A {|Agent B, Nonce PMS|} : set evs;   \
paulson@5433
   500
\        evs : tls;  A' ~= Spy |]                \
paulson@5433
   501
\     ==> A = A'";
paulson@5433
   502
by (etac rev_mp 1);
paulson@5433
   503
by (etac rev_mp 1);
paulson@6284
   504
by (analz_induct_tac 1); 
paulson@3711
   505
by (ALLGOALS Clarify_tac);
paulson@3704
   506
(*ClientFinished, ClientResume: by unicity of PMS*)
paulson@3704
   507
by (REPEAT 
wenzelm@4091
   508
    (blast_tac (claset() addSDs [Notes_master_imp_Notes_PMS]
paulson@4201
   509
     	 	         addIs  [Notes_unique_PMS RS conjunct1]) 2));
paulson@3745
   510
(*ClientKeyExch*)
paulson@4472
   511
by (blast_tac (claset() addSDs [PMS_Crypt_sessionK_not_spied,
paulson@4472
   512
				Says_imp_spies RS parts.Inj]) 1);
paulson@5433
   513
qed "Says_clientK_unique";
paulson@3704
   514
paulson@3704
   515
paulson@3704
   516
(*If A created PMS and has not leaked her clientK to the Spy, 
paulson@5433
   517
  then it is completely secure: not even in parts!*)
paulson@5433
   518
Goal "[| Notes A {|Agent B, Nonce PMS|} : set evs;  \
paulson@5433
   519
\        Says A Spy (Key (clientK(Na,Nb,PRF(PMS,NA,NB)))) ~: set evs;  \
paulson@5433
   520
\        A ~: bad;  B ~: bad; \
paulson@5433
   521
\        evs : tls |]   \
paulson@5433
   522
\     ==> Key (clientK(Na,Nb,PRF(PMS,NA,NB))) ~: parts (spies evs)";
paulson@5433
   523
by (etac rev_mp 1);
paulson@5433
   524
by (etac rev_mp 1);
paulson@6284
   525
by (analz_induct_tac 1);        (*4 seconds*)
paulson@3704
   526
(*Oops*)
paulson@5433
   527
by (blast_tac (claset() addIs [Says_clientK_unique]) 4);
paulson@3745
   528
(*ClientKeyExch*)
paulson@5433
   529
by (blast_tac (claset() addSDs [PMS_sessionK_not_spied]) 3);
paulson@5433
   530
(*SpyKeys*)
paulson@5433
   531
by (blast_tac (claset() addSEs [Spy_not_see_MS RSN (2,rev_notE)]) 2);
paulson@5433
   532
(*Fake*) 
paulson@5433
   533
by (spy_analz_tac 1);
paulson@5433
   534
qed "clientK_not_spied";
paulson@3704
   535
paulson@3704
   536
paulson@3704
   537
(*** Weakening the Oops conditions for leakage of serverK ***)
paulson@3704
   538
paulson@3704
   539
(*If A created PMS for B, then nobody other than B or the Spy would
paulson@3704
   540
  send a message using a serverK generated from that PMS.*)
paulson@5433
   541
Goal "[| Says B' A' (Crypt (serverK(Na,Nb,PRF(PMS,NA,NB))) Y) : set evs;  \
paulson@5433
   542
\        Notes A {|Agent B, Nonce PMS|} : set evs;  \
paulson@5433
   543
\        evs : tls;  A ~: bad;  B ~: bad;  B' ~= Spy |]                \
paulson@5433
   544
\     ==> B = B'";
paulson@5433
   545
by (etac rev_mp 1);
paulson@5433
   546
by (etac rev_mp 1);
paulson@6284
   547
by (analz_induct_tac 1);
paulson@3711
   548
by (ALLGOALS Clarify_tac);
paulson@3704
   549
(*ServerResume, ServerFinished: by unicity of PMS*)
paulson@3704
   550
by (REPEAT
paulson@5433
   551
    (blast_tac (claset() addSDs [Notes_master_imp_Crypt_PMS]
paulson@4201
   552
			 addDs  [Spy_not_see_PMS, 
paulson@4201
   553
				 Notes_Crypt_parts_spies,
paulson@4201
   554
				 Crypt_unique_PMS]) 2));
paulson@3745
   555
(*ClientKeyExch*)
paulson@4472
   556
by (blast_tac (claset() addSDs [PMS_Crypt_sessionK_not_spied,
paulson@4472
   557
				Says_imp_spies RS parts.Inj]) 1);
paulson@5433
   558
qed "Says_serverK_unique";
paulson@3704
   559
paulson@3704
   560
(*If A created PMS for B, and B has not leaked his serverK to the Spy, 
paulson@5433
   561
  then it is completely secure: not even in parts!*)
paulson@6284
   562
Goal "[| Notes A {|Agent B, Nonce PMS|} : set evs;                   \
paulson@5433
   563
\        Says B Spy (Key(serverK(Na,Nb,PRF(PMS,NA,NB)))) ~: set evs; \
paulson@6284
   564
\        A ~: bad;  B ~: bad;  evs : tls |]                          \
paulson@5433
   565
\     ==> Key (serverK(Na,Nb,PRF(PMS,NA,NB))) ~: parts (spies evs)";
paulson@5433
   566
by (etac rev_mp 1);
paulson@5433
   567
by (etac rev_mp 1);
paulson@6284
   568
by (analz_induct_tac 1);
paulson@3704
   569
(*Oops*)
paulson@5433
   570
by (blast_tac (claset() addIs [Says_serverK_unique]) 4);
paulson@3745
   571
(*ClientKeyExch*)
paulson@5433
   572
by (blast_tac (claset() addSDs [PMS_sessionK_not_spied]) 3);
paulson@5433
   573
(*SpyKeys*)
paulson@5433
   574
by (blast_tac (claset() addSEs [Spy_not_see_MS RSN (2,rev_notE)]) 2);
paulson@5433
   575
(*Fake*) 
paulson@5433
   576
by (spy_analz_tac 1);
paulson@5433
   577
qed "serverK_not_spied";
paulson@3704
   578
paulson@3704
   579
paulson@3685
   580
(*** Protocol goals: if A receives ServerFinished, then B is present 
paulson@3729
   581
     and has used the quoted values PA, PB, etc.  Note that it is up to A
paulson@3729
   582
     to compare PA with what she originally sent.
paulson@3474
   583
***)
paulson@3474
   584
paulson@3685
   585
(*The mention of her name (A) in X assures A that B knows who she is.*)
paulson@5114
   586
Goal "[| X = Crypt (serverK(Na,Nb,M))                  \
paulson@5114
   587
\              (Hash{|Number SID, Nonce M,             \
paulson@5114
   588
\                     Nonce Na, Number PA, Agent A,    \
paulson@5114
   589
\                     Nonce Nb, Number PB, Agent B|}); \
paulson@5114
   590
\        M = PRF(PMS,NA,NB);                           \
paulson@5114
   591
\        evs : tls;  A ~: bad;  B ~: bad |]            \
paulson@5433
   592
\     ==> Says B Spy (Key(serverK(Na,Nb,M))) ~: set evs --> \
paulson@5114
   593
\         Notes A {|Agent B, Nonce PMS|} : set evs --> \
paulson@5114
   594
\         X : parts (spies evs) --> Says B A X : set evs";
paulson@3480
   595
by (hyp_subst_tac 1);
paulson@6284
   596
by (analz_induct_tac 1);        (*7 seconds*)
wenzelm@4091
   597
by (ALLGOALS (asm_simp_tac (simpset() addsimps [all_conj_distrib])));
paulson@3711
   598
by (ALLGOALS Clarify_tac);
paulson@4472
   599
(*ClientKeyExch*)
paulson@4472
   600
by (blast_tac (claset() addSDs [PMS_Crypt_sessionK_not_spied]) 2);
paulson@3480
   601
(*Fake: the Spy doesn't have the critical session key!*)
paulson@5433
   602
by (blast_tac (claset() addEs [serverK_not_spied RSN (2,rev_notE)]) 1);
paulson@3474
   603
qed_spec_mp "TrustServerFinished";
paulson@3474
   604
paulson@3685
   605
(*This version refers not to ServerFinished but to any message from B.
paulson@3685
   606
  We don't assume B has received CertVerify, and an intruder could
paulson@3515
   607
  have changed A's identity in all other messages, so we can't be sure
paulson@3519
   608
  that B sends his message to A.  If CLIENT KEY EXCHANGE were augmented
paulson@3704
   609
  to bind A's identity with PMS, then we could replace A' by A below.*)
paulson@5114
   610
Goal "[| M = PRF(PMS,NA,NB);  evs : tls;  A ~: bad;  B ~: bad |]     \
paulson@5433
   611
\     ==> Says B Spy (Key(serverK(Na,Nb,M))) ~: set evs --> \
paulson@5114
   612
\         Notes A {|Agent B, Nonce PMS|} : set evs -->              \
paulson@5114
   613
\         Crypt (serverK(Na,Nb,M)) Y : parts (spies evs)  -->  \
paulson@5114
   614
\         (EX A'. Says B A' (Crypt (serverK(Na,Nb,M)) Y) : set evs)";
paulson@3672
   615
by (hyp_subst_tac 1);
paulson@6284
   616
by (analz_induct_tac 1);	(*6 seconds*)
wenzelm@4091
   617
by (ALLGOALS (asm_simp_tac (simpset() addsimps [ex_disj_distrib])));
paulson@3711
   618
by (ALLGOALS Clarify_tac);
paulson@3704
   619
(*ServerResume, ServerFinished: by unicity of PMS*)
paulson@3704
   620
by (REPEAT
paulson@5433
   621
    (blast_tac (claset() addSDs [Notes_master_imp_Crypt_PMS]
paulson@4201
   622
			 addDs  [Spy_not_see_PMS, 
paulson@4201
   623
				 Notes_Crypt_parts_spies,
paulson@4201
   624
				 Crypt_unique_PMS]) 3));
paulson@3745
   625
(*ClientKeyExch*)
paulson@4472
   626
by (blast_tac (claset() addSDs [PMS_Crypt_sessionK_not_spied]) 2);
paulson@3515
   627
(*Fake: the Spy doesn't have the critical session key!*)
paulson@5433
   628
by (blast_tac (claset() addEs [serverK_not_spied RSN (2,rev_notE)]) 1);
paulson@3515
   629
qed_spec_mp "TrustServerMsg";
paulson@3515
   630
paulson@3515
   631
paulson@3515
   632
(*** Protocol goal: if B receives any message encrypted with clientK
paulson@3672
   633
     then A has sent it, ASSUMING that A chose PMS.  Authentication is
paulson@3515
   634
     assumed here; B cannot verify it.  But if the message is
paulson@3729
   635
     ClientFinished, then B can then check the quoted values PA, PB, etc.
paulson@3506
   636
***)
paulson@3704
   637
paulson@5114
   638
Goal "[| M = PRF(PMS,NA,NB);  evs : tls;  A ~: bad;  B ~: bad |] \
paulson@5433
   639
\     ==> Says A Spy (Key(clientK(Na,Nb,M))) ~: set evs --> \
paulson@5359
   640
\         Notes A {|Agent B, Nonce PMS|} : set evs -->               \
paulson@5359
   641
\         Crypt (clientK(Na,Nb,M)) Y : parts (spies evs) -->         \
paulson@5359
   642
\         Says A B (Crypt (clientK(Na,Nb,M)) Y) : set evs";
paulson@3772
   643
by (hyp_subst_tac 1);
paulson@6284
   644
by (analz_induct_tac 1);	(*6 seconds*)
paulson@3711
   645
by (ALLGOALS Clarify_tac);
paulson@3704
   646
(*ClientFinished, ClientResume: by unicity of PMS*)
wenzelm@4091
   647
by (REPEAT (blast_tac (claset() delrules [conjI]
paulson@4201
   648
		                addSDs [Notes_master_imp_Notes_PMS]
paulson@4201
   649
	 	                addDs  [Notes_unique_PMS]) 3));
paulson@4472
   650
(*ClientKeyExch*)
paulson@4472
   651
by (blast_tac (claset() addSDs [PMS_Crypt_sessionK_not_spied]) 2);
paulson@3480
   652
(*Fake: the Spy doesn't have the critical session key!*)
paulson@5433
   653
by (blast_tac (claset() addEs [clientK_not_spied RSN (2,rev_notE)]) 1);
paulson@5433
   654
qed_spec_mp "TrustClientMsg";
paulson@3506
   655
paulson@3506
   656
paulson@3685
   657
paulson@3685
   658
(*** Protocol goal: if B receives ClientFinished, and if B is able to
paulson@3685
   659
     check a CertVerify from A, then A has used the quoted
paulson@3729
   660
     values PA, PB, etc.  Even this one requires A to be uncompromised.
paulson@3506
   661
 ***)
paulson@5114
   662
Goal "[| M = PRF(PMS,NA,NB);                           \
paulson@5114
   663
\        Says A Spy (Key(clientK(Na,Nb,M))) ~: set evs;\
paulson@5114
   664
\        Says A' B (Crypt (clientK(Na,Nb,M)) Y) : set evs; \
paulson@5114
   665
\        certificate A KA : parts (spies evs);       \
paulson@5114
   666
\        Says A'' B (Crypt (invKey KA) (Hash{|nb, Agent B, Nonce PMS|}))\
paulson@5114
   667
\          : set evs;                                                  \
paulson@5359
   668
\        evs : tls;  A ~: bad;  B ~: bad |]                             \
paulson@5359
   669
\     ==> Says A B (Crypt (clientK(Na,Nb,M)) Y) : set evs";
wenzelm@4091
   670
by (blast_tac (claset() addSIs [TrustClientMsg, UseCertVerify]
paulson@4201
   671
                        addDs  [Says_imp_spies RS parts.Inj]) 1);
paulson@3515
   672
qed "AuthClientFinished";
paulson@3687
   673
paulson@3687
   674
(*22/9/97: loads in 622s, which is 10 minutes 22 seconds*)
paulson@3711
   675
(*24/9/97: loads in 672s, which is 11 minutes 12 seconds [stronger theorems]*)
paulson@3745
   676
(*29/9/97: loads in 481s, after removing Certificate from ClientKeyExch*)
paulson@3758
   677
(*30/9/97: loads in 476s, after removing unused theorems*)
paulson@3760
   678
(*30/9/97: loads in 448s, after fixing ServerResume*)
paulson@5433
   679
paulson@5433
   680
(*08/9/97: loads in 189s (pike), after much reorganization, 
paulson@5433
   681
           back to 621s on albatross?*)
paulson@6284
   682
paulson@6284
   683
(*10/2/99: loads in 139s (pike)
paulson@6284
   684
           down to 433s on albatross*)