doc-src/TutorialI/Protocol/NS_Public.thy

     Author:     Lawrence C Paulson, Cambridge University Computer Laboratory
     Copyright   1996  University of Cambridge
 
 Inductive relation "ns_public" for the Needham-Schroeder Public-Key protocol.
 Version incorporating Lowe's fix (inclusion of B's identity in round 2).
-*)
-
-theory NS_Public imports Public begin
-
-inductive_set
-  ns_public :: "event list set"
+*)(*<*)
+theory NS_Public imports Public begin(*>*)
+
+section{* Modelling the Protocol \label{sec:modelling} *}
+
+text_raw {*
+\begin{figure}
+\begin{isabelle}
+*}
+
+inductive_set ns_public :: "event list set"
   where
-         (*Initial trace is empty*)
+
    Nil:  "[] \<in> ns_public"
 
-         (*The spy MAY say anything he CAN say.  We do not expect him to
-           invent new nonces here, but he can also use NS1.  Common to
-           all similar protocols.*)
- | Fake: "\<lbrakk>evs \<in> ns_public;  X \<in> synth (analz (knows Spy evs))\<rbrakk>
-          \<Longrightarrow> Says Spy B X  # evs \<in> ns_public"
-
-         (*Alice initiates a protocol run, sending a nonce to Bob*)
+
+ | Fake: "\<lbrakk>evsf \<in> ns_public;  X \<in> synth (analz (knows Spy evsf))\<rbrakk>
+          \<Longrightarrow> Says Spy B X  # evsf \<in> ns_public"
+
+
  | NS1:  "\<lbrakk>evs1 \<in> ns_public;  Nonce NA \<notin> used evs1\<rbrakk>
           \<Longrightarrow> Says A B (Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>)
                  # evs1  \<in>  ns_public"
 
