X-Git-Url: https://git.distorted.org.uk/~mdw/tripe/blobdiff_plain/874aed515f3a8a54f32cb076267640d7d522945d..96e12a8165129bfe385e6ec233317ada460a271d:/doc/wrestlers.tex

diff --git a/doc/wrestlers.tex b/doc/wrestlers.tex
index 600b2fda..c175b1a9 100644
--- a/doc/wrestlers.tex
+++ b/doc/wrestlers.tex
@@ -1,6 +1,6 @@
 %%% -*-latex-*-
 %%%
-%%% $Id: wrestlers.tex,v 1.2 2001/02/22 09:09:05 mdw Exp $
+%%% $Id: wrestlers.tex,v 1.5 2002/01/13 14:55:31 mdw Exp $
 %%%
 %%% Description of the Wrestlers Protocol
 %%%
@@ -10,6 +10,15 @@
 %%%----- Revision history ---------------------------------------------------
 %%%
 %%% $Log: wrestlers.tex,v $
+%%% Revision 1.5  2002/01/13 14:55:31  mdw
+%%% More incomplete stuff.
+%%%
+%%% Revision 1.4  2001/06/29 19:36:05  mdw
+%%% Some progress made on laptop.
+%%%
+%%% Revision 1.3  2001/06/22 19:41:31  mdw
+%%% Restart with different structure and rather more formal objectives.
+%%%
 %%% Revision 1.2  2001/02/22 09:09:05  mdw
 %%% Partially through reworking.
 %%%
@@ -17,242 +26,392 @@
 %%% Initial versions of documentation.
 %%%
 
