72 Here is a detailed explanation of rule \<open>NS2\<close>. |
72 Here is a detailed explanation of rule \<open>NS2\<close>. |
73 A trace containing an event of the form |
73 A trace containing an event of the form |
74 @{term [display,indent=5] "Says A' B (Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>)"} |
74 @{term [display,indent=5] "Says A' B (Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>)"} |
75 may be extended by an event of the form |
75 may be extended by an event of the form |
76 @{term [display,indent=5] "Says B A (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>)"} |
76 @{term [display,indent=5] "Says B A (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>)"} |
77 where \<open>NB\<close> is a fresh nonce: @{term "Nonce NB \<notin> used evs2"}. |
77 where \<open>NB\<close> is a fresh nonce: \<^term>\<open>Nonce NB \<notin> used evs2\<close>. |
78 Writing the sender as \<open>A'\<close> indicates that \<open>B\<close> does not |
78 Writing the sender as \<open>A'\<close> indicates that \<open>B\<close> does not |
79 know who sent the message. Calling the trace variable \<open>evs2\<close> rather |
79 know who sent the message. Calling the trace variable \<open>evs2\<close> rather |
80 than simply \<open>evs\<close> helps us know where we are in a proof after many |
80 than simply \<open>evs\<close> helps us know where we are in a proof after many |
81 case-splits: every subgoal mentioning \<open>evs2\<close> involves message~2 of the |
81 case-splits: every subgoal mentioning \<open>evs2\<close> involves message~2 of the |
82 protocol. |
82 protocol. |
110 (*>*) |
110 (*>*) |
111 |
111 |
112 text \<open> |
112 text \<open> |
113 Secrecy properties can be hard to prove. The conclusion of a typical |
113 Secrecy properties can be hard to prove. The conclusion of a typical |
114 secrecy theorem is |
114 secrecy theorem is |
115 @{term "X \<notin> analz (knows Spy evs)"}. The difficulty arises from |
115 \<^term>\<open>X \<notin> analz (knows Spy evs)\<close>. The difficulty arises from |
116 having to reason about \<open>analz\<close>, or less formally, showing that the spy |
116 having to reason about \<open>analz\<close>, or less formally, showing that the spy |
117 can never learn~\<open>X\<close>. Much easier is to prove that \<open>X\<close> can never |
117 can never learn~\<open>X\<close>. Much easier is to prove that \<open>X\<close> can never |
118 occur at all. Such \emph{regularity} properties are typically expressed |
118 occur at all. Such \emph{regularity} properties are typically expressed |
119 using \<open>parts\<close> rather than \<open>analz\<close>. |
119 using \<open>parts\<close> rather than \<open>analz\<close>. |
120 |
120 |
149 by auto |
149 by auto |
150 (*>*) |
150 (*>*) |
151 |
151 |
152 text \<open> |
152 text \<open> |
153 The \<open>Fake\<close> case is proved automatically. If |
153 The \<open>Fake\<close> case is proved automatically. If |
154 @{term "priK A"} is in the extended trace then either (1) it was already in the |
154 \<^term>\<open>priK A\<close> is in the extended trace then either (1) it was already in the |
155 original trace or (2) it was |
155 original trace or (2) it was |
156 generated by the spy, who must have known this key already. |
156 generated by the spy, who must have known this key already. |
157 Either way, the induction hypothesis applies. |
157 Either way, the induction hypothesis applies. |
158 |
158 |
159 \emph{Unicity} lemmas are regularity lemmas stating that specified items |
159 \emph{Unicity} lemmas are regularity lemmas stating that specified items |
305 default simplification rule that does a case |
305 default simplification rule that does a case |
306 analysis for each encrypted message on whether or not the decryption key |
306 analysis for each encrypted message on whether or not the decryption key |
307 is compromised. |
307 is compromised. |
308 @{named_thms [display,indent=0,margin=50] analz_Crypt_if [no_vars] (analz_Crypt_if)} |
308 @{named_thms [display,indent=0,margin=50] analz_Crypt_if [no_vars] (analz_Crypt_if)} |
309 The simplifier has also used \<open>Spy_see_priK\<close>, proved in |
309 The simplifier has also used \<open>Spy_see_priK\<close>, proved in |
310 {\S}\ref{sec:regularity} above, to yield @{term "Ba \<in> bad"}. |
310 {\S}\ref{sec:regularity} above, to yield \<^term>\<open>Ba \<in> bad\<close>. |
311 |
311 |
312 Recall that this subgoal concerns the case |
312 Recall that this subgoal concerns the case |
313 where the last message to be sent was |
313 where the last message to be sent was |
314 \[ 1.\quad A'\to B' : \comp{Na',A'}\sb{Kb'}. \] |
314 \[ 1.\quad A'\to B' : \comp{Na',A'}\sb{Kb'}. \] |
315 This message can compromise $Nb$ only if $Nb=Na'$ and $B'$ is compromised, |
315 This message can compromise $Nb$ only if $Nb=Na'$ and $B'$ is compromised, |
316 allowing the spy to decrypt the message. The Isabelle subgoal says |
316 allowing the spy to decrypt the message. The Isabelle subgoal says |
317 precisely this, if we allow for its choice of variable names. |
317 precisely this, if we allow for its choice of variable names. |
318 Proving @{term "NB \<noteq> NAa"} is easy: \<open>NB\<close> was |
318 Proving \<^term>\<open>NB \<noteq> NAa\<close> is easy: \<open>NB\<close> was |
319 sent earlier, while \<open>NAa\<close> is fresh; formally, we have |
319 sent earlier, while \<open>NAa\<close> is fresh; formally, we have |
320 the assumption @{term "Nonce NAa \<notin> used evs1"}. |
320 the assumption \<^term>\<open>Nonce NAa \<notin> used evs1\<close>. |
321 |
321 |
322 Note that our reasoning concerned \<open>B\<close>'s participation in another |
322 Note that our reasoning concerned \<open>B\<close>'s participation in another |
323 run. Agents may engage in several runs concurrently, and some attacks work |
323 run. Agents may engage in several runs concurrently, and some attacks work |
324 by interleaving the messages of two runs. With model checking, this |
324 by interleaving the messages of two runs. With model checking, this |
325 possibility can cause a state-space explosion, and for us it |
325 possibility can cause a state-space explosion, and for us it |