%%% -*-latex-*-
%%%
-%%% $Id: wrestlers.tex,v 1.2 2001/02/22 09:09:05 mdw Exp $
+%%% $Id: wrestlers.tex,v 1.4 2001/06/29 19:36:05 mdw Exp $
%%%
%%% Description of the Wrestlers Protocol
%%%
%%%----- Revision history ---------------------------------------------------
%%%
%%% $Log: wrestlers.tex,v $
+%%% 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.
%%%
%%% Initial versions of documentation.
%%%
-\documentclass{article}
+\documentclass[a4paper]{article}
+\usepackage{a4wide}
\usepackage{amssymb}
-\title{The Wrestlers Protocol}
-\author{Mark Wooding \\ Clive Jones}
-\def\from{\leftarrow}
+\usepackage{amstext}
+\usepackage{mdwtab}
+
+\errorcontextlines=999
+\makeatletter
+
+\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
+\author{Mark Wooding \and Clive Jones}
+
+\bibliographystyle{alpha}
+
+\newtheorem{theorem}{Theorem}
+\newenvironment{proof}[1][Proof]{%
+ \par\noindent\textbf{#1}\ %
+}{%
+ \penalty\@M\hfill\vadjust{}%
+ \penalty\z@\relax\vadjust{}%
+ \penalty\@M\hfill$\square$%
+ \par%
+}
+
+\newcommand{\rgets}{\stackrel{\scriptscriptstyle R}{\gets}}
+\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}{\mathrm{poly}}
+\newcommand{\compind}{\stackrel{c}{\approx}}
+
+\newcolumntype{G}{p{0pt}}
+
+\newenvironment{program}
+ {\begin{tabbing}}
+ {\end{tabbing}}
\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.
-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 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.
-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.
+\subsection{Introduction}
-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:
-\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.
-\end{enumerate}
+Suppose that $G$ is some cyclic group of prime order $q$, generated by an
+element $g$, in which the decision Diffie-Hellman problem
+\cite{Boneh:1998:DDP} is hard.
+
+Alice can choose a private key $1 < \alpha < q$ and publish her corresponding
+public key $A = g^\alpha$.
-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:
+A simplistic proof-of-identity protocol might then proceed as follows:
\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 random exponent $1 < \beta < q$, and sends a
+ \emph{challenge} $B = g^\beta$ to Alice.
+\item Alice computes $B^\alpha$ and returns it to Bob.
+\item If Alice's response is equal to $A^\beta$ then Bob is satisfied.
\end{enumerate}
+This is evidently secure if the Diffie-Hellman problem is hard: 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 this protocol by requiring that Bob prove that he already knows the
+answer to his challenge. Instead of sending just his challenge $B$, he sends
+the pair $(B, h(A^\beta))$ for some function $h$: Alice verifies that
+$h(B^\alpha) = h(A^\beta)$ before returning her response. We need to choose
+the function $h$ such that
+\begin{itemize}
+\item $h$ is one-way, so that providing $h(A^\beta)$ doesn't provide an
+ impersonator with an additional clue to guessing the correct response; and
+\item providing $h(A^\beta)$ is hard without previously knowing the value of
+ $A^\beta$.
+\end{itemize}
+\subsection{Analysis}
+
+We now examine the protocol in a more formal setting, with the objective of
+characterizing our requirements for the function $\oracle{H}$. Fix a
+\emph{group description} $\mathcal{G} = (G, q, g)$, where $G$ is a cyclic
+group of prime order $q$ generated by $g \in G$, and a function
+$\oracle{H}\colon \{ 0, 1 \}^* \to \{ 0, 1 \}^L$. Define the
+\emph{authentication oracle} $\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, x,
+h)$, where $\alpha \in \mathbb{Z} / q \mathbb{Z}$, $x \in g$ and $h \in \{ 0,
+1 \}^L$, to return $x^\alpha$ if $h = \oracle{H}(x^\alpha)$ and the symbol
+$\bot$ otherwise.
+
+We introduce two experiments:
+\begin{tabular}[C]{@{}G|G@{}}
+ \begin{program}
+ \quad \= \quad \= \kill
+ Experiment $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$ \\
+ \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\
+ \> $R \gets
+ A_{\text{cca}}
+ ^{\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, \cdot, \cdot),
+ \oracle{H}
+ (\cdot)}
+ (g^\alpha, g^\tau, \oracle{H}(g^{\alpha\tau}))$; \\
+ \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\
+ \> \textbf{else} \textbf{return} $0$;
+ \end{program}
+ &
+ \begin{program}
+ \quad \= \quad \= \kill
+ Experiment $\expt{uni-no}{A}(\mathcal{G})$ \\
+ \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\
+ \> $R \gets A(g^\alpha, g^\tau)$; \\
+ \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\
+ \> \textbf{else} \textbf{return} $0$;
+ \end{program}
+\end{tabular}
+We mandate that the adversary $A_{\text{cca}}$ never query its authentication
+oracle with the test challenge $g^\tau$.
+
+We will consider a function $\oracle{H}$ to be suitable for our purposes if
+for any adversary $A_{\text{cca}}$, there is an adversary $A$ for which the
+distributions of $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$
+and $\expt{uni-no}{A}(\mathcal{G})$ are computationally indistinguishable.
+Intuitively, this means that the authentication oracle isn't useful in
+attacking the protocol: any adversary which has access to an oracle can be
+replaced by one which has approximately the same probability of success but
+without oracle access.
+
+We first prove that a random oracle \cite{Bellare:1993:ROP} makes a
+`suitable' function.
+
+\begin{theorem}
+ If $\oracle{H}$ is a random oracle with $L$-bit output, where $L$ is some
+ polynomial function of the length of $q$, then, for any adversary
+ $A_{\text{cca}}$, there exists an adversary $A$ such that
+ \[ \expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})
+ \compind \expt{uni-no}{A}(\mathcal{G}) \]
+\end{theorem}
+\begin{proof}
+ The idea behind the proof is that we construct an adversary $A$ in terms of
+ the given adversary $A_{\text{cca}}$ with the same output in all but
+ negligibly few cases.
+
+ Our adversary $A$ isn't provided with either oracle supplied to
+ $A_{\text{cca}}$.
+
+ Simulating the random oracle is easy. $A$ maintains a table, initially
+ empty, of pairs $(q, r)$. When the oracle is invoked on input $q$, we look
+ it up in the table: if there is some entry $(q, r)$, it returns $r$;
+ otherwise we toss coins to choose a new output $r$ and add $(q, r)$ to the
+ table. This is obviously a polynomial-time activity, since
+ $A_{\text{cca}}$ makes only polynomially many queries, and answering each
+ one takes polynomial time.
+
+ The authentication oracle is a little harder. Suppose $A_{\text{cca}}$
+ makes a query $(x, h)$. If there is an entry $(q, h)$ in the random oracle
+ table, the authentication oracle returns $q$; otherwise it returns $\bot$.
-\section{A key exchange protocol}
+ It remains to show that this is a valid thing to do.
+\end{proof}
-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.
-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'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}
-And now in detail:
-\begin{enumerate}
-\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}
+\section{An MT-authenticator}
+% Use the protocol of the previous section as an MT-authenticator, within the
+% meaning of [Canetti:2001:AKE].
-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.
+\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.
%%%----- That's all, folks --------------------------------------------------
+\bibliography{cryptography,mdw-crypto}
\end{document}
%%% Local Variables:
~mdw / tripe / blobdiff