-\documentclass{article}
-\usepackage{amssymb}
-\title{The Wrestlers Protocol}
-\author{Mark Wooding \\ Clive Jones}
-\def\from{\leftarrow}
+\newif\iffancystyle\fancystylefalse
+
+\iffancystyle
+  \documentclass
+    [a4paper, article, 10pt, numbering, noherefloats, notitlepage]
+    {strayman}
+  \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
+  \usepackage[margin]{amsthm}
+\else
+  \documentclass[a4paper]{article}
+  \usepackage{a4wide}
+  \usepackage{amsthm}
+\fi
+
+\usepackage{amssymb, amstext}
+\usepackage{mdwtab, mathenv}
+
+\errorcontextlines=999
+\showboxbreadth=999
+\showboxdepth=999
+\makeatletter
+
+\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
+\author{Mark Wooding \and Clive Jones}
+
+\bibliographystyle{alpha}
+
+\newtheorem{theorem}{Theorem}
+\renewcommand{\qedsymbol}{$\square$}
+
+\newcommand{\getsr}{\stackrel{\scriptscriptstyle R}{\gets}}
+\newcommand{\inr}{\in_{\scriptscriptstyle R}}
+\newcommand{\oracle}[1]{\mathcal{#1}}
+
+\newcommand{\expt}[2]{\mathbf{Exp}^{\text{\normalfont#1}}_{#2}}
+\newcommand{\adv}[2]{\mathbf{Adv}^{\text{\normalfont#1}}_{#2}}
+\newcommand{\ord}{\mathop{\operator@font ord}}
+\newcommand{\poly}[1]{\mathop{\operator@font poly}({#1})}
+\newcommand{\negl}[1]{\mathop{\operator@font negl}({#1})}
+\newcommand{\compind}{\stackrel{c}{\approx}}
+
+\newcolumntype{G}{p{0pt}}
+
+\newcommand{\xor}{\oplus}
+\renewcommand{\epsilon}{\varepsilon}
+
+\newenvironment{program}
+  {\begin{tabular}[C]{|G|}\hlx{hv[][\tabcolsep]}\begin{tabbing}}
+  {\end{tabbing}\\\hlx{v[][\tabcolsep]h}\end{tabular}}
 
 \begin{document}
 
 \maketitle
-
 \begin{abstract}
-  We present a simple key-exchange protocol with of mutual authentication and
-  perfect forward-secrecy, which doesn't leave any long-lasting evidence of
-  participation in the exchange.  The protocol's security depends on the
-  intractability of the Diffie-Hellman problem (in some cyclic group), and on
-  the strength of a hash function.
+  Fill this in later.
 \end{abstract}
+\tableofcontents
+\newpage
 
-\section{Introduction}
+%%%--------------------------------------------------------------------------
 
-Current key-agreement protocols are all very well for securing generally
-`honest' traffic (e.g., transmission of credit-card details to a merchant),
-but they're less satisfactory if you actually have something to hide.
-
-In the UK, new key exchange protocols have been particularly motivated by the
-new Regulation of Investigatory Powers Act, which allows `authorized persons'
-to intercept communications and demand long-term encryption keys.
-
-Let's suppose that Alice and Bob are shady characters, and that their
-communications are of great interest to the draconian r\'egime in which they
-live.  (They might be international arms smugglers, for example, because they
-export cryptographic toolkits.)
-
-Alice could just invent a session key and transmit it to Bob, encrypted under
-his public key, each time she wanted to talk to him.  However, once the
-secret police turn up at Bob's house and demand his private key, the game is
-over and all of the communications can be recovered.
-
-Alice and Bob would clearly be better off using a system which offers forward
-secrecy, for example, Diffie-Hellman.  However, in order to prevent active
-attacks, the messages in the Diffie-Hellman exchange must be authenticated.
-The way this usually works is that Alice and Bob pick a group $G$ of order
-$q$ generated by $g$.  When Alice and Bob want to communicate, they choose
-exponents $\alpha$ and $\beta$ respectively ($1 < \alpha, \beta < q$), Alice
-sends $S_A(g^\alpha)$ to Bob, Bob sends $S_B(g^\beta)$ to Alice, and, after
-verifying each other's signatures, they each compute a shared key $K =
-g^{\alpha \beta}$.  They dispose of their secrets $\alpha$ and $\beta$
-forthwith, and destroy $K$ when the conversation finishes.  Now the secret
-police can demand all they like: they still can't decrypt old sessions, and
-Alice and Bob, however badly tortured, can't help them.  The secret police
-might not even be all owed to demand their long-term signing keys: for
-example, the RIPA grants special protection to authentication-only keys.
-
-This is fine, except that sending $S_A(g^\alpha)$ is a wonderful way of
-shouting `Alice was here' to all of the spooks tapping Bob's network
-connection.  The Wrestlers Protocol\footnote{%
-  Named after the excellent pub in Cambridge where most of the design was
-  done.}
-fixes these problems.  It provides perfect forward secrecy, just like
-Diffie-Hellman, without leaving signatures around for the spooks.
+\section{Introduction}
+% Some waffle here about the desirability of a key-exchange protocol that
+% doesn't leave signatures lying around, followed by an extended report of
+% the various results.
 
+%%%--------------------------------------------------------------------------
 
 \section{A simple authentication protocol}
+% Present the basic Diffie-Hellman-based authenticator, and prove that an
+% authentication oracle is useless if the hash function has appropriate
+% properties.
+
+We begin by introducing a simple proof-of-identity protocol, based on the
+Diffie-Hellman key-exchange protocol \cite{Diffie:1976:NDC} and prove some of
+its useful properties.
+
+\subsection{Introduction}
 
-As a building-block, we construct a simple authentication protocol based on
-Diffie-Hellman key exchange.  As before, let's use a group $G$ of order $q$
-(for some prime $q$), generated by a group element $g$.
+We start by selecting a security parameter $k$.  We choose a cyclic group $G
+= \langle g \rangle$ with $q = |G|$ prime, in which the decision
+Diffie-Hellman problem is assumed to be hard \cite{Boneh:1998:DDP}; we
+require that $q$ is a $k$-bit number.  Suitable groups include elliptic
+curves over finite fields and prime-order subgroups of prime fields.
+Throughout, we shall write the group operation as multiplication, and we
+shall assume that group elements are interchangeable with their binary
+representations.
 
-A Diffie-Hellman key exchange allows two parties to compute the same value,
-with different knowledge.  We'll use this to make an authentication protocol.
+Alice can choose a private key $\alpha$ from the set $\{ 1, 2, \ldots, q - 1
+\}$ and publish her corresponding public key $a = g^\alpha$.
 
-Alice chooses a private key $1 < a < q$.  Her public key is $A = g^a$.  She
-can prove her knowledge of $a$ to Bob like this:
+A simplistic proof-of-identity protocol might then proceed as follows:
 \begin{enumerate}
-\item Bob makes up a random $1 < \beta < q$.  He sends a challenge $C =
-  g^\beta$ to Alice.
-\item Alice computes the response $R = C^a = g^{a \beta}$.  This would
-  be the shared key if we were doing proper Diffie-Hellman, but we aren't.
-  Instead, she just sends $R$ back to Bob.
-\item Bob checks that $R = A^\beta$.  If it is, he accepts that the person
-  he's talking to has Alice's private key, and hence is presumably Alice.
+\item Bob chooses a random exponent $\beta$, also from $\{ 1, 2, \ldots, q -
+  1 \}$, and sends a \emph{challenge} $b = g^\beta$ to Alice.
+\item Alice computes her \emph{response} $b^\alpha$ and returns it to Bob.
+\item If Alice's response is equal to $a^\beta$ then Bob is satisfied.
 \end{enumerate}
-
-This protocol has nice properties.  It's not terribly difficult to implement,
-given the usual tools like modular exponentiation or elliptic curve
-point-addition.
-
-An eavesdropper -- let's call her Eve, for tradition's sake -- doesn't learn
-anything terribly interesting from watching the exchange.  She sees $C$ going
-one way and then $C^a$ coming back.  If she finds this illuminating, she can
-program her computer to generate random numbers $\gamma$ and show her pairs
-$C = g^\gamma$ and $R = A^\gamma = C^a$.  So Eve learns nothing useful she
-couldn't have worked out for herself.  In fact, she doesn't even learn that
-Alice is involved in the conversation!  Bob can fake up an authentication
-with Alice by secretly agreeing which value of $\beta$ he's going to use with
-an accomplice.
-
-Bob's in a better position than Eve.  If he computes his challenges honestly
-then he doesn't learn much except that he's talking to Alice, because as
-we've seen, she only tells him $R$, which he knew already.  However, if Bob
-carefully chooses a challenge $C$ without knowing its discrete log $\beta$,
-then Alice's response might tell him useful information about her private
-key that he couldn't have worked out just by sitting at home computing
-discrete logs.
-
-We can fix this little problem easily enough if we make Bob transmit a hash
-of his expected answer.  Let $H \colon \mathbb{Z} \to \{\,0, 1\,\}^n$ be a
-hash function.  The property we require from $H$ is that Bob can't compute
-$H(g^{a \beta})$ given only $C = g^\beta$ and $A = g^a$ with more than
-negligible probability; a random function would fit the bill fine.  This
-does, of course, also assume that the Diffie-Hellman problem is difficult.
-The new protocol looks very much like the old one:
+If Bob always plays by the rules then this protocol is evidently secure,
+since computing $g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely
+the Diffie-Hellman problem.
+
+This protocol has a flaw, though: by using Alice as an oracle for the
+function $x \mapsto x^\alpha$, he could conceivably acquire information about
+Alice's private key which he could later use to impersonate her.  As an
+example, Bob can submit $-g^\beta$ as a challenge: if the reply
+$(-g^\beta)^\alpha = g^{\alpha\beta}$, Bob can conclude that $\alpha$ is
+even.
+
+We fix the protocol by requiring that Bob prove that he already knows the
+answer to his challenge.  We introduce a hash function $h$ whose properties
+we shall investigate later.  The \emph{Wrestlers Authentication Protocol} is
+then:
 \begin{enumerate}
-\item Bob chooses a random $1 < \beta < q$.  He computes $C = g^\beta$ and $R
-  = A^\beta$, and sends $C, H(R)$ to Alice.
-\item Alice computes $R' = C^a$ and checks that it matches the hash which Bob
-  sent.  If it doesn't, he's trying to cheat, and she should refuse to
-  answer.  Otherwise, she sends her response $R'$ back to Bob.
-\item Bob checks that Alice's reply matches the one he computed back in step
-  1.  If it does, he knows that he's talking to Alice.
+\item Bob chooses a secret $\beta \getsr \{ 1, 2, \ldots, q - 1 \}$.  He
+  computes his \emph{challenge} $b \gets g^\beta$ and also a \emph{check
+    value} $c \gets \beta \xor h(a^\beta)$.  He sends the pair $(b, c)$.
+\item Alice receives $(b', c')$.  She computes $r \gets b'^\alpha$ and
+  $\gamma \gets c' \xor h(R)$.  If $b' = g^\gamma$, she sends $r$ back as her
+  \emph{response}; otherwise she sends the distinguished value $\bot$.
+\item Bob receives $r'$.  If $r' = a^\beta$ then he accepts that he's talking
+  to Alice.
 \end{enumerate}
+We show that the introduction of the check value has indeed patched up the
+weakness described above, and that the check value itself hasn't made an
+impersonator's job much easier.
+
+\subsection{Analysis in the random oracle model}
+
+Here, we prove that the Wrestlers Authentication Protocol is secure if $h$ is
+implemented by a public \emph{random oracle} \cite{Bellare:1993:ROP}.
+
+Fix a private key $\alpha \inr \{ 1, 2, \ldots, q - 1\}$ and the corresponding public
+key $a = g^\alpha$, and consider a probabilistic polynomial-time adversary
+$A$, equipped with two oracles.  One is a random oracle $\oracle{H}\colon
+\{0, 1\}^* \to \{0, 1\}^k$, which implements a function $h$ randomly selected
+from the set of all functions with that signature; the other is an
+authentication oracle $\oracle{O}\colon G \times \{0, 1\}^k \to G \cup \{
+\bot \}$ defined by:
+\[
+\oracle{O}^(b, c) = \begin{cases}
+  b^\alpha & if $b = g^{c \xor h(b^\alpha)}$ \\
+  \bot     & otherwise
+\end{cases}
+\]
+The authentication oracle will play the part of Alice in the following.  We
+first show that access to this authentication oracle can't help an adversary
+learn how to impersonate Alice.
+
+\begin{theorem}
+  The Wrestlers Authentication Protocol with random oracle is computational
+  zero knowledge \cite{Brassard:1989:SZK}.
+  \label{thm:wap-czk}
+\end{theorem}
+\begin{proof}
+  \newcommand{\Hlist}{\textit{$\oracle{H}$-list}}
+  \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}}
+  \newcommand{\Osim}{\textit{$\oracle{O}$-sim}}
+  \renewcommand{\H}{\oracle{H}}
+  \renewcommand{\O}{\oracle{O}}
+  %
+  Let $A$ be any probabilistic polynomial-time adversary with access to a
+  random.  We shall construct a probabilistic polynomial-time adversary $A'$
+  without either oracle such that the probability distributions on the output
+  of $A$ and $A'$ are equal.  Specifically, $A'$ runs $A$ with simulated
+  random and authentication oracles whose behaviour is computationally
+  indistinguishable from the originals.  The algorithm for $A'$ and the
+  simulated oracles is shown in figure~\ref{fig:wap-czk-sim}.
+
+  \begin{figure}
+    \begin{program}
+      \quad \= \kill
+      Adversary $A'^{\H(\cdot)}$: \+ \\
+        $\Hlist \gets \emptyset$; \\
+        $r \gets A^{\Hsim(\cdot), \Osim(\cdot, \cdot)}$; \\
+        \textbf{return} $r$; \- \\[\medskipamount]
+      %
+      Simulated random oracle $\Hsim(q)$: \+ \\
+        \textbf{if} $\exists r : (q, r) \in \Hlist$ \textbf{then}
+          \textbf{return} $r$; \\
+        $r \getsr \H(q)$; \\
+        $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
+        \textbf{return} $r$; \- \\[\medskipamount]
+      %
+      Simulated authentication oracle $\Osim(b, c)$: \+ \\
+        \textbf{if} $\exists q, r : (q, r) \in \Hlist \wedge
+                                    b = g^{c \xor r} \wedge
+                                    q = a^{c \xor r}$ \textbf{then}
+          \textbf{return} $a^{c \xor r}$; \\
+        \textbf{else} \textbf{return} $\bot$;
+    \end{program}
+    %
+    \caption{The algorithm and simulated oracles for the proof of
+        theorem~\ref{thm:wap-czk}.}
+    \label{fig:wap-czk-sim}
+  \end{figure}
+  
+  Firstly we show that $A'$ runs in polynomial time.  The only modifications
+  to $\Hlist$ are in $\Hsim$, which adds at most one element for each oracle
+  query.  Since $\Hlist$ is initially empty and $A$ can only make $\poly{k}$
+  queries to $\Hsim$, this implies that $|\Hlist|$ is always
+  polynomially-bounded.  Each query can be answered in polynomial time:
+  indeed, the search implied by the test $\exists r : (q, r) \in \Hlist$ can
+  be performed in $O(\log q)$ time by indexing $\Hlist$ on $q$ using a radix
+  tree.  Now, since $|\Hlist|$ is polynomially bounded, the test $\exists q,
+  r : (q, r) \in \Hlist \wedge b = g^{c \xor r} \wedge q = a^{c \xor r}$ at
+  the start of $\Osim$ runs in polynomial time even though it requires an
+  exhaustive search of the history of $A$'s queries to its simulated random
+  oracle.
+  
+  Next, we examine the behaviour of the simulated oracles.  Since $\Hsim$ is
+  implemented in terms of the public random oracle $\H$, and returns the same
+  answers to queries, its probability distribution must be identical.
+  
+  We turn our attention to the simulation of the authentication oracle.
+  Consider a query $(b, c)$ made by $A$ to its authentication oracle.
+  
+  Firstly, suppose that there is a $\beta$ such that $b = g^\beta$ and $c =
+  \beta \xor r$ where $r$ is the response to a previous query made by $A$ to
+  its random oracle on $a^\beta$.  Then the true authentication oracle $\O$
+  is satisfied because $b = g^\beta = g^{c \xor r} = g^{c \xor h(a^\beta)} =
+  g^{c \xor h(b^\alpha)}$, and returns $b^\alpha$.  Similarly, the simulated
+  authentication oracle $\Osim$ will find the pair $(a^\beta, r) \in \Hlist$,
+  recover $\beta = c \xor r$, confirm that $b = g^\beta$, and return
+  $a^\beta$ as required.  These events all occur with probability 1.
+
+  Conversely, suppose that there is no such $\beta$.  Then the simulated
+  oracle $\Osim$ will reject the query, returning $\bot$, again with
+  probability 1.  However, a genuine authentication oracle $\O$ will succeed
+  and return $b^\alpha$ with probability $2^{-k}$.  To see this, note that $b
+  = g^\gamma$ for some $\gamma \in \{ 0, 1, \ldots, q - 1 \}$, and the
+  probability that $h(b^\alpha) = c \xor \gamma$ is precisely $2^{-k}$, since
+  $c$ and $\gamma$ are $k$-bit strings.  Since this probability is
+  negligible, we have shown that the distributions of the simulated oracles
+  $\Hsim$ and $\Osim$ are computationally indistinguishable from the genuine
+  oracles $\H$ and $\O$.  The theorem follows.
+\end{proof}
+
+Our next objective is to show that pretending to be Alice is hard without
+knowledge of her secret $\alpha$.  We say that an adversary $A$
+\emph{impersonates} in the Wrestlers Authentication Protocol with probability
+$\epsilon$ if
+\[ \Pr[A^{\oracle{H}(\cdot)}(g^\alpha, g^\beta,
+                             \beta \xor h(g^{\alpha\beta}))
+         = g^{\alpha\beta}]
+     = \epsilon
+\]
+where the probability is taken over all choices of $\alpha, \beta \in \{ 1,
+2, \ldots, q - 1 \}$ and random oracles $\oracle{H}$.
+
+\begin{theorem}
+  Assuming that the Diffie-Hellman problem is hard in $G$, no probabilistic
+  polynomial-time adversary can impersonate in the Wrestlers Authentication
+  Protocol with random oracle with better than negligible probability.
+  \label{thm:wap-dhp}
+\end{theorem}
+\begin{proof}
+  \newcommand{\Hlist}{\textit{$\oracle{H}$-list}}
+  \newcommand{\Hqueries}{\textit{$\oracle{H}$-queries}}
+  \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}}
+  \renewcommand{\H}{\oracle{H}}
+  %
+  We prove the theorem by contradiction.  Given a polynomial-time adversary
+  $A$ which impersonates Alice with non-negligible probability $\epsilon$, we
+  construct an adversary which solves the Diffie-Hellman problem with
+  probability no less than $\epsilon \poly{k}$, i.e.,
+  \[ \Pr[A'(g^\alpha, g^\beta) = g^{\alpha\beta}] \ge \epsilon \poly{k}. \]
+  Thus, if there is any polynomial-time $A$ which impersonates with better
+  than negligible probability, then there is a polynomial-time $A'$ which
+  solves Diffie-Hellman with essentially the same probability, which would
+  violate our assumption of the hardness of Diffie-Hellman.
+
+  The idea behind the proof is that the check value is only useful to $A$
+  once it has discovered the correct response to the challenge, which it must
+  have done by solving the Diffie-Hellman problem.  Hence, our Diffie-Hellman
+
+  \begin{figure}
+    \begin{program}
+      \quad \= \kill
+      Adversary $A'(a, b)$: \+ \\
+        $\Hlist \gets \emptyset$; \\
+        $\Hqueries \gets \emptyset$; \\
+        $r \getsr \{ 0, 1 \}^k$; \\
+        $x \gets A^{\Hsim(\cdot)}(a, b, r)$; \\
+        $c \getsr (\Hlist \cup \{ x \}) \cap G$; \\
+        \textbf{return} $c$; \- \\[\medskipamount]
+      %
+      Simulated random oracle $\Hsim(q)$: \+ \\
+        \textbf{if} $\exists r : (q, r) \in \Hlist$
+          \textbf{then} \textbf{return} $r$; \\
+        $r \gets \{ 0, 1 \}^k$; \\
+        $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
+        $\Hqueries \gets \Hqueries \cup \{ q \}$; \\
+        \textbf{return} $r$;
+    \end{program}
+    %
+    \caption{The algorithm for the proof of theorem~\ref{thm:wap-dhp}}
+    \label{fig:wap-dhp-rdc}
+  \end{figure}
+
+  The adversary $A'$ is shown in figure~\ref{fig:wap-dhp-rdc}.  It generates
+  a random check-value and runs the impersonator $A$.
+  
+  The simulated random oracle $\Hsim$ gathers together the results of all of
+  the random oracle queries made by $A$.  The final result returned by $A'$
+  is randomly chosen from among all of the `plausible' random oracle queries
+  and $A$'s output, i.e., those queries which are actually members of the
+  group.  The check value given to $A$ is most likely incorrect (with
+  probability $1 - 2^{-k}$): the intuition is that $A$ can only notice if it
+  actually computes the right answer and then checks explicitly.
+
+  If $A$ does compute the correct answer $g^{\alpha\beta}$ and either returns
+  it or queries $\Hsim$ on it, then $A'$ succeeds with probability $\epsilon
+  / |(\Hlist \cup \{ x \}) \cap G| = \epsilon \poly{k}$, since $|\Hlist|$ is
+  no greater than the number of random oracle queries made by $A$ (which must
+  be polynomially bounded).\footnote{%
+    This polynomial factor introduces a loss in the perceived security of the
+    authentication protocol.  It appears that this loss is only caused by the
+    possibility of the adversary $A$ being deliberately awkward and checking
+    the value of $c$ after having computed the answer.  However, we can't see
+    a way to improve the security bound on the scheme without imposing
+    artificial requirements on $A$.} %
+  
+  It remains to show that if $A$ never queries its random oracle on
+  $g^{\alpha\beta}$ then it cannot distinguish the random check value $r$
+  from the correct one $\beta \xor \H(g^{\alpha\beta})$, and hence won't
+  notice that $A'$ is lying to it.  But this is obvious: $A$'s probability of
+  guessing the random value that would have been returned had it actually
+  queried $\Hsim$ on the input $g^{\alpha\beta}$ is equal to the probability
+  of it guessing $\beta \xor r$ instead, since $\Hsim$ chooses its responses
+  uniformly at random.  This completes the proof.
+\end{proof}
 
+We conclude here that the Wrestlers Authentication Protocol is a secure
+authentication protocol in the random oracle model: impersonation is hard if
+the Diffie-Hellman problem is hard, and proving one's identity doesn't leak
+secret key information.
 
-\section{A key exchange protocol}
+\subsection{Requirements on hash functions}
 
-We observe a useful side-effect of the authentication protocol just
-described: Bob should be convinved that Alice received his challenge $C$
-correctly.  The idea of the Wrestlers Protocol is to use this to construct a
-full Diffie-Hellman key exchange with mutual authentication.  We maintain the
-useful properties of the previous protocol.
+Having seen that the Wrestlers Authentication Protocol is secure in the
+random oracle model, we now ask which properties we require from the hash
+function.  This at least demonstrates that the protocol isn't deeply flawed,
+and suggests an efficient implementation in terms of conventional hash
+functions.
 
-Before they can use the protocol, Alice and Bob must agree on a group $G$ as
-before.  Alice chooses a private key $1 < a < q$, and publishes her public
-key $A = g^a$; Bob similarly chooses a private key $1 < b < q$ and publishes
-his public key $B = g^b$.
+Here we investigate more carefully the properties required of the hash
+function, and provide a more quantitative analysis of the protocol.
 
-Here's the actual protocol in summary:
-\begin{enumerate}
-\item $A \to   B$:\quad $g^\alpha$
-\item $A \from B$:\quad $g^\beta$, $H(g^\alpha, g^\beta, g^{a \beta})$
-\item $A \to   B$:\quad $g^{a \beta}$, $H(g^\beta, g^\alpha, g^{\alpha b})$
-\item $A \from B$:\quad $g^{\alpha b}$
-\end{enumerate}
+Looking at the proofs of the previous two sections, we see that the random
+oracles are mainly a device which allow our constructions to `grab hold' of
+the hashing operations performed by the adversary.
 
-And now in detail:
-\begin{enumerate}
+%%%--------------------------------------------------------------------------
+
+\section{A key-exchange protocol}
+% Present the Wrestlers protocol in all its glory.  Show, by means of the
+% previous proofs, that the Wrestlers protocol is simulatable in the
+% authenticated model using a much simpler protocol.  Show that the simpler
+% protocol is SK-secure.
+
+
+% messages
+%
+% pre-challenge: g^b
+% cookie: g^b, h(cookie, g^b')
+% challenge: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab')
+% reply: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab'), E_k(g^a'b)
+% switch: h(g^b), h(g^b'), E_k(g^a'b, h(switch-request, g^a, g^a'))
+% switch-ok: E_k(g^ab, h(switch-confirm, g^a, g^a'))begin{
+
+
+We now describe the full Wrestlers Protocol, in a multi-party setting.  Fix a
+cyclic group $G = \langle g \rangle$ of order $q = |G|$.  Each player $P_i$
+chooses a private key $\alpha_i \in \{ 1, 2, \ldots, q - 1 \}$ and publishes
+the corresponding public key $a_i = g^{\alpha_i}$ to the other players.
 
-\item Alice invents a temporary secret $1 < \alpha < q$.  She computes her
-  challenge $C_A = g^\alpha$, and sends it to Bob.
-  
-\item Bob receives the $C_A$, and stores it away.  He invents a temporary
-  secret $1 < \beta < q$ of his own, and computes both his challenge $C_B =
-  g^\beta$ and the expected response $R_B = A^\beta = g^{a \beta}$.  He
-  hashes both challenges (hers first) and the expected response $R_B$, and
-  sends his challenge and the hash back to Alice.
-  
-\item Alice reads Bob's challenge.  She computes her response $R_B' = C_B^a =
-  g^{a \beta}$ and ensures that the Bob's hash is correct.  If it isn't, she
-  stops talking to Bob.  If the hash matches, she sends back her response,
-  together with a hash of Bob's challenge, her original challenge from step
-  1, and her expected response $R_A = B^\alpha = g^{\alpha b}$.
 
-\item Bob reads Alice's response.  If it's wrong then he stops talking.
-  Otherwise he computes his response to Alice's challenge $R_A' = C_A^b =
-  g^{\alpha b}$ and checks Alice's hash.  If the hash is wrong, he also stops
-  talking.  Otherwise he sends the response back to Alice.
 
-\end{enumerate}
-Finally, Alice checks Bob's response, stopping the conversation if it's
-wrong.  Then both sides compute their shared key $K = C_A^\beta = C_B^\alpha
-= g^{\alpha \beta}$, and discard their temporary secrets.
-
-The protocol is essentially symmetrical: each side sends and receives both a
-challenge and hash pair, and a response, but it doesn't look that simple
-because the hashes include both sides' challenges.  Looking at it from one
-side at a time will make things clearer, so let's just take Alice's point of
-view.
-
-Alice constructs her challenge in step 1, and sends it off.  She receives a
-challenge and hash in step 2.  When she computes the response to the
-challenge, she verifies the hash she received.  If it matches, she knows that
-\begin{itemize}
-\item whoever she's talking to hasn't attempted to cheat her by sending a
-  challenge for which he doesn't know the answer; and
-\item he has successfully received her challenge.
-\end{itemize}
-Because she's now received a challenge, she can work out her hash.  She sends
-off her response to the challenge, together with the hash, and awaits the
-response.
-
-In step 4, the response arrives.  If it's correct, she knows that it's from
-Bob, and that he (Bob) received her challenge OK.  Tying everything else
-together is the tricky bit.
-
-If we assume that Bob is playing by the rules, the fact that he's sent his
-response means that he verified it against Alice's hash and decided that
-\begin{itemize}
-\item Alice wasn't trying to cheat him and find out about his private key;
-  and 
-\item Alice correctly received his challenge.
-\end{itemize}
-Because Bob wouldn't have replied if these weren't true, Alice can therefore
-believe that she has received Bob's challenge correctly.
-
-To summarize: Alice has managed to get a challenge to Bob, and he responded;
-Alice has also received Bob's challenge correctly.
-
-What if Bob isn't honest?  The only hole in the protocol which can be
-exploited by Bob is that he can send a response \emph{even though} it doesn't
-match Alice's hash.  This means that the protocol will continue even if Alice
-is attempting to cheat Bob and find information about his private key: this
-is a penalty Bob has to pay for not following the rules.  The protocol still
-aborts if an adversary interferes with the challenges: if Alice isn't given
-Bob's challenge accurately, her response will be wrong, and Bob can abort the
-exchange; similarly, if Bob isn't given Alice's challenge, she will detect
-this and abort the exchange.
-
-
-\section{Practical considerations}
-
-
-\section{Conclusions and further work}
-
-We have presented a new key exchange protocol based upon a novel use of
-Diffie-Hellman key exchange as a means of authentication.
-
-The arguments given in the previous section sound fairly convincing, but they
-don't provide a formal proof of the security of the Wrestlers Protocol.  The
-authors are unaware of a logic system for verifying protocols which correctly
-capture the properties of hash functions.
 
 %%%----- That's all, folks --------------------------------------------------
 
+\bibliography{cryptography,mdw-crypto}
 \end{document}
 
 %%% Local Variables: 
 %%% mode: latex
 %%% TeX-master: "wrestlers"
-%%% End: 
+%%% End:
