src/HOL/Auth/Message.ML
author paulson
Fri, 11 Jul 1997 13:26:15 +0200
changeset 3512 9dcb4daa15e8
parent 3476 1be4fee7606b
child 3514 eb16b8e8d872
permissions -rw-r--r--
Moving common declarations and proofs from theories "Shared" and "Public" to "Event". NB the original "Event" theory was later renamed "Shared". Addition of the Notes constructor to datatype "event".
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
     1
(*  Title:      HOL/Auth/Message
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
     2
    ID:         $Id$
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
     3
    Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
     4
    Copyright   1996  University of Cambridge
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
     5
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
     6
Datatypes of agents and messages;
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
     7
Inductive relations "parts", "analz" and "synth"
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
     8
*)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
     9
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    10
open Message;
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    11
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
    12
AddIffs (msg.inject);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    13
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    14
(** Inverse of keys **)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    15
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    16
goal thy "!!K K'. (invKey K = invKey K') = (K=K')";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    17
by (Step_tac 1);
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
    18
by (rtac box_equals 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    19
by (REPEAT (rtac invKey 2));
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    20
by (Asm_simp_tac 1);
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    21
qed "invKey_eq";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    22
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    23
Addsimps [invKey, invKey_eq];
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    24
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    25
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    26
(**** keysFor operator ****)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    27
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    28
goalw thy [keysFor_def] "keysFor {} = {}";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
    29
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    30
qed "keysFor_empty";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    31
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    32
goalw thy [keysFor_def] "keysFor (H Un H') = keysFor H Un keysFor H'";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
    33
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    34
qed "keysFor_Un";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    35
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    36
goalw thy [keysFor_def] "keysFor (UN i. H i) = (UN i. keysFor (H i))";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
    37
by (Blast_tac 1);
3121
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
    38
qed "keysFor_UN1";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    39
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    40
(*Monotonicity*)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    41
goalw thy [keysFor_def] "!!G H. G<=H ==> keysFor(G) <= keysFor(H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
    42
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    43
qed "keysFor_mono";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    44
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    45
goalw thy [keysFor_def] "keysFor (insert (Agent A) H) = keysFor H";
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
    46
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    47
qed "keysFor_insert_Agent";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    48
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    49
goalw thy [keysFor_def] "keysFor (insert (Nonce N) H) = keysFor H";
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
    50
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    51
qed "keysFor_insert_Nonce";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    52
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    53
goalw thy [keysFor_def] "keysFor (insert (Key K) H) = keysFor H";
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
    54
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    55
qed "keysFor_insert_Key";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    56
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
    57
goalw thy [keysFor_def] "keysFor (insert (Hash X) H) = keysFor H";
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
    58
by (Blast_tac 1);
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
    59
qed "keysFor_insert_Hash";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
    60
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    61
goalw thy [keysFor_def] "keysFor (insert {|X,Y|} H) = keysFor H";
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
    62
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    63
qed "keysFor_insert_MPair";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    64
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    65
goalw thy [keysFor_def]
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
    66
    "keysFor (insert (Crypt K X) H) = insert (invKey K) (keysFor H)";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    67
by (Auto_tac());
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    68
qed "keysFor_insert_Crypt";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    69
3121
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
    70
Addsimps [keysFor_empty, keysFor_Un, keysFor_UN1, 
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
    71
          keysFor_insert_Agent, keysFor_insert_Nonce, keysFor_insert_Key, 
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
    72
          keysFor_insert_Hash, keysFor_insert_MPair, keysFor_insert_Crypt];
3121
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
    73
AddSEs [keysFor_Un RS equalityD1 RS subsetD RS UnE,
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
    74
	keysFor_UN1 RS equalityD1 RS subsetD RS UN1_E];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    75
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
    76
goalw thy [keysFor_def] "!!H. Crypt K X : H ==> invKey K : keysFor H";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
    77
by (Blast_tac 1);
2068
0d05468dc80c New theorem Crypt_imp_invKey_keysFor
paulson
parents: 2061
diff changeset
    78
qed "Crypt_imp_invKey_keysFor";
0d05468dc80c New theorem Crypt_imp_invKey_keysFor
paulson
parents: 2061
diff changeset
    79
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    80
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    81
(**** Inductive relation "parts" ****)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    82
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    83
val major::prems = 
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    84
goal thy "[| {|X,Y|} : parts H;       \
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    85
\            [| X : parts H; Y : parts H |] ==> P  \
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    86
\         |] ==> P";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    87
by (cut_facts_tac [major] 1);
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
    88