-         (*Bob responds to Alice's message with a further nonce*)
+
  | NS2:  "\<lbrakk>evs2 \<in> ns_public;  Nonce NB \<notin> used evs2;
            Says A' B (Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>) \<in> set evs2\<rbrakk>
           \<Longrightarrow> Says B A (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>)
                 # evs2  \<in>  ns_public"
 
-         (*Alice proves her existence by sending NB back to Bob.*)
+
  | NS3:  "\<lbrakk>evs3 \<in> ns_public;
            Says A  B (Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>) \<in> set evs3;
            Says B' A (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>)
               \<in> set evs3\<rbrakk>
           \<Longrightarrow> Says A B (Crypt (pubK B) (Nonce NB)) # evs3 \<in> ns_public"
 
+text_raw {*
+\end{isabelle}
+\caption{An Inductive Protocol Definition}\label{fig:ns_public}
+\end{figure}
+*}
+
+text {*
+Let us formalize the Needham-Schroeder public-key protocol, as corrected by
+Lowe:
+\begin{alignat*%
+}{2}
+  &1.&\quad  A\to B  &: \comp{Na,A}\sb{Kb} \\
+  &2.&\quad  B\to A  &: \comp{Na,Nb,B}\sb{Ka} \\
+  &3.&\quad  A\to B  &: \comp{Nb}\sb{Kb}
+\end{alignat*%
+}
+
+Each protocol step is specified by a rule of an inductive definition.  An
+event trace has type @{text "event list"}, so we declare the constant
+@{text ns_public} to be a set of such traces.
+
+Figure~\ref{fig:ns_public} presents the inductive definition.  The
+@{text Nil} rule introduces the empty trace.  The @{text Fake} rule models the
+adversary's sending a message built from components taken from past
+traffic, expressed using the functions @{text synth} and
+@{text analz}. 
+The next three rules model how honest agents would perform the three
+protocol steps.  
+
+Here is a detailed explanation of rule @{text NS2}.
+A trace containing an event of the form
+@{term [display,indent=5] "Says A' B (Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>)"}
+may be extended by an event of the form
+@{term [display,indent=5] "Says B A (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>)"}
+where @{text NB} is a fresh nonce: @{term "Nonce NB \<in> used evs2"}.
+Writing the sender as @{text A'} indicates that @{text B} does not 
+know who sent the message.  Calling the trace variable @{text evs2} rather
+than simply @{text evs} helps us know where we are in a proof after many
+case-splits: every subgoal mentioning @{text evs2} involves message~2 of the
+protocol.
+
+Benefits of this approach are simplicity and clarity.  The semantic model
+is set theory, proofs are by induction and the translation from the informal
+notation to the inductive rules is straightforward. 
+*}
+
+section{* Proving Elementary Properties \label{sec:regularity} *}
+
+(*<*)
 declare knows_Spy_partsEs [elim]
 declare analz_subset_parts [THEN subsetD, dest]
 declare Fake_parts_insert [THEN subsetD, dest]
 declare image_eq_UN [simp]  (*accelerates proofs involving nested images*)
 

 
 (** Theorems of the form X \<notin> parts (knows Spy evs) imply that NOBODY
     sends messages containing X! **)
 
 (*Spy never sees another agent's private key! (unless it's bad at start)*)
+(*>*)
+
+text {*
+Secrecy properties can be hard to prove.  The conclusion of a typical
+secrecy theorem is 
+@{term "X \<notin> analz (knows Spy evs)"}.  The difficulty arises from
+having to reason about @{text analz}, or less formally, showing that the spy
+can never learn~@{text X}.  Much easier is to prove that @{text X} can never
+occur at all.  Such \emph{regularity} properties are typically expressed
+using @{text parts} rather than @{text analz}.
+
+The following lemma states that @{text A}'s private key is potentially
+known to the spy if and only if @{text A} belongs to the set @{text bad} of
+compromised agents.  The statement uses @{text parts}: the very presence of
+@{text A}'s private key in a message, whether protected by encryption or
+not, is enough to confirm that @{text A} is compromised.  The proof, like
+nearly all protocol proofs, is by induction over traces.
+*}
+
 lemma Spy_see_priK [simp]:
-      "evs \<in> ns_public \<Longrightarrow> (Key (priK A) \<in> parts (knows Spy evs)) = (A \<in> bad)"
-by (erule ns_public.induct, auto)
-
+      "evs \<in> ns_public
+       \<Longrightarrow> (Key (priK A) \<in> parts (knows Spy evs)) = (A \<in> bad)"
+apply (erule ns_public.induct, simp_all)
+txt {*
+The induction yields five subgoals, one for each rule in the definition of
+@{text ns_public}.  The idea is to prove that the protocol property holds initially
+(rule @{text Nil}), is preserved by each of the legitimate protocol steps (rules
+@{text NS1}--@{text 3}), and even is preserved in the face of anything the
+spy can do (rule @{text Fake}).  
+
+The proof is trivial.  No legitimate protocol rule sends any keys
+at all, so only @{text Fake} is relevant. Indeed, simplification leaves
+only the @{text Fake} case, as indicated by the variable name @{text evsf}:
+@{subgoals[display,indent=0,margin=65]}
+*}
+by blast
+(*<*)
 lemma Spy_analz_priK [simp]:
       "evs \<in> ns_public \<Longrightarrow> (Key (priK A) \<in> analz (knows Spy evs)) = (A \<in> bad)"
 by auto
-
-
-(*** Authenticity properties obtained from NS2 ***)
-
-
-(*It is impossible to re-use a nonce in both NS1 and NS2, provided the nonce
-  is secret.  (Honest users generate fresh nonces.)*)
+(*>*)
+
+text {*
+The @{text Fake} case is proved automatically.  If
+@{term "priK A"} is in the extended trace then either (1) it was already in the
+original trace or (2) it was
+generated by the spy, who must have known this key already. 
+Either way, the induction hypothesis applies.
+
+\emph{Unicity} lemmas are regularity lemmas stating that specified items
+can occur only once in a trace.  The following lemma states that a nonce
+cannot be used both as $Na$ and as $Nb$ unless
+it is known to the spy.  Intuitively, it holds because honest agents
+always choose fresh values as nonces; only the spy might reuse a value,
+and he doesn't know this particular value.  The proof script is short:
+induction, simplification, @{text blast}.  The first line uses the rule
+@{text rev_mp} to prepare the induction by moving two assumptions into the 
+induction formula.
+*}
+
 lemma no_nonce_NS1_NS2:
-      "\<lbrakk>Crypt (pubK C) \<lbrace>NA', Nonce NA, Agent D\<rbrace> \<in> parts (knows Spy evs);
-        Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace> \<in> parts (knows Spy evs);
-        evs \<in> ns_public\<rbrakk>
-       \<Longrightarrow> Nonce NA \<in> analz (knows Spy evs)"
+    "\<lbrakk>Crypt (pubK C) \<lbrace>NA', Nonce NA, Agent D\<rbrace> \<in> parts (knows Spy evs);
+      Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace> \<in> parts (knows Spy evs);
+      evs \<in> ns_public\<rbrakk>
+     \<Longrightarrow> Nonce NA \<in> analz (knows Spy evs)"
 apply (erule rev_mp, erule rev_mp)
 apply (erule ns_public.induct, simp_all)
 apply (blast intro: analz_insertI)+
 done
 
-(*Unicity for NS1: nonce NA identifies agents A and B*)
+text {*
+The following unicity lemma states that, if \isa{NA} is secret, then its
+appearance in any instance of message~1 determines the other components. 
+The proof is similar to the previous one.
+*}
+
 lemma unique_NA:
      "\<lbrakk>Crypt(pubK B)  \<lbrace>Nonce NA, Agent A \<rbrace> \<in> parts(knows Spy evs);
        Crypt(pubK B') \<lbrace>Nonce NA, Agent A'\<rbrace> \<in> parts(knows Spy evs);
        Nonce NA \<notin> analz (knows Spy evs); evs \<in> ns_public\<rbrakk>
       \<Longrightarrow> A=A' \<and> B=B'"
+(*<*)
 apply (erule rev_mp, erule rev_mp, erule rev_mp)
 apply (erule ns_public.induct, simp_all)
 (*Fake, NS1*)
 apply (blast intro: analz_insertI)+
 done
-
-
+(*>*)
+
+section{* Proving Secrecy Theorems \label{sec:secrecy} *}
+
+(*<*)
 (*Secrecy: Spy does not see the nonce sent in msg NS1 if A and B are secure
   The major premise "Says A B ..." makes it a dest-rule, so we use
   (erule rev_mp) rather than rule_format. *)
 theorem Spy_not_see_NA:
       "\<lbrakk>Says A B (Crypt(pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>) \<in> set evs;

 apply (erule rev_mp, erule rev_mp, erule rev_mp)
 apply (erule ns_public.induct, simp_all)
 (*Fake, NS2*)
 apply (blast intro: analz_insertI)+
 done
-
-
-
-text{*
-@{thm[display] analz_Crypt_if[no_vars]}
-\rulename{analz_Crypt_if}
-*}
-
-(*Secrecy: Spy does not see the nonce sent in msg NS2 if A and B are secure*)
+(*>*)
+
+text {*
+The secrecy theorems for Bob (the second participant) are especially
+important because they fail for the original protocol.  The following
+theorem states that if Bob sends message~2 to Alice, and both agents are
+uncompromised, then Bob's nonce will never reach the spy.
+*}
+
 theorem Spy_not_see_NB [dest]:
-     "\<lbrakk>Says B A (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>) \<in> set evs;
-       A \<notin> bad;  B \<notin> bad;  evs \<in> ns_public\<rbrakk>
-      \<Longrightarrow> Nonce NB \<notin> analz (knows Spy evs)"
-apply (erule rev_mp)
-apply (erule ns_public.induct, simp_all)
+ "\<lbrakk>Says B A (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>) \<in> set evs;
+   A \<notin> bad;  B \<notin> bad;  evs \<in> ns_public\<rbrakk>
+  \<Longrightarrow> Nonce NB \<notin> analz (knows Spy evs)"
+txt {*
+To prove it, we must formulate the induction properly (one of the
+assumptions mentions~@{text evs}), apply induction, and simplify:
+*}
+
+apply (erule rev_mp, erule ns_public.induct, simp_all)
+(*<*)
 apply spy_analz
-apply (blast intro: no_nonce_NS1_NS2)+
-done
-
-
-(*Authentication for B: if he receives message 3 and has used NB
-  in message 2, then A has sent message 3.*)
+defer
+apply (blast intro: no_nonce_NS1_NS2)
+apply (blast intro: no_nonce_NS1_NS2)
+(*>*)
+
+txt {*
+The proof states are too complicated to present in full.  
+Let's examine the simplest subgoal, that for message~1.  The following
+event has just occurred:
+\[ 1.\quad  A'\to B'  : \comp{Na',A'}\sb{Kb'} \]
+The variables above have been primed because this step
+belongs to a different run from that referred to in the theorem
+statement --- the theorem
+refers to a past instance of message~2, while this subgoal
+concerns message~1 being sent just now.
+In the Isabelle subgoal, instead of primed variables like $B'$ and $Na'$
+we have @{text Ba} and~@{text NAa}:
+@{subgoals[display,indent=0]}
+The simplifier has used a 
+default simplification rule that does a case
+analysis for each encrypted message on whether or not the decryption key
+is compromised.
+@{named_thms [display,indent=0,margin=50] analz_Crypt_if [no_vars] (analz_Crypt_if)}
+The simplifier has also used @{text Spy_see_priK}, proved in
+{\S}\ref{sec:regularity}) above, to yield @{term "Ba \<in> bad"}.
+
+Recall that this subgoal concerns the case
+where the last message to be sent was
+\[ 1.\quad  A'\to B'  : \comp{Na',A'}\sb{Kb'}. \]
+This message can compromise $Nb$ only if $Nb=Na'$ and $B'$ is compromised,
+allowing the spy to decrypt the message.  The Isabelle subgoal says
+precisely this, if we allow for its choice of variable names.
+Proving @{term "NB \<noteq> NAa"} is easy: @{text NB} was
+sent earlier, while @{text NAa} is fresh; formally, we have
+the assumption @{term "Nonce NAa \<notin> used evs1"}. 
+
+Note that our reasoning concerned @{text B}'s participation in another
+run.  Agents may engage in several runs concurrently, and some attacks work
+by interleaving the messages of two runs.  With model checking, this
+possibility can cause a state-space explosion, and for us it
+certainly complicates proofs.  The biggest subgoal concerns message~2.  It
+splits into several cases, such as whether or not the message just sent is
+the very message mentioned in the theorem statement.
+Some of the cases are proved by unicity, others by
+the induction hypothesis.  For all those complications, the proofs are
+automatic by @{text blast} with the theorem @{text no_nonce_NS1_NS2}.
+
+The remaining theorems about the protocol are not hard to prove.  The
+following one asserts a form of \emph{authenticity}: if
+@{text B} has sent an instance of message~2 to~@{text A} and has received the
+expected reply, then that reply really originated with~@{text A}.  The
+proof is a simple induction.
+*}
+
+(*<*)
+by (blast intro: no_nonce_NS1_NS2)
+
 lemma B_trusts_NS3_lemma [rule_format]:
      "\<lbrakk>A \<notin> bad;  B \<notin> bad;  evs \<in> ns_public\<rbrakk> \<Longrightarrow>
       Crypt (pubK B) (Nonce NB) \<in> parts (knows Spy evs) \<longrightarrow>
       Says B A (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>) \<in> set evs \<longrightarrow>
       Says A B (Crypt (pubK B) (Nonce NB)) \<in> set evs"
 by (erule ns_public.induct, auto)
-
+(*>*)
 theorem B_trusts_NS3:
-     "\<lbrakk>Says B A  (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>) \<in> set evs;
-       Says A' B (Crypt (pubK B) (Nonce NB)) \<in> set evs;
-       A \<notin> bad;  B \<notin> bad;  evs \<in> ns_public\<rbrakk>
-      \<Longrightarrow> Says A B (Crypt (pubK B) (Nonce NB)) \<in> set evs"
+ "\<lbrakk>Says B A  (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>) \<in> set evs;
+   Says A' B (Crypt (pubK B) (Nonce NB)) \<in> set evs;
+   A \<notin> bad;  B \<notin> bad;  evs \<in> ns_public\<rbrakk>
+  \<Longrightarrow> Says A B (Crypt (pubK B) (Nonce NB)) \<in> set evs"
+(*<*)
 by (blast intro: B_trusts_NS3_lemma)
 
 (*** Overall guarantee for B ***)
 
 
 (*If NS3 has been sent and the nonce NB agrees with the nonce B joined with
   NA, then A initiated the run using NA.*)
-theorem B_trusts_protocol:
+theorem B_trusts_protocol [rule_format]:
      "\<lbrakk>A \<notin> bad;  B \<notin> bad;  evs \<in> ns_public\<rbrakk> \<Longrightarrow>
       Crypt (pubK B) (Nonce NB) \<in> parts (knows Spy evs) \<longrightarrow>
       Says B A  (Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>) \<in> set evs \<longrightarrow>
       Says A B (Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>) \<in> set evs"
 by (erule ns_public.induct, auto)
-
-end
+(*>*)
+
+text {*
+From similar assumptions, we can prove that @{text A} started the protocol
+run by sending an instance of message~1 involving the nonce~@{text NA}\@. 
+For this theorem, the conclusion is 
+@{thm_style [display] concl B_trusts_protocol [no_vars]}
+Analogous theorems can be proved for~@{text A}, stating that nonce~@{text NA}
+remains secret and that message~2 really originates with~@{text B}.  Even the
+flawed protocol establishes these properties for~@{text A};
+the flaw only harms the second participant.
+
+\medskip
+
+Detailed information on this protocol verification technique can be found
+elsewhere~\cite{paulson-jcs}, including proofs of an Internet
+protocol~\cite{paulson-tls}.  We must stress that the protocol discussed
+in this chapter is trivial.  There are only three messages; no keys are
+exchanged; we merely have to prove that encrypted data remains secret. 
+Real world protocols are much longer and distribute many secrets to their
+participants.  To be realistic, the model has to include the possibility
+of keys being lost dynamically due to carelessness.  If those keys have
+been used to encrypt other sensitive information, there may be cascading
+losses.  We may still be able to establish a bound on the losses and to
+prove that other protocol runs function
+correctly~\cite{paulson-yahalom}.  Proofs of real-world protocols follow
+the strategy illustrated above, but the subgoals can
+be much bigger and there are more of them.
+\index{protocols!security|)}
+*}
+
+(*<*)end(*>*)