--- a/doc-src/TutorialI/Protocol/NS_Public.thy Mon Jul 23 14:30:53 2007 +0200
+++ b/doc-src/TutorialI/Protocol/NS_Public.thy Mon Jul 23 14:31:34 2007 +0200
@@ -5,40 +5,92 @@
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(*>*)
-theory NS_Public imports Public begin
+section{* Modelling the Protocol \label{sec:modelling} *}
-inductive_set
- ns_public :: "event list set"
+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]
@@ -58,43 +110,98 @@
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 ***)
-
+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.
-(*It is impossible to re-use a nonce in both NS1 and NS2, provided the nonce
- is secret. (Honest users generate fresh nonces.)*)
+\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. *)
@@ -158,40 +265,97 @@
(*Fake, NS2*)
apply (blast intro: analz_insertI)+
done
-
-
+(*>*)
-text{*
-@{thm[display] analz_Crypt_if[no_vars]}
-\rulename{analz_Crypt_if}
+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:
*}
-(*Secrecy: Spy does not see the nonce sent in msg NS2 if A and B are secure*)
-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)
+apply (erule rev_mp, erule ns_public.induct, simp_all)
+(*<*)
apply spy_analz
-apply (blast intro: no_nonce_NS1_NS2)+
-done
+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"}.
-(*Authentication for B: if he receives message 3 and has used NB
- in message 2, then A has sent message 3.*)
+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 ***)
@@ -199,11 +363,41 @@
(*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(*>*)