1 % |
|
2 \begin{isabellebody}% |
|
3 \def\isabellecontext{NS{\isaliteral{5F}{\isacharunderscore}}Public}% |
|
4 % |
|
5 \isadelimtheory |
|
6 % |
|
7 \endisadelimtheory |
|
8 % |
|
9 \isatagtheory |
|
10 % |
|
11 \endisatagtheory |
|
12 {\isafoldtheory}% |
|
13 % |
|
14 \isadelimtheory |
|
15 % |
|
16 \endisadelimtheory |
|
17 % |
|
18 \isamarkupsection{Modelling the Protocol \label{sec:modelling}% |
|
19 } |
|
20 \isamarkuptrue% |
|
21 % |
|
22 \begin{figure} |
|
23 \begin{isabelle} |
|
24 \isacommand{inductive{\isaliteral{5F}{\isacharunderscore}}set}\isamarkupfalse% |
|
25 \ ns{\isaliteral{5F}{\isacharunderscore}}public\ {\isaliteral{3A}{\isacharcolon}}{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{22}{\isachardoublequoteopen}}event\ list\ set{\isaliteral{22}{\isachardoublequoteclose}}\isanewline |
|
26 \ \ \isakeyword{where}\isanewline |
|
27 \isanewline |
|
28 \ \ \ Nil{\isaliteral{3A}{\isacharcolon}}\ \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{5B}{\isacharbrackleft}}{\isaliteral{5D}{\isacharbrackright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{22}{\isachardoublequoteclose}}\isanewline |
|
29 \isanewline |
|
30 \isanewline |
|
31 \ {\isaliteral{7C}{\isacharbar}}\ Fake{\isaliteral{3A}{\isacharcolon}}\ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}evsf\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{3B}{\isacharsemicolon}}\ \ X\ {\isaliteral{5C3C696E3E}{\isasymin}}\ synth\ {\isaliteral{28}{\isacharparenleft}}analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evsf{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
32 \ \ \ \ \ \ \ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ Says\ Spy\ B\ X\ \ {\isaliteral{23}{\isacharhash}}\ evsf\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{22}{\isachardoublequoteclose}}\isanewline |
|
33 \isanewline |
|
34 \isanewline |
|
35 \ {\isaliteral{7C}{\isacharbar}}\ NS{\isadigit{1}}{\isaliteral{3A}{\isacharcolon}}\ \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}evs{\isadigit{1}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{3B}{\isacharsemicolon}}\ \ Nonce\ NA\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ used\ evs{\isadigit{1}}{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
36 \ \ \ \ \ \ \ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ Says\ A\ B\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Agent\ A{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\isanewline |
|
37 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\isaliteral{23}{\isacharhash}}\ evs{\isadigit{1}}\ \ {\isaliteral{5C3C696E3E}{\isasymin}}\ \ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{22}{\isachardoublequoteclose}}\isanewline |
|
38 \isanewline |
|
39 \isanewline |
|
40 \ {\isaliteral{7C}{\isacharbar}}\ NS{\isadigit{2}}{\isaliteral{3A}{\isacharcolon}}\ \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}evs{\isadigit{2}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{3B}{\isacharsemicolon}}\ \ Nonce\ NB\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ used\ evs{\isadigit{2}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
41 \ \ \ \ \ \ \ \ \ \ \ Says\ A{\isaliteral{27}{\isacharprime}}\ B\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Agent\ A{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs{\isadigit{2}}{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
42 \ \ \ \ \ \ \ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ Says\ B\ A\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Nonce\ NB{\isaliteral{2C}{\isacharcomma}}\ Agent\ B{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\isanewline |
|
43 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\isaliteral{23}{\isacharhash}}\ evs{\isadigit{2}}\ \ {\isaliteral{5C3C696E3E}{\isasymin}}\ \ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{22}{\isachardoublequoteclose}}\isanewline |
|
44 \isanewline |
|
45 \isanewline |
|
46 \ {\isaliteral{7C}{\isacharbar}}\ NS{\isadigit{3}}{\isaliteral{3A}{\isacharcolon}}\ \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}evs{\isadigit{3}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
47 \ \ \ \ \ \ \ \ \ \ \ Says\ A\ \ B\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Agent\ A{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs{\isadigit{3}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
48 \ \ \ \ \ \ \ \ \ \ \ Says\ B{\isaliteral{27}{\isacharprime}}\ A\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Nonce\ NB{\isaliteral{2C}{\isacharcomma}}\ Agent\ B{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\isanewline |
|
49 \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs{\isadigit{3}}{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
50 \ \ \ \ \ \ \ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ Says\ A\ B\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{28}{\isacharparenleft}}Nonce\ NB{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{23}{\isacharhash}}\ evs{\isadigit{3}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{22}{\isachardoublequoteclose}}% |
|
51 \end{isabelle} |
|
52 \caption{An Inductive Protocol Definition}\label{fig:ns_public} |
|
53 \end{figure} |
|
54 % |
|
55 \begin{isamarkuptext}% |
|
56 Let us formalize the Needham-Schroeder public-key protocol, as corrected by |
|
57 Lowe: |
|
58 \begin{alignat*% |
|
59 }{2} |
|
60 &1.&\quad A\to B &: \comp{Na,A}\sb{Kb} \\ |
|
61 &2.&\quad B\to A &: \comp{Na,Nb,B}\sb{Ka} \\ |
|
62 &3.&\quad A\to B &: \comp{Nb}\sb{Kb} |
|
63 \end{alignat*% |
|
64 } |
|
65 |
|
66 Each protocol step is specified by a rule of an inductive definition. An |
|
67 event trace has type \isa{event\ list}, so we declare the constant |
|
68 \isa{ns{\isaliteral{5F}{\isacharunderscore}}public} to be a set of such traces. |
|
69 |
|
70 Figure~\ref{fig:ns_public} presents the inductive definition. The |
|
71 \isa{Nil} rule introduces the empty trace. The \isa{Fake} rule models the |
|
72 adversary's sending a message built from components taken from past |
|
73 traffic, expressed using the functions \isa{synth} and |
|
74 \isa{analz}. |
|
75 The next three rules model how honest agents would perform the three |
|
76 protocol steps. |
|
77 |
|
78 Here is a detailed explanation of rule \isa{NS{\isadigit{2}}}. |
|
79 A trace containing an event of the form |
|
80 \begin{isabelle}% |
|
81 \ \ \ \ \ Says\ A{\isaliteral{27}{\isacharprime}}\ B\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Agent\ A{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}% |
|
82 \end{isabelle} |
|
83 may be extended by an event of the form |
|
84 \begin{isabelle}% |
|
85 \ \ \ \ \ Says\ B\ A\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Nonce\ NB{\isaliteral{2C}{\isacharcomma}}\ Agent\ B{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}% |
|
86 \end{isabelle} |
|
87 where \isa{NB} is a fresh nonce: \isa{Nonce\ NB\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ used\ evs{\isadigit{2}}}. |
|
88 Writing the sender as \isa{A{\isaliteral{27}{\isacharprime}}} indicates that \isa{B} does not |
|
89 know who sent the message. Calling the trace variable \isa{evs{\isadigit{2}}} rather |
|
90 than simply \isa{evs} helps us know where we are in a proof after many |
|
91 case-splits: every subgoal mentioning \isa{evs{\isadigit{2}}} involves message~2 of the |
|
92 protocol. |
|
93 |
|
94 Benefits of this approach are simplicity and clarity. The semantic model |
|
95 is set theory, proofs are by induction and the translation from the informal |
|
96 notation to the inductive rules is straightforward.% |
|
97 \end{isamarkuptext}% |
|
98 \isamarkuptrue% |
|
99 % |
|
100 \isamarkupsection{Proving Elementary Properties \label{sec:regularity}% |
|
101 } |
|
102 \isamarkuptrue% |
|
103 % |
|
104 \isadelimproof |
|
105 % |
|
106 \endisadelimproof |
|
107 % |
|
108 \isatagproof |
|
109 % |
|
110 \endisatagproof |
|
111 {\isafoldproof}% |
|
112 % |
|
113 \isadelimproof |
|
114 % |
|
115 \endisadelimproof |
|
116 % |
|
117 \begin{isamarkuptext}% |
|
118 Secrecy properties can be hard to prove. The conclusion of a typical |
|
119 secrecy theorem is |
|
120 \isa{X\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}}. The difficulty arises from |
|
121 having to reason about \isa{analz}, or less formally, showing that the spy |
|
122 can never learn~\isa{X}. Much easier is to prove that \isa{X} can never |
|
123 occur at all. Such \emph{regularity} properties are typically expressed |
|
124 using \isa{parts} rather than \isa{analz}. |
|
125 |
|
126 The following lemma states that \isa{A}'s private key is potentially |
|
127 known to the spy if and only if \isa{A} belongs to the set \isa{bad} of |
|
128 compromised agents. The statement uses \isa{parts}: the very presence of |
|
129 \isa{A}'s private key in a message, whether protected by encryption or |
|
130 not, is enough to confirm that \isa{A} is compromised. The proof, like |
|
131 nearly all protocol proofs, is by induction over traces.% |
|
132 \end{isamarkuptext}% |
|
133 \isamarkuptrue% |
|
134 \isacommand{lemma}\isamarkupfalse% |
|
135 \ Spy{\isaliteral{5F}{\isacharunderscore}}see{\isaliteral{5F}{\isacharunderscore}}priK\ {\isaliteral{5B}{\isacharbrackleft}}simp{\isaliteral{5D}{\isacharbrackright}}{\isaliteral{3A}{\isacharcolon}}\isanewline |
|
136 \ \ \ \ \ \ {\isaliteral{22}{\isachardoublequoteopen}}evs\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public\isanewline |
|
137 \ \ \ \ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ {\isaliteral{28}{\isacharparenleft}}Key\ {\isaliteral{28}{\isacharparenleft}}priK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ parts\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ {\isaliteral{28}{\isacharparenleft}}A\ {\isaliteral{5C3C696E3E}{\isasymin}}\ bad{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}\isanewline |
|
138 % |
|
139 \isadelimproof |
|
140 % |
|
141 \endisadelimproof |
|
142 % |
|
143 \isatagproof |
|
144 \isacommand{apply}\isamarkupfalse% |
|
145 \ {\isaliteral{28}{\isacharparenleft}}erule\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{2E}{\isachardot}}induct{\isaliteral{2C}{\isacharcomma}}\ simp{\isaliteral{5F}{\isacharunderscore}}all{\isaliteral{29}{\isacharparenright}}% |
|
146 \begin{isamarkuptxt}% |
|
147 The induction yields five subgoals, one for each rule in the definition of |
|
148 \isa{ns{\isaliteral{5F}{\isacharunderscore}}public}. The idea is to prove that the protocol property holds initially |
|
149 (rule \isa{Nil}), is preserved by each of the legitimate protocol steps (rules |
|
150 \isa{NS{\isadigit{1}}}--\isa{{\isadigit{3}}}), and even is preserved in the face of anything the |
|
151 spy can do (rule \isa{Fake}). |
|
152 |
|
153 The proof is trivial. No legitimate protocol rule sends any keys |
|
154 at all, so only \isa{Fake} is relevant. Indeed, simplification leaves |
|
155 only the \isa{Fake} case, as indicated by the variable name \isa{evsf}: |
|
156 \begin{isabelle}% |
|
157 \ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ {\isaliteral{5C3C416E643E}{\isasymAnd}}evsf\ X{\isaliteral{2E}{\isachardot}}\isanewline |
|
158 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ }{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}evsf\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
159 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ \ }{\isaliteral{28}{\isacharparenleft}}Key\ {\isaliteral{28}{\isacharparenleft}}priK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ parts\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evsf{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\ {\isaliteral{28}{\isacharparenleft}}A\ {\isaliteral{5C3C696E3E}{\isasymin}}\ bad{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
160 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ \ }X\ {\isaliteral{5C3C696E3E}{\isasymin}}\ synth\ {\isaliteral{28}{\isacharparenleft}}analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evsf{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
161 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ }{\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ {\isaliteral{28}{\isacharparenleft}}Key\ {\isaliteral{28}{\isacharparenleft}}priK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ parts\ {\isaliteral{28}{\isacharparenleft}}insert\ X\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evsf{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\isanewline |
|
162 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ }{\isaliteral{28}{\isacharparenleft}}A\ {\isaliteral{5C3C696E3E}{\isasymin}}\ bad{\isaliteral{29}{\isacharparenright}}% |
|
163 \end{isabelle}% |
|
164 \end{isamarkuptxt}% |
|
165 \isamarkuptrue% |
|
166 \isacommand{by}\isamarkupfalse% |
|
167 \ blast% |
|
168 \endisatagproof |
|
169 {\isafoldproof}% |
|
170 % |
|
171 \isadelimproof |
|
172 % |
|
173 \endisadelimproof |
|
174 % |
|
175 \isadelimproof |
|
176 % |
|
177 \endisadelimproof |
|
178 % |
|
179 \isatagproof |
|
180 % |
|
181 \endisatagproof |
|
182 {\isafoldproof}% |
|
183 % |
|
184 \isadelimproof |
|
185 % |
|
186 \endisadelimproof |
|
187 % |
|
188 \begin{isamarkuptext}% |
|
189 The \isa{Fake} case is proved automatically. If |
|
190 \isa{priK\ A} is in the extended trace then either (1) it was already in the |
|
191 original trace or (2) it was |
|
192 generated by the spy, who must have known this key already. |
|
193 Either way, the induction hypothesis applies. |
|
194 |
|
195 \emph{Unicity} lemmas are regularity lemmas stating that specified items |
|
196 can occur only once in a trace. The following lemma states that a nonce |
|
197 cannot be used both as $Na$ and as $Nb$ unless |
|
198 it is known to the spy. Intuitively, it holds because honest agents |
|
199 always choose fresh values as nonces; only the spy might reuse a value, |
|
200 and he doesn't know this particular value. The proof script is short: |
|
201 induction, simplification, \isa{blast}. The first line uses the rule |
|
202 \isa{rev{\isaliteral{5F}{\isacharunderscore}}mp} to prepare the induction by moving two assumptions into the |
|
203 induction formula.% |
|
204 \end{isamarkuptext}% |
|
205 \isamarkuptrue% |
|
206 \isacommand{lemma}\isamarkupfalse% |
|
207 \ no{\isaliteral{5F}{\isacharunderscore}}nonce{\isaliteral{5F}{\isacharunderscore}}NS{\isadigit{1}}{\isaliteral{5F}{\isacharunderscore}}NS{\isadigit{2}}{\isaliteral{3A}{\isacharcolon}}\isanewline |
|
208 \ \ \ \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ C{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}NA{\isaliteral{27}{\isacharprime}}{\isaliteral{2C}{\isacharcomma}}\ Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Agent\ D{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ parts\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
209 \ \ \ \ \ \ Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Agent\ A{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ parts\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
210 \ \ \ \ \ \ evs\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
211 \ \ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ Nonce\ NA\ {\isaliteral{5C3C696E3E}{\isasymin}}\ analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}\isanewline |
|
212 % |
|
213 \isadelimproof |
|
214 % |
|
215 \endisadelimproof |
|
216 % |
|
217 \isatagproof |
|
218 \isacommand{apply}\isamarkupfalse% |
|
219 \ {\isaliteral{28}{\isacharparenleft}}erule\ rev{\isaliteral{5F}{\isacharunderscore}}mp{\isaliteral{2C}{\isacharcomma}}\ erule\ rev{\isaliteral{5F}{\isacharunderscore}}mp{\isaliteral{29}{\isacharparenright}}\isanewline |
|
220 \isacommand{apply}\isamarkupfalse% |
|
221 \ {\isaliteral{28}{\isacharparenleft}}erule\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{2E}{\isachardot}}induct{\isaliteral{2C}{\isacharcomma}}\ simp{\isaliteral{5F}{\isacharunderscore}}all{\isaliteral{29}{\isacharparenright}}\isanewline |
|
222 \isacommand{apply}\isamarkupfalse% |
|
223 \ {\isaliteral{28}{\isacharparenleft}}blast\ intro{\isaliteral{3A}{\isacharcolon}}\ analz{\isaliteral{5F}{\isacharunderscore}}insertI{\isaliteral{29}{\isacharparenright}}{\isaliteral{2B}{\isacharplus}}\isanewline |
|
224 \isacommand{done}\isamarkupfalse% |
|
225 % |
|
226 \endisatagproof |
|
227 {\isafoldproof}% |
|
228 % |
|
229 \isadelimproof |
|
230 % |
|
231 \endisadelimproof |
|
232 % |
|
233 \begin{isamarkuptext}% |
|
234 The following unicity lemma states that, if \isa{NA} is secret, then its |
|
235 appearance in any instance of message~1 determines the other components. |
|
236 The proof is similar to the previous one.% |
|
237 \end{isamarkuptext}% |
|
238 \isamarkuptrue% |
|
239 \isacommand{lemma}\isamarkupfalse% |
|
240 \ unique{\isaliteral{5F}{\isacharunderscore}}NA{\isaliteral{3A}{\isacharcolon}}\isanewline |
|
241 \ \ \ \ \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}Crypt{\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ \ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Agent\ A\ {\isaliteral{5C3C7262726163653E}{\isasymrbrace}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ parts{\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
242 \ \ \ \ \ \ \ Crypt{\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{27}{\isacharprime}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Agent\ A{\isaliteral{27}{\isacharprime}}{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ parts{\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
243 \ \ \ \ \ \ \ Nonce\ NA\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\ evs\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
244 \ \ \ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ A{\isaliteral{3D}{\isacharequal}}A{\isaliteral{27}{\isacharprime}}\ {\isaliteral{5C3C616E643E}{\isasymand}}\ B{\isaliteral{3D}{\isacharequal}}B{\isaliteral{27}{\isacharprime}}{\isaliteral{22}{\isachardoublequoteclose}}% |
|
245 \isadelimproof |
|
246 % |
|
247 \endisadelimproof |
|
248 % |
|
249 \isatagproof |
|
250 % |
|
251 \endisatagproof |
|
252 {\isafoldproof}% |
|
253 % |
|
254 \isadelimproof |
|
255 % |
|
256 \endisadelimproof |
|
257 % |
|
258 \isamarkupsection{Proving Secrecy Theorems \label{sec:secrecy}% |
|
259 } |
|
260 \isamarkuptrue% |
|
261 % |
|
262 \isadelimproof |
|
263 % |
|
264 \endisadelimproof |
|
265 % |
|
266 \isatagproof |
|
267 % |
|
268 \endisatagproof |
|
269 {\isafoldproof}% |
|
270 % |
|
271 \isadelimproof |
|
272 % |
|
273 \endisadelimproof |
|
274 % |
|
275 \isadelimproof |
|
276 % |
|
277 \endisadelimproof |
|
278 % |
|
279 \isatagproof |
|
280 % |
|
281 \endisatagproof |
|
282 {\isafoldproof}% |
|
283 % |
|
284 \isadelimproof |
|
285 % |
|
286 \endisadelimproof |
|
287 % |
|
288 \isadelimproof |
|
289 % |
|
290 \endisadelimproof |
|
291 % |
|
292 \isatagproof |
|
293 % |
|
294 \endisatagproof |
|
295 {\isafoldproof}% |
|
296 % |
|
297 \isadelimproof |
|
298 % |
|
299 \endisadelimproof |
|
300 % |
|
301 \isadelimproof |
|
302 % |
|
303 \endisadelimproof |
|
304 % |
|
305 \isatagproof |
|
306 % |
|
307 \endisatagproof |
|
308 {\isafoldproof}% |
|
309 % |
|
310 \isadelimproof |
|
311 % |
|
312 \endisadelimproof |
|
313 % |
|
314 \isadelimproof |
|
315 % |
|
316 \endisadelimproof |
|
317 % |
|
318 \isatagproof |
|
319 % |
|
320 \endisatagproof |
|
321 {\isafoldproof}% |
|
322 % |
|
323 \isadelimproof |
|
324 % |
|
325 \endisadelimproof |
|
326 % |
|
327 \begin{isamarkuptext}% |
|
328 The secrecy theorems for Bob (the second participant) are especially |
|
329 important because they fail for the original protocol. The following |
|
330 theorem states that if Bob sends message~2 to Alice, and both agents are |
|
331 uncompromised, then Bob's nonce will never reach the spy.% |
|
332 \end{isamarkuptext}% |
|
333 \isamarkuptrue% |
|
334 \isacommand{theorem}\isamarkupfalse% |
|
335 \ Spy{\isaliteral{5F}{\isacharunderscore}}not{\isaliteral{5F}{\isacharunderscore}}see{\isaliteral{5F}{\isacharunderscore}}NB\ {\isaliteral{5B}{\isacharbrackleft}}dest{\isaliteral{5D}{\isacharbrackright}}{\isaliteral{3A}{\isacharcolon}}\isanewline |
|
336 \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}Says\ B\ A\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Nonce\ NB{\isaliteral{2C}{\isacharcomma}}\ Agent\ B{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
337 \ \ \ A\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ bad{\isaliteral{3B}{\isacharsemicolon}}\ \ B\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ bad{\isaliteral{3B}{\isacharsemicolon}}\ \ evs\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
338 \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ Nonce\ NB\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isaliteral{29}{\isacharparenright}}{\isaliteral{22}{\isachardoublequoteclose}}% |
|
339 \isadelimproof |
|
340 % |
|
341 \endisadelimproof |
|
342 % |
|
343 \isatagproof |
|
344 % |
|
345 \begin{isamarkuptxt}% |
|
346 To prove it, we must formulate the induction properly (one of the |
|
347 assumptions mentions~\isa{evs}), apply induction, and simplify:% |
|
348 \end{isamarkuptxt}% |
|
349 \isamarkuptrue% |
|
350 \isacommand{apply}\isamarkupfalse% |
|
351 \ {\isaliteral{28}{\isacharparenleft}}erule\ rev{\isaliteral{5F}{\isacharunderscore}}mp{\isaliteral{2C}{\isacharcomma}}\ erule\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{2E}{\isachardot}}induct{\isaliteral{2C}{\isacharcomma}}\ simp{\isaliteral{5F}{\isacharunderscore}}all{\isaliteral{29}{\isacharparenright}}% |
|
352 \begin{isamarkuptxt}% |
|
353 The proof states are too complicated to present in full. |
|
354 Let's examine the simplest subgoal, that for message~1. The following |
|
355 event has just occurred: |
|
356 \[ 1.\quad A'\to B' : \comp{Na',A'}\sb{Kb'} \] |
|
357 The variables above have been primed because this step |
|
358 belongs to a different run from that referred to in the theorem |
|
359 statement --- the theorem |
|
360 refers to a past instance of message~2, while this subgoal |
|
361 concerns message~1 being sent just now. |
|
362 In the Isabelle subgoal, instead of primed variables like $B'$ and $Na'$ |
|
363 we have \isa{Ba} and~\isa{NAa}: |
|
364 \begin{isabelle}% |
|
365 \ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ {\isaliteral{5C3C416E643E}{\isasymAnd}}evs{\isadigit{1}}\ NAa\ Ba{\isaliteral{2E}{\isachardot}}\isanewline |
|
366 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ }{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}A\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ bad{\isaliteral{3B}{\isacharsemicolon}}\ B\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ bad{\isaliteral{3B}{\isacharsemicolon}}\ evs{\isadigit{1}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
367 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ \ }Says\ B\ A\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Nonce\ NB{\isaliteral{2C}{\isacharcomma}}\ Agent\ B{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\isanewline |
|
368 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ \ }{\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs{\isadigit{1}}\ {\isaliteral{5C3C6C6F6E6772696768746172726F773E}{\isasymlongrightarrow}}\isanewline |
|
369 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ \ }Nonce\ NB\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ analz\ {\isaliteral{28}{\isacharparenleft}}knows\ Spy\ evs{\isadigit{1}}{\isaliteral{29}{\isacharparenright}}{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
370 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ \ }Nonce\ NAa\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ used\ evs{\isadigit{1}}{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
371 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ }{\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ Ba\ {\isaliteral{5C3C696E3E}{\isasymin}}\ bad\ {\isaliteral{5C3C6C6F6E6772696768746172726F773E}{\isasymlongrightarrow}}\isanewline |
|
372 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ }Says\ B\ A\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Nonce\ NB{\isaliteral{2C}{\isacharcomma}}\ Agent\ B{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\isanewline |
|
373 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ }{\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs{\isadigit{1}}\ {\isaliteral{5C3C6C6F6E6772696768746172726F773E}{\isasymlongrightarrow}}\isanewline |
|
374 \isaindent{\ {\isadigit{1}}{\isaliteral{2E}{\isachardot}}\ \ \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ }NB\ {\isaliteral{5C3C6E6F7465713E}{\isasymnoteq}}\ NAa% |
|
375 \end{isabelle} |
|
376 The simplifier has used a |
|
377 default simplification rule that does a case |
|
378 analysis for each encrypted message on whether or not the decryption key |
|
379 is compromised. |
|
380 \begin{isabelle}% |
|
381 analz\ {\isaliteral{28}{\isacharparenleft}}insert\ {\isaliteral{28}{\isacharparenleft}}Crypt\ K\ X{\isaliteral{29}{\isacharparenright}}\ H{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{3D}{\isacharequal}}\isanewline |
|
382 {\isaliteral{28}{\isacharparenleft}}if\ Key\ {\isaliteral{28}{\isacharparenleft}}invKey\ K{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ analz\ H\isanewline |
|
383 \isaindent{{\isaliteral{28}{\isacharparenleft}}}then\ insert\ {\isaliteral{28}{\isacharparenleft}}Crypt\ K\ X{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{28}{\isacharparenleft}}analz\ {\isaliteral{28}{\isacharparenleft}}insert\ X\ H{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\isanewline |
|
384 \isaindent{{\isaliteral{28}{\isacharparenleft}}}else\ insert\ {\isaliteral{28}{\isacharparenleft}}Crypt\ K\ X{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{28}{\isacharparenleft}}analz\ H{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\rulename{analz{\isaliteral{5F}{\isacharunderscore}}Crypt{\isaliteral{5F}{\isacharunderscore}}if}% |
|
385 \end{isabelle} |
|
386 The simplifier has also used \isa{Spy{\isaliteral{5F}{\isacharunderscore}}see{\isaliteral{5F}{\isacharunderscore}}priK}, proved in |
|
387 {\S}\ref{sec:regularity} above, to yield \isa{Ba\ {\isaliteral{5C3C696E3E}{\isasymin}}\ bad}. |
|
388 |
|
389 Recall that this subgoal concerns the case |
|
390 where the last message to be sent was |
|
391 \[ 1.\quad A'\to B' : \comp{Na',A'}\sb{Kb'}. \] |
|
392 This message can compromise $Nb$ only if $Nb=Na'$ and $B'$ is compromised, |
|
393 allowing the spy to decrypt the message. The Isabelle subgoal says |
|
394 precisely this, if we allow for its choice of variable names. |
|
395 Proving \isa{NB\ {\isaliteral{5C3C6E6F7465713E}{\isasymnoteq}}\ NAa} is easy: \isa{NB} was |
|
396 sent earlier, while \isa{NAa} is fresh; formally, we have |
|
397 the assumption \isa{Nonce\ NAa\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ used\ evs{\isadigit{1}}}. |
|
398 |
|
399 Note that our reasoning concerned \isa{B}'s participation in another |
|
400 run. Agents may engage in several runs concurrently, and some attacks work |
|
401 by interleaving the messages of two runs. With model checking, this |
|
402 possibility can cause a state-space explosion, and for us it |
|
403 certainly complicates proofs. The biggest subgoal concerns message~2. It |
|
404 splits into several cases, such as whether or not the message just sent is |
|
405 the very message mentioned in the theorem statement. |
|
406 Some of the cases are proved by unicity, others by |
|
407 the induction hypothesis. For all those complications, the proofs are |
|
408 automatic by \isa{blast} with the theorem \isa{no{\isaliteral{5F}{\isacharunderscore}}nonce{\isaliteral{5F}{\isacharunderscore}}NS{\isadigit{1}}{\isaliteral{5F}{\isacharunderscore}}NS{\isadigit{2}}}. |
|
409 |
|
410 The remaining theorems about the protocol are not hard to prove. The |
|
411 following one asserts a form of \emph{authenticity}: if |
|
412 \isa{B} has sent an instance of message~2 to~\isa{A} and has received the |
|
413 expected reply, then that reply really originated with~\isa{A}. The |
|
414 proof is a simple induction.% |
|
415 \end{isamarkuptxt}% |
|
416 \isamarkuptrue% |
|
417 % |
|
418 \endisatagproof |
|
419 {\isafoldproof}% |
|
420 % |
|
421 \isadelimproof |
|
422 % |
|
423 \endisadelimproof |
|
424 % |
|
425 \isadelimproof |
|
426 % |
|
427 \endisadelimproof |
|
428 % |
|
429 \isatagproof |
|
430 % |
|
431 \endisatagproof |
|
432 {\isafoldproof}% |
|
433 % |
|
434 \isadelimproof |
|
435 % |
|
436 \endisadelimproof |
|
437 \isacommand{theorem}\isamarkupfalse% |
|
438 \ B{\isaliteral{5F}{\isacharunderscore}}trusts{\isaliteral{5F}{\isacharunderscore}}NS{\isadigit{3}}{\isaliteral{3A}{\isacharcolon}}\isanewline |
|
439 \ {\isaliteral{22}{\isachardoublequoteopen}}{\isaliteral{5C3C6C6272616B6B3E}{\isasymlbrakk}}Says\ B\ A\ \ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ A{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Nonce\ NB{\isaliteral{2C}{\isacharcomma}}\ Agent\ B{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
440 \ \ \ Says\ A{\isaliteral{27}{\isacharprime}}\ B\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{28}{\isacharparenleft}}Nonce\ NB{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs{\isaliteral{3B}{\isacharsemicolon}}\isanewline |
|
441 \ \ \ A\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ bad{\isaliteral{3B}{\isacharsemicolon}}\ \ B\ {\isaliteral{5C3C6E6F74696E3E}{\isasymnotin}}\ bad{\isaliteral{3B}{\isacharsemicolon}}\ \ evs\ {\isaliteral{5C3C696E3E}{\isasymin}}\ ns{\isaliteral{5F}{\isacharunderscore}}public{\isaliteral{5C3C726272616B6B3E}{\isasymrbrakk}}\isanewline |
|
442 \ \ {\isaliteral{5C3C4C6F6E6772696768746172726F773E}{\isasymLongrightarrow}}\ Says\ A\ B\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{28}{\isacharparenleft}}Nonce\ NB{\isaliteral{29}{\isacharparenright}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs{\isaliteral{22}{\isachardoublequoteclose}}% |
|
443 \isadelimproof |
|
444 % |
|
445 \endisadelimproof |
|
446 % |
|
447 \isatagproof |
|
448 % |
|
449 \endisatagproof |
|
450 {\isafoldproof}% |
|
451 % |
|
452 \isadelimproof |
|
453 % |
|
454 \endisadelimproof |
|
455 % |
|
456 \isadelimproof |
|
457 % |
|
458 \endisadelimproof |
|
459 % |
|
460 \isatagproof |
|
461 % |
|
462 \endisatagproof |
|
463 {\isafoldproof}% |
|
464 % |
|
465 \isadelimproof |
|
466 % |
|
467 \endisadelimproof |
|
468 % |
|
469 \begin{isamarkuptext}% |
|
470 From similar assumptions, we can prove that \isa{A} started the protocol |
|
471 run by sending an instance of message~1 involving the nonce~\isa{NA}\@. |
|
472 For this theorem, the conclusion is |
|
473 \begin{isabelle}% |
|
474 Says\ A\ B\ {\isaliteral{28}{\isacharparenleft}}Crypt\ {\isaliteral{28}{\isacharparenleft}}pubK\ B{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C6C62726163653E}{\isasymlbrace}}Nonce\ NA{\isaliteral{2C}{\isacharcomma}}\ Agent\ A{\isaliteral{5C3C7262726163653E}{\isasymrbrace}}{\isaliteral{29}{\isacharparenright}}\ {\isaliteral{5C3C696E3E}{\isasymin}}\ set\ evs% |
|
475 \end{isabelle} |
|
476 Analogous theorems can be proved for~\isa{A}, stating that nonce~\isa{NA} |
|
477 remains secret and that message~2 really originates with~\isa{B}. Even the |
|
478 flawed protocol establishes these properties for~\isa{A}; |
|
479 the flaw only harms the second participant. |
|
480 |
|
481 \medskip |
|
482 |
|
483 Detailed information on this protocol verification technique can be found |
|
484 elsewhere~\cite{paulson-jcs}, including proofs of an Internet |
|
485 protocol~\cite{paulson-tls}. We must stress that the protocol discussed |
|
486 in this chapter is trivial. There are only three messages; no keys are |
|
487 exchanged; we merely have to prove that encrypted data remains secret. |
|
488 Real world protocols are much longer and distribute many secrets to their |
|
489 participants. To be realistic, the model has to include the possibility |
|
490 of keys being lost dynamically due to carelessness. If those keys have |
|
491 been used to encrypt other sensitive information, there may be cascading |
|
492 losses. We may still be able to establish a bound on the losses and to |
|
493 prove that other protocol runs function |
|
494 correctly~\cite{paulson-yahalom}. Proofs of real-world protocols follow |
|
495 the strategy illustrated above, but the subgoals can |
|
496 be much bigger and there are more of them. |
|
497 \index{protocols!security|)}% |
|
498 \end{isamarkuptext}% |
|
499 \isamarkuptrue% |
|
500 % |
|
501 \isadelimtheory |
|
502 % |
|
503 \endisadelimtheory |
|
504 % |
|
505 \isatagtheory |
|
506 % |
|
507 \endisatagtheory |
|
508 {\isafoldtheory}% |
|
509 % |
|
510 \isadelimtheory |
|
511 % |
|
512 \endisadelimtheory |
|
513 \end{isabellebody}% |
|
514 %%% Local Variables: |
|
515 %%% mode: latex |
|
516 %%% TeX-master: "root" |
|
517 %%% End: |
|