src/Doc/Tutorial/Protocol/NS_Public.thy
changeset 69597 ff784d5a5bfb
parent 69505 cc2d676d5395
child 76987 4c275405faae
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
    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