--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/Doc/Tutorial/Protocol/NS_Public.thy Tue Aug 28 18:57:32 2012 +0200
@@ -0,0 +1,402 @@
+(* Title: HOL/Auth/NS_Public
+ 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(*>*)
+
+section{* Modelling the Protocol \label{sec:modelling} *}
+
+text_raw {*
+\begin{figure}
+\begin{isabelle}
+*}
+
+inductive_set ns_public :: "event list set"
+ where
+
+ Nil: "[] \<in> ns_public"
+
+
+ | 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"
+
+
+ | 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"
+
+
+ | 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 \<notin> 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*)
+
+(*A "possibility property": there are traces that reach the end*)
+lemma "\<exists>NB. \<exists>evs \<in> ns_public. Says A B (Crypt (pubK B) (Nonce NB)) \<in> set evs"
+apply (intro exI bexI)
+apply (rule_tac [2] ns_public.Nil [THEN ns_public.NS1, THEN ns_public.NS2,
+ THEN ns_public.NS3])
+by possibility
+
+
+(**** Inductive proofs about ns_public ****)
+
+(** 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)"
+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
+(*>*)
+
+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)"
+apply (erule rev_mp, erule rev_mp)
+apply (erule ns_public.induct, simp_all)
+apply (blast intro: analz_insertI)+
+done
+
+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;
+ A \<notin> bad; B \<notin> bad; evs \<in> ns_public\<rbrakk>
+ \<Longrightarrow> Nonce NA \<notin> analz (knows Spy evs)"
+apply (erule rev_mp)
+apply (erule ns_public.induct, simp_all)
+apply spy_analz
+apply (blast dest: unique_NA intro: no_nonce_NS1_NS2)+
+done
+
+
+(*Authentication for A: if she receives message 2 and has used NA
+ to start a run, then B has sent message 2.*)
+lemma A_trusts_NS2_lemma [rule_format]:
+ "\<lbrakk>A \<notin> bad; B \<notin> bad; evs \<in> ns_public\<rbrakk>
+ \<Longrightarrow> Crypt (pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace> \<in> parts (knows Spy evs) \<longrightarrow>
+ Says A B (Crypt(pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>) \<in> set evs \<longrightarrow>
+ Says B A (Crypt(pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>) \<in> set evs"
+apply (erule ns_public.induct, simp_all)
+(*Fake, NS1*)
+apply (blast dest: Spy_not_see_NA)+
+done
+
+theorem A_trusts_NS2:
+ "\<lbrakk>Says A B (Crypt(pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>) \<in> set evs;
+ 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> Says B A (Crypt(pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace>) \<in> set evs"
+by (blast intro: A_trusts_NS2_lemma)
+
+
+(*If the encrypted message appears then it originated with Alice in NS1*)
+lemma B_trusts_NS1 [rule_format]:
+ "evs \<in> ns_public
+ \<Longrightarrow> Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace> \<in> parts (knows Spy evs) \<longrightarrow>
+ Nonce NA \<notin> analz (knows Spy evs) \<longrightarrow>
+ Says A B (Crypt (pubK B) \<lbrace>Nonce NA, Agent A\<rbrace>) \<in> set evs"
+apply (erule ns_public.induct, simp_all)
+(*Fake*)
+apply (blast intro!: analz_insertI)
+done
+
+
+
+(*** Authenticity properties obtained from NS2 ***)
+
+(*Unicity for NS2: nonce NB identifies nonce NA and agents A, B
+ [unicity of B makes Lowe's fix work]
+ [proof closely follows that for unique_NA] *)
+
+lemma unique_NB [dest]:
+ "\<lbrakk>Crypt(pubK A) \<lbrace>Nonce NA, Nonce NB, Agent B\<rbrace> \<in> parts(knows Spy evs);
+ Crypt(pubK A') \<lbrace>Nonce NA', Nonce NB, Agent B'\<rbrace> \<in> parts(knows Spy evs);
+ Nonce NB \<notin> analz (knows Spy evs); evs \<in> ns_public\<rbrakk>
+ \<Longrightarrow> A=A' \<and> NA=NA' \<and> B=B'"
+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 {*
+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)"
+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
+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"
+(*<*)
+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 [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)
+(*>*)
+
+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 [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(*>*)