by (resolve_tac prems 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    89
by (REPEAT (eresolve_tac [asm_rl, parts.Fst, parts.Snd] 1));
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    90
qed "MPair_parts";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    91
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
    92
AddIs  [parts.Inj];
1929
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
    93
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
    94
val partsEs = [MPair_parts, make_elim parts.Body];
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
    95
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
    96
AddSEs partsEs;
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
    97
(*NB These two rules are UNSAFE in the formal sense, as they discard the
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
    98
     compound message.  They work well on THIS FILE, perhaps because its
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
    99
     proofs concern only atomic messages.*)
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   100
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   101
goal thy "H <= parts(H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   102
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   103
qed "parts_increasing";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   104
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   105
(*Monotonicity*)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   106
goalw thy parts.defs "!!G H. G<=H ==> parts(G) <= parts(H)";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   107
by (rtac lfp_mono 1);
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   108
by (REPEAT (ares_tac basic_monos 1));
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   109
qed "parts_mono";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   110
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   111
val parts_insertI = impOfSubs (subset_insertI RS parts_mono);
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   112
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   113
goal thy "parts{} = {}";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   114
by (Step_tac 1);
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   115
by (etac parts.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   116
by (ALLGOALS Blast_tac);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   117
qed "parts_empty";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   118
Addsimps [parts_empty];
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   119
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   120
goal thy "!!X. X: parts{} ==> P";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   121
by (Asm_full_simp_tac 1);
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   122
qed "parts_emptyE";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   123
AddSEs [parts_emptyE];
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   124
1893
fa58f4a06f21 Works up to main theorem, then XXX...X
paulson
parents: 1885
diff changeset
   125
(*WARNING: loops if H = {Y}, therefore must not be repeated!*)
fa58f4a06f21 Works up to main theorem, then XXX...X
paulson
parents: 1885
diff changeset
   126
goal thy "!!H. X: parts H ==> EX Y:H. X: parts {Y}";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   127
by (etac parts.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   128
by (ALLGOALS Blast_tac);
1893
fa58f4a06f21 Works up to main theorem, then XXX...X
paulson
parents: 1885
diff changeset
   129
qed "parts_singleton";
fa58f4a06f21 Works up to main theorem, then XXX...X
paulson
parents: 1885
diff changeset
   130
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   131
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   132
(** Unions **)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   133
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   134
goal thy "parts(G) Un parts(H) <= parts(G Un H)";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   135
by (REPEAT (ares_tac [Un_least, parts_mono, Un_upper1, Un_upper2] 1));
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   136
val parts_Un_subset1 = result();
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   137
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   138
goal thy "parts(G Un H) <= parts(G) Un parts(H)";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   139
by (rtac subsetI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   140
by (etac parts.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   141
by (ALLGOALS Blast_tac);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   142
val parts_Un_subset2 = result();
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   143
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   144
goal thy "parts(G Un H) = parts(G) Un parts(H)";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   145
by (REPEAT (ares_tac [equalityI, parts_Un_subset1, parts_Un_subset2] 1));
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   146
qed "parts_Un";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   147
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   148
goal thy "parts (insert X H) = parts {X} Un parts H";
1852
289ce6cb5c84 Added Msg 3; works up to Says_Server_imp_Key_newK
paulson
parents: 1839
diff changeset
   149
by (stac (read_instantiate [("A","H")] insert_is_Un) 1);
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   150
by (simp_tac (HOL_ss addsimps [parts_Un]) 1);
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   151
qed "parts_insert";
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   152
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   153
(*TWO inserts to avoid looping.  This rewrite is better than nothing.
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   154
  Not suitable for Addsimps: its behaviour can be strange.*)
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   155
goal thy "parts (insert X (insert Y H)) = parts {X} Un parts {Y} Un parts H";
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   156
by (simp_tac (!simpset addsimps [Un_assoc]) 1);
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   157
by (simp_tac (!simpset addsimps [parts_insert RS sym]) 1);
1852
289ce6cb5c84 Added Msg 3; works up to Says_Server_imp_Key_newK
paulson
parents: 1839
diff changeset
   158
qed "parts_insert2";
289ce6cb5c84 Added Msg 3; works up to Says_Server_imp_Key_newK
paulson
parents: 1839
diff changeset
   159
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   160
goal thy "(UN x:A. parts(H x)) <= parts(UN x:A. H x)";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   161
by (REPEAT (ares_tac [UN_least, parts_mono, UN_upper] 1));
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   162
val parts_UN_subset1 = result();
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   163
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   164
goal thy "parts(UN x:A. H x) <= (UN x:A. parts(H x))";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   165
by (rtac subsetI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   166
by (etac parts.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   167
by (ALLGOALS Blast_tac);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   168
val parts_UN_subset2 = result();
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   169
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   170
goal thy "parts(UN x:A. H x) = (UN x:A. parts(H x))";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   171
by (REPEAT (ares_tac [equalityI, parts_UN_subset1, parts_UN_subset2] 1));
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   172
qed "parts_UN";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   173
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   174
goal thy "parts(UN x. H x) = (UN x. parts(H x))";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   175
by (simp_tac (!simpset addsimps [UNION1_def, parts_UN]) 1);
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   176
qed "parts_UN1";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   177
3121
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   178
(*Added to simplify arguments to parts, analz and synth.
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   179
  NOTE: the UN versions are no longer used!*)
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   180
Addsimps [parts_Un, parts_UN, parts_UN1];
3121
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   181
AddSEs [parts_Un RS equalityD1 RS subsetD RS UnE,
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   182
	parts_UN RS equalityD1 RS subsetD RS UN_E,
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   183
	parts_UN1 RS equalityD1 RS subsetD RS UN1_E];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   184
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   185
goal thy "insert X (parts H) <= parts(insert X H)";
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   186
by (blast_tac (!claset addIs [impOfSubs parts_mono]) 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   187
qed "parts_insert_subset";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   188
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   189
(** Idempotence and transitivity **)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   190
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   191
goal thy "!!H. X: parts (parts H) ==> X: parts H";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   192
by (etac parts.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   193
by (ALLGOALS Blast_tac);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   194
qed "parts_partsD";
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   195
AddSDs [parts_partsD];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   196
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   197
goal thy "parts (parts H) = parts H";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   198
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   199
qed "parts_idem";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   200
Addsimps [parts_idem];
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   201
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   202
goal thy "!!H. [| X: parts G;  G <= parts H |] ==> X: parts H";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   203
by (dtac parts_mono 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   204
by (Blast_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   205
qed "parts_trans";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   206
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   207
(*Cut*)
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   208
goal thy "!!H. [| Y: parts (insert X G);  X: parts H |] \
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   209
\              ==> Y: parts (G Un H)";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   210
by (etac parts_trans 1);
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   211
by (Auto_tac());
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   212
qed "parts_cut";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   213
1929
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   214
goal thy "!!H. X: parts H ==> parts (insert X H) = parts H";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   215
by (fast_tac (!claset addSDs [parts_cut]
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   216
                      addIs  [parts_insertI] 
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   217
                      addss (!simpset)) 1);
1929
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   218
qed "parts_cut_eq";
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   219
2028
738bb98d65ec Last working version prior to addition of "lost" component
paulson
parents: 2026
diff changeset
   220
Addsimps [parts_cut_eq];
738bb98d65ec Last working version prior to addition of "lost" component
paulson
parents: 2026
diff changeset
   221
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   222
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   223
(** Rewrite rules for pulling out atomic messages **)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   224
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   225
fun parts_tac i =
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   226
  EVERY [rtac ([subsetI, parts_insert_subset] MRS equalityI) i,
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   227
         etac parts.induct i,
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
   228
         REPEAT (Blast_tac i)];
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   229
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   230
goal thy "parts (insert (Agent agt) H) = insert (Agent agt) (parts H)";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   231
by (parts_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   232
qed "parts_insert_Agent";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   233
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   234
goal thy "parts (insert (Nonce N) H) = insert (Nonce N) (parts H)";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   235
by (parts_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   236
qed "parts_insert_Nonce";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   237
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   238
goal thy "parts (insert (Key K) H) = insert (Key K) (parts H)";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   239
by (parts_tac 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   240
qed "parts_insert_Key";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   241
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   242
goal thy "parts (insert (Hash X) H) = insert (Hash X) (parts H)";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   243
by (parts_tac 1);
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   244
qed "parts_insert_Hash";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   245
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   246
goal thy "parts (insert (Crypt K X) H) = \
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   247
\         insert (Crypt K X) (parts (insert X H))";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   248
by (rtac equalityI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   249
by (rtac subsetI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   250
by (etac parts.induct 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   251
by (Auto_tac());
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   252
by (etac parts.induct 1);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   253
by (ALLGOALS (blast_tac (!claset addIs [parts.Body])));
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   254
qed "parts_insert_Crypt";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   255
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   256
goal thy "parts (insert {|X,Y|} H) = \
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   257
\         insert {|X,Y|} (parts (insert X (insert Y H)))";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   258
by (rtac equalityI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   259
by (rtac subsetI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   260
by (etac parts.induct 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   261
by (Auto_tac());
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   262
by (etac parts.induct 1);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   263
by (ALLGOALS (blast_tac (!claset addIs [parts.Fst, parts.Snd])));
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   264
qed "parts_insert_MPair";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   265
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   266
Addsimps [parts_insert_Agent, parts_insert_Nonce, parts_insert_Key, 
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   267
          parts_insert_Hash, parts_insert_Crypt, parts_insert_MPair];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   268
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   269
2026
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   270
goal thy "parts (Key``N) = Key``N";
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   271
by (Auto_tac());
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   272
by (etac parts.induct 1);
2026
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   273
by (Auto_tac());
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   274
qed "parts_image_Key";
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   275
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   276
Addsimps [parts_image_Key];
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   277
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   278
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   279
(**** Inductive relation "analz" ****)
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   280
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   281
val major::prems = 
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   282
goal thy "[| {|X,Y|} : analz H;       \
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   283
\            [| X : analz H; Y : analz H |] ==> P  \
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   284
\         |] ==> P";
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   285
by (cut_facts_tac [major] 1);
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   286
by (resolve_tac prems 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   287
by (REPEAT (eresolve_tac [asm_rl, analz.Fst, analz.Snd] 1));
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   288
qed "MPair_analz";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   289
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   290
AddIs  [analz.Inj];
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   291
AddSEs [MPair_analz];      (*Perhaps it should NOT be deemed safe!*)
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   292
AddDs  [analz.Decrypt];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   293
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   294
Addsimps [analz.Inj];
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   295
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   296
goal thy "H <= analz(H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   297
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   298
qed "analz_increasing";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   299
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   300
goal thy "analz H <= parts H";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   301
by (rtac subsetI 1);
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   302
by (etac analz.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   303
by (ALLGOALS Blast_tac);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   304
qed "analz_subset_parts";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   305
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   306
bind_thm ("not_parts_not_analz", analz_subset_parts RS contra_subsetD);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   307
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   308
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   309
goal thy "parts (analz H) = parts H";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   310
by (rtac equalityI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   311
by (rtac (analz_subset_parts RS parts_mono RS subset_trans) 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   312
by (Simp_tac 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   313
by (blast_tac (!claset addIs [analz_increasing RS parts_mono RS subsetD]) 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   314
qed "parts_analz";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   315
Addsimps [parts_analz];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   316
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   317
goal thy "analz (parts H) = parts H";
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   318
by (Auto_tac());
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   319
by (etac analz.induct 1);
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   320
by (Auto_tac());
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   321
qed "analz_parts";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   322
Addsimps [analz_parts];
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   323
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   324
(*Monotonicity; Lemma 1 of Lowe*)
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   325
goalw thy analz.defs "!!G H. G<=H ==> analz(G) <= analz(H)";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   326
by (rtac lfp_mono 1);
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   327
by (REPEAT (ares_tac basic_monos 1));
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   328
qed "analz_mono";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   329
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   330
val analz_insertI = impOfSubs (subset_insertI RS analz_mono);
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   331
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   332
(** General equational properties **)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   333
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   334
goal thy "analz{} = {}";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   335
by (Step_tac 1);
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   336
by (etac analz.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   337
by (ALLGOALS Blast_tac);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   338
qed "analz_empty";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   339
Addsimps [analz_empty];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   340
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   341
(*Converse fails: we can analz more from the union than from the 
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   342
  separate parts, as a key in one might decrypt a message in the other*)
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   343
goal thy "analz(G) Un analz(H) <= analz(G Un H)";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   344
by (REPEAT (ares_tac [Un_least, analz_mono, Un_upper1, Un_upper2] 1));
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   345
qed "analz_Un";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   346
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   347
goal thy "insert X (analz H) <= analz(insert X H)";
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   348
by (blast_tac (!claset addIs [impOfSubs analz_mono]) 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   349
qed "analz_insert";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   350
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   351
(** Rewrite rules for pulling out atomic messages **)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   352
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   353
fun analz_tac i =
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   354
  EVERY [rtac ([subsetI, analz_insert] MRS equalityI) i,
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   355
         etac analz.induct i,
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
   356
         REPEAT (Blast_tac i)];
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   357
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   358
goal thy "analz (insert (Agent agt) H) = insert (Agent agt) (analz H)";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   359
by (analz_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   360
qed "analz_insert_Agent";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   361
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   362
goal thy "analz (insert (Nonce N) H) = insert (Nonce N) (analz H)";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   363
by (analz_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   364
qed "analz_insert_Nonce";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   365
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   366
goal thy "analz (insert (Hash X) H) = insert (Hash X) (analz H)";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   367
by (analz_tac 1);
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   368
qed "analz_insert_Hash";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   369
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   370
(*Can only pull out Keys if they are not needed to decrypt the rest*)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   371
goalw thy [keysFor_def]
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   372
    "!!K. K ~: keysFor (analz H) ==>  \
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   373
\         analz (insert (Key K) H) = insert (Key K) (analz H)";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   374
by (analz_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   375
qed "analz_insert_Key";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   376
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   377
goal thy "analz (insert {|X,Y|} H) = \
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   378
\         insert {|X,Y|} (analz (insert X (insert Y H)))";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   379
by (rtac equalityI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   380
by (rtac subsetI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   381
by (etac analz.induct 1);
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   382
by (Auto_tac());
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   383
by (etac analz.induct 1);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   384
by (ALLGOALS (blast_tac (!claset addIs [analz.Fst, analz.Snd])));
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   385
qed "analz_insert_MPair";
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   386
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   387
(*Can pull out enCrypted message if the Key is not known*)
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   388
goal thy "!!H. Key (invKey K) ~: analz H ==>  \
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   389
\              analz (insert (Crypt K X) H) = \
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   390
\              insert (Crypt K X) (analz H)";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   391
by (analz_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   392
qed "analz_insert_Crypt";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   393
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   394
goal thy "!!H. Key (invKey K) : analz H ==>  \
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   395
\              analz (insert (Crypt K X) H) <= \
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   396
\              insert (Crypt K X) (analz (insert X H))";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   397
by (rtac subsetI 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   398
by (eres_inst_tac [("za","x")] analz.induct 1);
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
   399
by (ALLGOALS (Blast_tac));
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   400
val lemma1 = result();
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   401
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   402
goal thy "!!H. Key (invKey K) : analz H ==>  \
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   403
\              insert (Crypt K X) (analz (insert X H)) <= \
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   404
\              analz (insert (Crypt K X) H)";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   405
by (Auto_tac());
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   406
by (eres_inst_tac [("za","x")] analz.induct 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   407
by (Auto_tac());
3449
6b17f82bbf01 New comments; a tidied proof
paulson
parents: 3431
diff changeset
   408
by (blast_tac (!claset addIs [analz_insertI, analz.Decrypt]) 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   409
val lemma2 = result();
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   410
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   411
goal thy "!!H. Key (invKey K) : analz H ==>  \
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   412
\              analz (insert (Crypt K X) H) = \
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   413
\              insert (Crypt K X) (analz (insert X H))";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   414
by (REPEAT (ares_tac [equalityI, lemma1, lemma2] 1));
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   415
qed "analz_insert_Decrypt";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   416
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   417
(*Case analysis: either the message is secure, or it is not!
1946
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   418
  Effective, but can cause subgoals to blow up!
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   419
  Use with expand_if;  apparently split_tac does not cope with patterns
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   420
  such as "analz (insert (Crypt K X) H)" *)
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   421
goal thy "analz (insert (Crypt K X) H) =                \
2154
913b4fc7670a New, purely illustrative result Crypt_synth_analz
paulson
parents: 2102
diff changeset
   422
\         (if (Key (invKey K) : analz H)                \
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   423
\          then insert (Crypt K X) (analz (insert X H)) \
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   424
\          else insert (Crypt K X) (analz H))";
2102
41a667d2c3fa Replaced excluded_middle_tac by case_tac
paulson
parents: 2068
diff changeset
   425
by (case_tac "Key (invKey K)  : analz H " 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   426
by (ALLGOALS (asm_simp_tac (!simpset addsimps [analz_insert_Crypt, 
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   427
                                               analz_insert_Decrypt])));
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   428
qed "analz_Crypt_if";
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   429
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   430
Addsimps [analz_insert_Agent, analz_insert_Nonce, analz_insert_Key, 
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   431
          analz_insert_Hash, analz_insert_MPair, analz_Crypt_if];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   432
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   433
(*This rule supposes "for the sake of argument" that we have the key.*)
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   434
goal thy  "analz (insert (Crypt K X) H) <=  \
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   435
\          insert (Crypt K X) (analz (insert X H))";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   436
by (rtac subsetI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   437
by (etac analz.induct 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   438
by (Auto_tac());
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   439
qed "analz_insert_Crypt_subset";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   440
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   441
2026
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   442
goal thy "analz (Key``N) = Key``N";
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   443
by (Auto_tac());
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   444
by (etac analz.induct 1);
2026
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   445
by (Auto_tac());
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   446
qed "analz_image_Key";
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   447
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   448
Addsimps [analz_image_Key];
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   449
0df5a96bf77e Last working version prior to introduction of "lost"
paulson
parents: 2011
diff changeset
   450
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   451
(** Idempotence and transitivity **)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   452
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   453
goal thy "!!H. X: analz (analz H) ==> X: analz H";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   454
by (etac analz.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   455
by (ALLGOALS Blast_tac);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   456
qed "analz_analzD";
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   457
AddSDs [analz_analzD];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   458
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   459
goal thy "analz (analz H) = analz H";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   460
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   461
qed "analz_idem";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   462
Addsimps [analz_idem];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   463
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   464
goal thy "!!H. [| X: analz G;  G <= analz H |] ==> X: analz H";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   465
by (dtac analz_mono 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   466
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   467
qed "analz_trans";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   468
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   469
(*Cut; Lemma 2 of Lowe*)
1998
f8230821f1e8 Reordering of premises for cut theorems, and new law MPair_synth_analz
paulson
parents: 1994
diff changeset
   470
goal thy "!!H. [| Y: analz (insert X H);  X: analz H |] ==> Y: analz H";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   471
by (etac analz_trans 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   472
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   473
qed "analz_cut";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   474
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   475
(*Cut can be proved easily by induction on
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   476
   "!!H. Y: analz (insert X H) ==> X: analz H --> Y: analz H"
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   477
*)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   478
3449
6b17f82bbf01 New comments; a tidied proof
paulson
parents: 3431
diff changeset
   479
(*This rewrite rule helps in the simplification of messages that involve
6b17f82bbf01 New comments; a tidied proof
paulson
parents: 3431
diff changeset
   480
  the forwarding of unknown components (X).  Without it, removing occurrences
6b17f82bbf01 New comments; a tidied proof
paulson
parents: 3431
diff changeset
   481
  of X can be very complicated. *)
3431
05b397185e1d Useful new lemma
paulson
parents: 3121
diff changeset
   482
goal thy "!!H. X: analz H ==> analz (insert X H) = analz H";
05b397185e1d Useful new lemma
paulson
parents: 3121
diff changeset
   483
by (blast_tac (!claset addIs [analz_cut, analz_insertI]) 1);
05b397185e1d Useful new lemma
paulson
parents: 3121
diff changeset
   484
qed "analz_insert_eq";
05b397185e1d Useful new lemma
paulson
parents: 3121
diff changeset
   485
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   486
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   487
(** A congruence rule for "analz" **)
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   488
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   489
goal thy "!!H. [| analz G <= analz G'; analz H <= analz H' \
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   490
\              |] ==> analz (G Un H) <= analz (G' Un H')";
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   491
by (Step_tac 1);
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   492
by (etac analz.induct 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   493
by (ALLGOALS (best_tac (!claset addIs [analz_mono RS subsetD])));
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   494
qed "analz_subset_cong";
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   495
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   496
goal thy "!!H. [| analz G = analz G'; analz H = analz H' \
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   497
\              |] ==> analz (G Un H) = analz (G' Un H')";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   498
by (REPEAT_FIRST (ares_tac [equalityI, analz_subset_cong]
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   499
          ORELSE' etac equalityE));
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   500
qed "analz_cong";
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   501
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   502
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   503
goal thy "!!H. analz H = analz H' ==> analz(insert X H) = analz(insert X H')";
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   504
by (asm_simp_tac (!simpset addsimps [insert_def] 
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   505
                           setloop (rtac analz_cong)) 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   506
qed "analz_insert_cong";
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   507
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   508
(*If there are no pairs or encryptions then analz does nothing*)
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   509
goal thy "!!H. [| ALL X Y. {|X,Y|} ~: H;  ALL X K. Crypt K X ~: H |] ==> \
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   510
\         analz H = H";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   511
by (Step_tac 1);
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   512
by (etac analz.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   513
by (ALLGOALS Blast_tac);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   514
qed "analz_trivial";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   515
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   516
(*Helps to prove Fake cases*)
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   517
goal thy "!!X. X: analz (UN i. analz (H i)) ==> X: analz (UN i. H i)";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   518
by (etac analz.induct 1);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   519
by (ALLGOALS (blast_tac (!claset addIs [impOfSubs analz_mono])));
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   520
val lemma = result();
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   521
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   522
goal thy "analz (UN i. analz (H i)) = analz (UN i. H i)";
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   523
by (blast_tac (!claset addIs [lemma, impOfSubs analz_mono]) 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   524
qed "analz_UN_analz";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   525
Addsimps [analz_UN_analz];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   526
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   527
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   528
(**** Inductive relation "synth" ****)
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   529
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   530
AddIs  synth.intrs;
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   531
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   532
(*Can only produce a nonce or key if it is already known,
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   533
  but can synth a pair or encryption from its components...*)
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   534
val mk_cases = synth.mk_cases msg.simps;
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   535
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   536
(*NO Agent_synth, as any Agent name can be synthesized*)
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   537
val Nonce_synth = mk_cases "Nonce n : synth H";
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   538
val Key_synth   = mk_cases "Key K : synth H";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   539
val Hash_synth  = mk_cases "Hash X : synth H";
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   540
val MPair_synth = mk_cases "{|X,Y|} : synth H";
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   541
val Crypt_synth = mk_cases "Crypt K X : synth H";
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   542
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   543
AddSEs [Nonce_synth, Key_synth, Hash_synth, MPair_synth, Crypt_synth];
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   544
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   545
goal thy "H <= synth(H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   546
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   547
qed "synth_increasing";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   548
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   549
(*Monotonicity*)
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   550
goalw thy synth.defs "!!G H. G<=H ==> synth(G) <= synth(H)";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   551
by (rtac lfp_mono 1);
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   552
by (REPEAT (ares_tac basic_monos 1));
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   553
qed "synth_mono";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   554
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   555
(** Unions **)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   556
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   557
(*Converse fails: we can synth more from the union than from the 
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   558
  separate parts, building a compound message using elements of each.*)
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   559
goal thy "synth(G) Un synth(H) <= synth(G Un H)";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   560
by (REPEAT (ares_tac [Un_least, synth_mono, Un_upper1, Un_upper2] 1));
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   561
qed "synth_Un";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   562
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   563
goal thy "insert X (synth H) <= synth(insert X H)";
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   564
by (blast_tac (!claset addIs [impOfSubs synth_mono]) 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   565
qed "synth_insert";
1885
a18a6dc14f76 Auth proofs work up to the XXX...
paulson
parents: 1852
diff changeset
   566
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   567
(** Idempotence and transitivity **)
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   568
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   569
goal thy "!!H. X: synth (synth H) ==> X: synth H";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   570
by (etac synth.induct 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   571
by (ALLGOALS Blast_tac);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   572
qed "synth_synthD";
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   573
AddSDs [synth_synthD];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   574
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   575
goal thy "synth (synth H) = synth H";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   576
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   577
qed "synth_idem";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   578
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   579
goal thy "!!H. [| X: synth G;  G <= synth H |] ==> X: synth H";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   580
by (dtac synth_mono 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   581
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   582
qed "synth_trans";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   583
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   584
(*Cut; Lemma 2 of Lowe*)
1998
f8230821f1e8 Reordering of premises for cut theorems, and new law MPair_synth_analz
paulson
parents: 1994
diff changeset
   585
goal thy "!!H. [| Y: synth (insert X H);  X: synth H |] ==> Y: synth H";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   586
by (etac synth_trans 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   587
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   588
qed "synth_cut";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   589
1946
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   590
goal thy "Agent A : synth H";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   591
by (Blast_tac 1);
1946
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   592
qed "Agent_synth";
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   593
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   594
goal thy "(Nonce N : synth H) = (Nonce N : H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   595
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   596
qed "Nonce_synth_eq";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   597
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   598
goal thy "(Key K : synth H) = (Key K : H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   599
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   600
qed "Key_synth_eq";
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   601
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   602
goal thy "!!K. Key K ~: H ==> (Crypt K X : synth H) = (Crypt K X : H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   603
by (Blast_tac 1);
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   604
qed "Crypt_synth_eq";
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   605
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   606
Addsimps [Agent_synth, Nonce_synth_eq, Key_synth_eq, Crypt_synth_eq];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   607
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   608
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   609
goalw thy [keysFor_def]
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   610
    "keysFor (synth H) = keysFor H Un invKey``{K. Key K : H}";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   611
by (Blast_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   612
qed "keysFor_synth";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   613
Addsimps [keysFor_synth];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   614
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   615
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   616
(*** Combinations of parts, analz and synth ***)
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   617
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   618
goal thy "parts (synth H) = parts H Un synth H";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   619
by (rtac equalityI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   620
by (rtac subsetI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   621
by (etac parts.induct 1);
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   622
by (ALLGOALS
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   623
    (blast_tac (!claset addIs ((synth_increasing RS parts_mono RS subsetD)
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   624
                             ::parts.intrs))));
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   625
qed "parts_synth";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   626
Addsimps [parts_synth];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   627
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   628
goal thy "analz (analz G Un H) = analz (G Un H)";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   629
by (REPEAT_FIRST (resolve_tac [equalityI, analz_subset_cong]));
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   630
by (ALLGOALS Simp_tac);
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   631
qed "analz_analz_Un";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   632
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   633
goal thy "analz (synth G Un H) = analz (G Un H) Un synth G";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   634
by (rtac equalityI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   635
by (rtac subsetI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   636
by (etac analz.induct 1);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   637
by (blast_tac (!claset addIs [impOfSubs analz_mono]) 5);
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   638
by (ALLGOALS (blast_tac (!claset addIs analz.intrs)));
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   639
qed "analz_synth_Un";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   640
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   641
goal thy "analz (synth H) = analz H Un synth H";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   642
by (cut_inst_tac [("H","{}")] analz_synth_Un 1);
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   643
by (Full_simp_tac 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   644
qed "analz_synth";
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   645
Addsimps [analz_analz_Un, analz_synth_Un, analz_synth];
1839
199243afac2b Proving safety properties of authentication protocols
paulson
parents:
diff changeset
   646
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   647
(*Hard to prove; still needed now that there's only one Spy?*)
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   648
goal thy "analz (UN i. synth (H i)) = \
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   649
\         analz (UN i. H i) Un (UN i. synth (H i))";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   650
by (rtac equalityI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   651
by (rtac subsetI 1);
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   652
by (etac analz.induct 1);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   653
by (blast_tac
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   654
    (!claset addIs [impOfSubs synth_increasing,
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   655
                    impOfSubs analz_mono]) 5);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   656
by (Blast_tac 1);
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   657
by (blast_tac (!claset addIs [analz.Inj RS analz.Fst]) 1);
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   658
by (blast_tac (!claset addIs [analz.Inj RS analz.Snd]) 1);
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   659
by (blast_tac (!claset addIs [analz.Decrypt]) 1);
1913
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   660
qed "analz_UN1_synth";
2809adb15eb0 Renaming of functions, and tidying
paulson
parents: 1893
diff changeset
   661
Addsimps [analz_UN1_synth];
1929
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   662
1946
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   663
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   664
(** For reasoning about the Fake rule in traces **)
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   665
1929
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   666
goal thy "!!Y. X: G ==> parts(insert X H) <= parts G Un parts H";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   667
by (rtac ([parts_mono, parts_Un_subset2] MRS subset_trans) 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   668
by (Blast_tac 1);
1929
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   669
qed "parts_insert_subset_Un";
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   670
1946
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   671
(*More specifically for Fake*)
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   672
goal thy "!!H. X: synth (analz G) ==> \
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   673
\              parts (insert X H) <= synth (analz G) Un parts G Un parts H";
2032
1bbf1bdcaf56 Introduction of "lost" argument
paulson
parents: 2028
diff changeset
   674
by (dtac parts_insert_subset_Un 1);
1946
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   675
by (Full_simp_tac 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   676
by (Blast_tac 1);
1946
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   677
qed "Fake_parts_insert";
b59a3d686436 New theorems for Fake case
paulson
parents: 1929
diff changeset
   678
2061
b14a08bf61bf New theorem Crypt_Fake_parts_insert
paulson
parents: 2032
diff changeset
   679
goal thy
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   680
     "!!H. [| Crypt K Y : parts (insert X H);  X: synth (analz G);  \
2061
b14a08bf61bf New theorem Crypt_Fake_parts_insert
paulson
parents: 2032
diff changeset
   681
\             Key K ~: analz G |]                                   \
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   682
\          ==> Crypt K Y : parts G Un parts H";
2061
b14a08bf61bf New theorem Crypt_Fake_parts_insert
paulson
parents: 2032
diff changeset
   683
by (dtac (impOfSubs Fake_parts_insert) 1);
2170
c5e460f1ebb4 Ran expandshort
paulson
parents: 2154
diff changeset
   684
by (assume_tac 1);
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
   685
by (blast_tac (!claset addDs [impOfSubs analz_subset_parts]) 1);
2061
b14a08bf61bf New theorem Crypt_Fake_parts_insert
paulson
parents: 2032
diff changeset
   686
qed "Crypt_Fake_parts_insert";
b14a08bf61bf New theorem Crypt_Fake_parts_insert
paulson
parents: 2032
diff changeset
   687
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   688
goal thy "!!H. X: synth (analz G) ==> \
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   689
\              analz (insert X H) <= synth (analz G) Un analz (G Un H)";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   690
by (rtac subsetI 1);
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   691
by (subgoal_tac "x : analz (synth (analz G) Un H)" 1);
2922
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   692
by (blast_tac (!claset addIs [impOfSubs analz_mono,
580647a879cf Using Blast_tac
paulson
parents: 2891
diff changeset
   693
			      impOfSubs (analz_mono RS synth_mono)]) 2);
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   694
by (Full_simp_tac 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   695
by (Blast_tac 1);
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   696
qed "Fake_analz_insert";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   697
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   698
goal thy "(X: analz H & X: parts H) = (X: analz H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   699
by (blast_tac (!claset addIs [impOfSubs analz_subset_parts]) 1);
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   700
val analz_conj_parts = result();
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   701
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   702
goal thy "(X: analz H | X: parts H) = (X: parts H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   703
by (blast_tac (!claset addIs [impOfSubs analz_subset_parts]) 1);
2011
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   704
val analz_disj_parts = result();
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   705
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   706
AddIffs [analz_conj_parts, analz_disj_parts];
d9af64c26be6 New laws for messages
paulson
parents: 1998
diff changeset
   707
1998
f8230821f1e8 Reordering of premises for cut theorems, and new law MPair_synth_analz
paulson
parents: 1994
diff changeset
   708
(*Without this equation, other rules for synth and analz would yield
f8230821f1e8 Reordering of premises for cut theorems, and new law MPair_synth_analz
paulson
parents: 1994
diff changeset
   709
  redundant cases*)
f8230821f1e8 Reordering of premises for cut theorems, and new law MPair_synth_analz
paulson
parents: 1994
diff changeset
   710
goal thy "({|X,Y|} : synth (analz H)) = \
f8230821f1e8 Reordering of premises for cut theorems, and new law MPair_synth_analz
paulson
parents: 1994
diff changeset
   711
\         (X : synth (analz H) & Y : synth (analz H))";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   712
by (Blast_tac 1);
1998
f8230821f1e8 Reordering of premises for cut theorems, and new law MPair_synth_analz
paulson
parents: 1994
diff changeset
   713
qed "MPair_synth_analz";
f8230821f1e8 Reordering of premises for cut theorems, and new law MPair_synth_analz
paulson
parents: 1994
diff changeset
   714
f8230821f1e8 Reordering of premises for cut theorems, and new law MPair_synth_analz
paulson
parents: 1994
diff changeset
   715
AddIffs [MPair_synth_analz];
1929
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   716
2154
913b4fc7670a New, purely illustrative result Crypt_synth_analz
paulson
parents: 2102
diff changeset
   717
goal thy "!!K. [| Key K : analz H;  Key (invKey K) : analz H |] \
2284
80ebd1a213fd Swapped arguments of Crypt (for clarity and because it is conventional)
paulson
parents: 2170
diff changeset
   718
\              ==> (Crypt K X : synth (analz H)) = (X : synth (analz H))";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   719
by (Blast_tac 1);
2154
913b4fc7670a New, purely illustrative result Crypt_synth_analz
paulson
parents: 2102
diff changeset
   720
qed "Crypt_synth_analz";
913b4fc7670a New, purely illustrative result Crypt_synth_analz
paulson
parents: 2102
diff changeset
   721
1929
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   722
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   723
goal thy "!!K. X ~: synth (analz H) \
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   724
\   ==> (Hash{|X,Y|} : synth (analz H)) = (Hash{|X,Y|} : analz H)";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   725
by (Blast_tac 1);
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   726
qed "Hash_synth_analz";
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   727
Addsimps [Hash_synth_analz];
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   728
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   729
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   730
(**** HPair: a combination of Hash and MPair ****)
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   731
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   732
(*** Freeness ***)
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   733
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   734
goalw thy [HPair_def] "Agent A ~= Hash[X] Y";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   735
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   736
qed "Agent_neq_HPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   737
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   738
goalw thy [HPair_def] "Nonce N ~= Hash[X] Y";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   739
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   740
qed "Nonce_neq_HPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   741
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   742
goalw thy [HPair_def] "Key K ~= Hash[X] Y";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   743
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   744
qed "Key_neq_HPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   745
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   746
goalw thy [HPair_def] "Hash Z ~= Hash[X] Y";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   747
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   748
qed "Hash_neq_HPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   749
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   750
goalw thy [HPair_def] "Crypt K X' ~= Hash[X] Y";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   751
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   752
qed "Crypt_neq_HPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   753
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   754
val HPair_neqs = [Agent_neq_HPair, Nonce_neq_HPair, 
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   755
                  Key_neq_HPair, Hash_neq_HPair, Crypt_neq_HPair];
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   756
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   757
AddIffs HPair_neqs;
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   758
AddIffs (HPair_neqs RL [not_sym]);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   759
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   760
goalw thy [HPair_def] "(Hash[X'] Y' = Hash[X] Y) = (X' = X & Y'=Y)";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   761
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   762
qed "HPair_eq";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   763
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   764
goalw thy [HPair_def] "({|X',Y'|} = Hash[X] Y) = (X' = Hash{|X,Y|} & Y'=Y)";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   765
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   766
qed "MPair_eq_HPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   767
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   768
goalw thy [HPair_def] "(Hash[X] Y = {|X',Y'|}) = (X' = Hash{|X,Y|} & Y'=Y)";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   769
by (Auto_tac());
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   770
qed "HPair_eq_MPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   771
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   772
AddIffs [HPair_eq, MPair_eq_HPair, HPair_eq_MPair];
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   773
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   774
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   775
(*** Specialized laws, proved in terms of those for Hash and MPair ***)
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   776
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   777
goalw thy [HPair_def] "keysFor (insert (Hash[X] Y) H) = keysFor H";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   778
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   779
qed "keysFor_insert_HPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   780
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   781
goalw thy [HPair_def]
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   782
    "parts (insert (Hash[X] Y) H) = \
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   783
\    insert (Hash[X] Y) (insert (Hash{|X,Y|}) (parts (insert Y H)))";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   784
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   785
qed "parts_insert_HPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   786
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   787
goalw thy [HPair_def]
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   788
    "analz (insert (Hash[X] Y) H) = \
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   789
\    insert (Hash[X] Y) (insert (Hash{|X,Y|}) (analz (insert Y H)))";
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   790
by (Simp_tac 1);
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   791
qed "analz_insert_HPair";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   792
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   793
goalw thy [HPair_def] "!!H. X ~: synth (analz H) \
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   794
\   ==> (Hash[X] Y : synth (analz H)) = \
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   795
\       (Hash {|X, Y|} : analz H & Y : synth (analz H))";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   796
by (Simp_tac 1);
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   797
by (Blast_tac 1);
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   798
qed "HPair_synth_analz";
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   799
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   800
Addsimps [keysFor_insert_HPair, parts_insert_HPair, analz_insert_HPair, 
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   801
          HPair_synth_analz, HPair_synth_analz];
2484
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   802
596a5b5a68ff Incorporation of HPair into Message
paulson
parents: 2415
diff changeset
   803
1929
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   804
(*We do NOT want Crypt... messages broken up in protocols!!*)
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   805
Delrules partsEs;
f0839bab4b00 Working version of NS, messages 1-3, WITH INTERLEAVING
paulson
parents: 1913
diff changeset
   806
2327
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   807
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   808
(** Rewrites to push in Key and Crypt messages, so that other messages can
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   809
    be pulled out using the analz_insert rules **)
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   810
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   811
fun insComm thy x y = read_instantiate_sg (sign_of thy) [("x",x), ("y",y)] 
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   812
                          insert_commute;
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   813
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   814
val pushKeys = map (insComm thy "Key ?K") 
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   815
                   ["Agent ?C", "Nonce ?N", "Hash ?X", 
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   816
                    "MPair ?X ?Y", "Crypt ?X ?K'"];
2327
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   817
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   818
val pushCrypts = map (insComm thy "Crypt ?X ?K") 
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   819
                     ["Agent ?C", "Nonce ?N", "Hash ?X'", "MPair ?X' ?Y"];
2327
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   820
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   821
(*Cannot be added with Addsimps -- we don't always want to re-order messages*)
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   822
val pushes = pushKeys@pushCrypts;
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   823
3121
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   824
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   825
(*** Tactics useful for many protocol proofs ***)
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   826
3470
8160cc3f6d40 Added a comment
paulson
parents: 3449
diff changeset
   827
(*Prove base case (subgoal i) and simplify others.  A typical base case
8160cc3f6d40 Added a comment
paulson
parents: 3449
diff changeset
   828
  concerns  Crypt K X ~: Key``shrK``lost  and cannot be proved by rewriting
8160cc3f6d40 Added a comment
paulson
parents: 3449
diff changeset
   829
  alone.*)
3121
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   830
fun prove_simple_subgoals_tac i = 
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   831
    fast_tac (!claset addss (!simpset)) i THEN
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   832
    ALLGOALS Asm_simp_tac;
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   833
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   834
fun Fake_parts_insert_tac i = 
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   835
    blast_tac (!claset addDs [impOfSubs analz_subset_parts,
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   836
			      impOfSubs Fake_parts_insert]) i;
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   837
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   838
(*Apply rules to break down assumptions of the form
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   839
  Y : parts(insert X H)  and  Y : analz(insert X H)
cbb6c0c1c58a Conversion to use blast_tac (with other improvements)
paulson
parents: 3102
diff changeset
   840
*)
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   841
val Fake_insert_tac = 
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   842
    dresolve_tac [impOfSubs Fake_analz_insert,
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   843
                  impOfSubs Fake_parts_insert] THEN'
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   844
    eresolve_tac [asm_rl, synth.Inj];
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   845
3449
6b17f82bbf01 New comments; a tidied proof
paulson
parents: 3431
diff changeset
   846
(*Analysis of Fake cases.  Also works for messages that forward unknown parts,
6b17f82bbf01 New comments; a tidied proof
paulson
parents: 3431
diff changeset
   847
  but this application is no longer necessary if analz_insert_eq is used.
2327
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   848
  Abstraction over i is ESSENTIAL: it delays the dereferencing of claset
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   849
  DEPENDS UPON "X" REFERRING TO THE FRADULENT MESSAGE *)
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   850
fun spy_analz_tac i =
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   851
  DETERM
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   852
   (SELECT_GOAL
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   853
     (EVERY 
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   854
      [  (*push in occurrences of X...*)
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   855
       (REPEAT o CHANGED)
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   856
           (res_inst_tac [("x1","X")] (insert_commute RS ssubst) 1),
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   857
       (*...allowing further simplifications*)
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   858
       simp_tac (!simpset setloop split_tac [expand_if]) 1,
3476
1be4fee7606b spy_analz_tac: Restored iffI to the list of rules used to break down
paulson
parents: 3470
diff changeset
   859
       REPEAT (FIRSTGOAL (resolve_tac [allI,impI,notI,conjI,iffI])),
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   860
       DEPTH_SOLVE 
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   861
         (REPEAT (Fake_insert_tac 1) THEN Asm_full_simp_tac 1
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   862
          THEN
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
   863
          IF_UNSOLVED (Blast.depth_tac
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
   864
		       (!claset addIs [impOfSubs analz_mono,
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
   865
				       impOfSubs analz_subset_parts]) 2 1))
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   866
       ]) i);
2327
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   867
2415
46de4b035f00 New tactic: prove_unique_tac
paulson
parents: 2373
diff changeset
   868
(** Useful in many uniqueness proofs **)
2327
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   869
fun ex_strip_tac i = REPEAT (swap_res_tac [exI, conjI] i) THEN 
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   870
                     assume_tac (i+1);
00ac25b2791d Moved much common material to Message.ML
paulson
parents: 2284
diff changeset
   871
2415
46de4b035f00 New tactic: prove_unique_tac
paulson
parents: 2373
diff changeset
   872
(*Apply the EX-ALL quantifification to prove uniqueness theorems in 
46de4b035f00 New tactic: prove_unique_tac
paulson
parents: 2373
diff changeset
   873
  their standard form*)
46de4b035f00 New tactic: prove_unique_tac
paulson
parents: 2373
diff changeset
   874
fun prove_unique_tac lemma = 
46de4b035f00 New tactic: prove_unique_tac
paulson
parents: 2373
diff changeset
   875
  EVERY' [dtac lemma,
2516
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   876
          REPEAT o (mp_tac ORELSE' eresolve_tac [asm_rl,exE]),
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   877
          (*Duplicate the assumption*)
4d68fbe6378b Now with Andy Gordon's treatment of freshness to replace newN/K
paulson
parents: 2484
diff changeset
   878
          forw_inst_tac [("psi", "ALL C.?P(C)")] asm_rl,
3102
4d01cdc119d2 Some blast_tac calls; more needed
paulson
parents: 2948
diff changeset
   879
          Blast.depth_tac (!claset addSDs [spec]) 0];
2415
46de4b035f00 New tactic: prove_unique_tac
paulson
parents: 2373
diff changeset
   880
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   881
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   882
(*Needed occasionally with spy_analz_tac, e.g. in analz_insert_Key_newK*)
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   883
goal Set.thy "A Un (B Un A) = B Un A";
2891
d8f254ad1ab9 Calls Blast_tac
paulson
parents: 2637
diff changeset
   884
by (Blast_tac 1);
2373
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   885
val Un_absorb3 = result();
490ffa16952e Addition of the Hash constructor
paulson
parents: 2327
diff changeset
   886
Addsimps [Un_absorb3];