3 %%% $Id: wrestlers.tex,v 1.5 2002/01/13 14:55:31 mdw Exp $
5 %%% Description of the Wrestlers Protocol
7 %%% (c) 2001 Mark Wooding
10 %%%----- Revision history ---------------------------------------------------
12 %%% $Log: wrestlers.tex,v $
13 %%% Revision 1.5 2002/01/13 14:55:31 mdw
14 %%% More incomplete stuff.
16 %%% Revision 1.4 2001/06/29 19:36:05 mdw
17 %%% Some progress made on laptop.
19 %%% Revision 1.3 2001/06/22 19:41:31 mdw
20 %%% Restart with different structure and rather more formal objectives.
22 %%% Revision 1.2 2001/02/22 09:09:05 mdw
23 %%% Partially through reworking.
25 %%% Revision 1.1 2001/02/16 21:43:33 mdw
26 %%% Initial versions of documentation.
29 \newif\iffancystyle\fancystylefalse
33 [a4paper, article, 10pt, numbering, noherefloats, notitlepage]
35 \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
36 \usepackage[margin]{amsthm}
38 \documentclass[a4paper]{article}
43 \usepackage{amssymb, amstext}
44 \usepackage{mdwtab, mathenv}
46 \errorcontextlines=999
51 \title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
52 \author{Mark Wooding \and Clive Jones}
54 \bibliographystyle{alpha}
56 \newtheorem{theorem}{Theorem}
57 \renewcommand{\qedsymbol}{$\square$}
59 \newcommand{\getsr}{\stackrel{\scriptscriptstyle R}{\gets}}
60 \newcommand{\inr}{\in_{\scriptscriptstyle R}}
61 \newcommand{\oracle}[1]{\mathcal{#1}}
63 \newcommand{\expt}[2]{\mathbf{Exp}^{\text{\normalfont#1}}_{#2}}
64 \newcommand{\adv}[2]{\mathbf{Adv}^{\text{\normalfont#1}}_{#2}}
65 \newcommand{\ord}{\mathop{\operator@font ord}}
66 \newcommand{\poly}[1]{\mathop{\operator@font poly}({#1})}
67 \newcommand{\negl}[1]{\mathop{\operator@font negl}({#1})}
68 \newcommand{\compind}{\stackrel{c}{\approx}}
70 \newcolumntype{G}{p{0pt}}
72 \newcommand{\xor}{\oplus}
73 \renewcommand{\epsilon}{\varepsilon}
75 \newenvironment{program}
76 {\begin{tabular}[C]{|G|}\hlx{hv[][\tabcolsep]}\begin{tabbing}}
77 {\end{tabbing}\\\hlx{v[][\tabcolsep]h}\end{tabular}}
88 %%%--------------------------------------------------------------------------
90 \section{Introduction}
91 % Some waffle here about the desirability of a key-exchange protocol that
92 % doesn't leave signatures lying around, followed by an extended report of
93 % the various results.
95 %%%--------------------------------------------------------------------------
97 \section{A simple authentication protocol}
98 % Present the basic Diffie-Hellman-based authenticator, and prove that an
99 % authentication oracle is useless if the hash function has appropriate
102 We begin by introducing a simple proof-of-identity protocol, based on the
103 Diffie-Hellman key-exchange protocol \cite{Diffie:1976:NDC} and prove some of
104 its useful properties.
106 \subsection{Introduction}
108 We start by selecting a security parameter $k$. We choose a cyclic group $G
109 = \langle g \rangle$ with $q = |G|$ prime, in which the decision
110 Diffie-Hellman problem is assumed to be hard \cite{Boneh:1998:DDP}; we
111 require that $q$ is a $k$-bit number. Suitable groups include elliptic
112 curves over finite fields and prime-order subgroups of prime fields.
113 Throughout, we shall write the group operation as multiplication, and we
114 shall assume that group elements are interchangeable with their binary
117 Alice can choose a private key $\alpha$ from the set $\{ 1, 2, \ldots, q - 1
118 \}$ and publish her corresponding public key $a = g^\alpha$.
120 A simplistic proof-of-identity protocol might then proceed as follows:
122 \item Bob chooses a random exponent $\beta$, also from $\{ 1, 2, \ldots, q -
123 1 \}$, and sends a \emph{challenge} $b = g^\beta$ to Alice.
124 \item Alice computes her \emph{response} $b^\alpha$ and returns it to Bob.
125 \item If Alice's response is equal to $a^\beta$ then Bob is satisfied.
127 If Bob always plays by the rules then this protocol is evidently secure,
128 since computing $g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely
129 the Diffie-Hellman problem.
131 This protocol has a flaw, though: by using Alice as an oracle for the
132 function $x \mapsto x^\alpha$, he could conceivably acquire information about
133 Alice's private key which he could later use to impersonate her. As an
134 example, Bob can submit $-g^\beta$ as a challenge: if the reply
135 $(-g^\beta)^\alpha = g^{\alpha\beta}$, Bob can conclude that $\alpha$ is
138 We fix the protocol by requiring that Bob prove that he already knows the
139 answer to his challenge. We introduce a hash function $h$ whose properties
140 we shall investigate later. The \emph{Wrestlers Authentication Protocol} is
143 \item Bob chooses a secret $\beta \getsr \{ 1, 2, \ldots, q - 1 \}$. He
144 computes his \emph{challenge} $b \gets g^\beta$ and also a \emph{check
145 value} $c \gets \beta \xor h(a^\beta)$. He sends the pair $(b, c)$.
146 \item Alice receives $(b', c')$. She computes $r \gets b'^\alpha$ and
147 $\gamma \gets c' \xor h(R)$. If $b' = g^\gamma$, she sends $r$ back as her
148 \emph{response}; otherwise she sends the distinguished value $\bot$.
149 \item Bob receives $r'$. If $r' = a^\beta$ then he accepts that he's talking
152 We show that the introduction of the check value has indeed patched up the
153 weakness described above, and that the check value itself hasn't made an
154 impersonator's job much easier.
156 \subsection{Analysis in the random oracle model}
158 Here, we prove that the Wrestlers Authentication Protocol is secure if $h$ is
159 implemented by a public \emph{random oracle} \cite{Bellare:1993:ROP}.
161 Fix a private key $\alpha \inr \{ 1, 2, \ldots, q - 1\}$ and the corresponding public
162 key $a = g^\alpha$, and consider a probabilistic polynomial-time adversary
163 $A$, equipped with two oracles. One is a random oracle $\oracle{H}\colon
164 \{0, 1\}^* \to \{0, 1\}^k$, which implements a function $h$ randomly selected
165 from the set of all functions with that signature; the other is an
166 authentication oracle $\oracle{O}\colon G \times \{0, 1\}^k \to G \cup \{
169 \oracle{O}^(b, c) = \begin{cases}
170 b^\alpha & if $b = g^{c \xor h(b^\alpha)}$ \\
174 The authentication oracle will play the part of Alice in the following. We
175 first show that access to this authentication oracle can't help an adversary
176 learn how to impersonate Alice.
179 The Wrestlers Authentication Protocol with random oracle is computational
180 zero knowledge \cite{Brassard:1989:SZK}.
184 \newcommand{\Hlist}{\textit{$\oracle{H}$-list}}
185 \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}}
186 \newcommand{\Osim}{\textit{$\oracle{O}$-sim}}
187 \renewcommand{\H}{\oracle{H}}
188 \renewcommand{\O}{\oracle{O}}
190 Let $A$ be any probabilistic polynomial-time adversary with access to a
191 random. We shall construct a probabilistic polynomial-time adversary $A'$
192 without either oracle such that the probability distributions on the output
193 of $A$ and $A'$ are equal. Specifically, $A'$ runs $A$ with simulated
194 random and authentication oracles whose behaviour is computationally
195 indistinguishable from the originals. The algorithm for $A'$ and the
196 simulated oracles is shown in figure~\ref{fig:wap-czk-sim}.
201 Adversary $A'^{\H(\cdot)}$: \+ \\
202 $\Hlist \gets \emptyset$; \\
203 $r \gets A^{\Hsim(\cdot), \Osim(\cdot, \cdot)}$; \\
204 \textbf{return} $r$; \- \\[\medskipamount]
206 Simulated random oracle $\Hsim(q)$: \+ \\
207 \textbf{if} $\exists r : (q, r) \in \Hlist$ \textbf{then}
208 \textbf{return} $r$; \\
210 $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
211 \textbf{return} $r$; \- \\[\medskipamount]
213 Simulated authentication oracle $\Osim(b, c)$: \+ \\
214 \textbf{if} $\exists q, r : (q, r) \in \Hlist \wedge
215 b = g^{c \xor r} \wedge
216 q = a^{c \xor r}$ \textbf{then}
217 \textbf{return} $a^{c \xor r}$; \\
218 \textbf{else} \textbf{return} $\bot$;
221 \caption{The algorithm and simulated oracles for the proof of
222 theorem~\ref{thm:wap-czk}.}
223 \label{fig:wap-czk-sim}
226 Firstly we show that $A'$ runs in polynomial time. The only modifications
227 to $\Hlist$ are in $\Hsim$, which adds at most one element for each oracle
228 query. Since $\Hlist$ is initially empty and $A$ can only make $\poly{k}$
229 queries to $\Hsim$, this implies that $|\Hlist|$ is always
230 polynomially-bounded. Each query can be answered in polynomial time:
231 indeed, the search implied by the test $\exists r : (q, r) \in \Hlist$ can
232 be performed in $O(\log q)$ time by indexing $\Hlist$ on $q$ using a radix
233 tree. Now, since $|\Hlist|$ is polynomially bounded, the test $\exists q,
234 r : (q, r) \in \Hlist \wedge b = g^{c \xor r} \wedge q = a^{c \xor r}$ at
235 the start of $\Osim$ runs in polynomial time even though it requires an
236 exhaustive search of the history of $A$'s queries to its simulated random
239 Next, we examine the behaviour of the simulated oracles. Since $\Hsim$ is
240 implemented in terms of the public random oracle $\H$, and returns the same
241 answers to queries, its probability distribution must be identical.
243 We turn our attention to the simulation of the authentication oracle.
244 Consider a query $(b, c)$ made by $A$ to its authentication oracle.
246 Firstly, suppose that there is a $\beta$ such that $b = g^\beta$ and $c =
247 \beta \xor r$ where $r$ is the response to a previous query made by $A$ to
248 its random oracle on $a^\beta$. Then the true authentication oracle $\O$
249 is satisfied because $b = g^\beta = g^{c \xor r} = g^{c \xor h(a^\beta)} =
250 g^{c \xor h(b^\alpha)}$, and returns $b^\alpha$. Similarly, the simulated
251 authentication oracle $\Osim$ will find the pair $(a^\beta, r) \in \Hlist$,
252 recover $\beta = c \xor r$, confirm that $b = g^\beta$, and return
253 $a^\beta$ as required. These events all occur with probability 1.
255 Conversely, suppose that there is no such $\beta$. Then the simulated
256 oracle $\Osim$ will reject the query, returning $\bot$, again with
257 probability 1. However, a genuine authentication oracle $\O$ will succeed
258 and return $b^\alpha$ with probability $2^{-k}$. To see this, note that $b
259 = g^\gamma$ for some $\gamma \in \{ 0, 1, \ldots, q - 1 \}$, and the
260 probability that $h(b^\alpha) = c \xor \gamma$ is precisely $2^{-k}$, since
261 $c$ and $\gamma$ are $k$-bit strings. Since this probability is
262 negligible, we have shown that the distributions of the simulated oracles
263 $\Hsim$ and $\Osim$ are computationally indistinguishable from the genuine
264 oracles $\H$ and $\O$. The theorem follows.
267 Our next objective is to show that pretending to be Alice is hard without
268 knowledge of her secret $\alpha$. We say that an adversary $A$
269 \emph{impersonates} in the Wrestlers Authentication Protocol with probability
271 \[ \Pr[A^{\oracle{H}(\cdot)}(g^\alpha, g^\beta,
272 \beta \xor h(g^{\alpha\beta}))
276 where the probability is taken over all choices of $\alpha, \beta \in \{ 1,
277 2, \ldots, q - 1 \}$ and random oracles $\oracle{H}$.
280 Assuming that the Diffie-Hellman problem is hard in $G$, no probabilistic
281 polynomial-time adversary can impersonate in the Wrestlers Authentication
282 Protocol with random oracle with better than negligible probability.
286 \newcommand{\Hlist}{\textit{$\oracle{H}$-list}}
287 \newcommand{\Hqueries}{\textit{$\oracle{H}$-queries}}
288 \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}}
289 \renewcommand{\H}{\oracle{H}}
291 We prove the theorem by contradiction. Given a polynomial-time adversary
292 $A$ which impersonates Alice with non-negligible probability $\epsilon$, we
293 construct an adversary which solves the Diffie-Hellman problem with
294 probability no less than $\epsilon \poly{k}$, i.e.,
295 \[ \Pr[A'(g^\alpha, g^\beta) = g^{\alpha\beta}] \ge \epsilon \poly{k}. \]
296 Thus, if there is any polynomial-time $A$ which impersonates with better
297 than negligible probability, then there is a polynomial-time $A'$ which
298 solves Diffie-Hellman with essentially the same probability, which would
299 violate our assumption of the hardness of Diffie-Hellman.
301 The idea behind the proof is that the check value is only useful to $A$
302 once it has discovered the correct response to the challenge, which it must
303 have done by solving the Diffie-Hellman problem. Hence, our Diffie-Hellman
308 Adversary $A'(a, b)$: \+ \\
309 $\Hlist \gets \emptyset$; \\
310 $\Hqueries \gets \emptyset$; \\
311 $r \getsr \{ 0, 1 \}^k$; \\
312 $x \gets A^{\Hsim(\cdot)}(a, b, r)$; \\
313 $c \getsr (\Hlist \cup \{ x \}) \cap G$; \\
314 \textbf{return} $c$; \- \\[\medskipamount]
316 Simulated random oracle $\Hsim(q)$: \+ \\
317 \textbf{if} $\exists r : (q, r) \in \Hlist$
318 \textbf{then} \textbf{return} $r$; \\
319 $r \gets \{ 0, 1 \}^k$; \\
320 $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
321 $\Hqueries \gets \Hqueries \cup \{ q \}$; \\
325 \caption{The algorithm for the proof of theorem~\ref{thm:wap-dhp}}
326 \label{fig:wap-dhp-rdc}
329 The adversary $A'$ is shown in figure~\ref{fig:wap-dhp-rdc}. It generates
330 a random check-value and runs the impersonator $A$.
332 The simulated random oracle $\Hsim$ gathers together the results of all of
333 the random oracle queries made by $A$. The final result returned by $A'$
334 is randomly chosen from among all of the `plausible' random oracle queries
335 and $A$'s output, i.e., those queries which are actually members of the
336 group. The check value given to $A$ is most likely incorrect (with
337 probability $1 - 2^{-k}$): the intuition is that $A$ can only notice if it
338 actually computes the right answer and then checks explicitly.
340 If $A$ does compute the correct answer $g^{\alpha\beta}$ and either returns
341 it or queries $\Hsim$ on it, then $A'$ succeeds with probability $\epsilon
342 / |(\Hlist \cup \{ x \}) \cap G| = \epsilon \poly{k}$, since $|\Hlist|$ is
343 no greater than the number of random oracle queries made by $A$ (which must
344 be polynomially bounded).\footnote{%
345 This polynomial factor introduces a loss in the perceived security of the
346 authentication protocol. It appears that this loss is only caused by the
347 possibility of the adversary $A$ being deliberately awkward and checking
348 the value of $c$ after having computed the answer. However, we can't see
349 a way to improve the security bound on the scheme without imposing
350 artificial requirements on $A$.} %
352 It remains to show that if $A$ never queries its random oracle on
353 $g^{\alpha\beta}$ then it cannot distinguish the random check value $r$
354 from the correct one $\beta \xor \H(g^{\alpha\beta})$, and hence won't
355 notice that $A'$ is lying to it. But this is obvious: $A$'s probability of
356 guessing the random value that would have been returned had it actually
357 queried $\Hsim$ on the input $g^{\alpha\beta}$ is equal to the probability
358 of it guessing $\beta \xor r$ instead, since $\Hsim$ chooses its responses
359 uniformly at random. This completes the proof.
362 We conclude here that the Wrestlers Authentication Protocol is a secure
363 authentication protocol in the random oracle model: impersonation is hard if
364 the Diffie-Hellman problem is hard, and proving one's identity doesn't leak
365 secret key information.
367 \subsection{Requirements on hash functions}
369 Having seen that the Wrestlers Authentication Protocol is secure in the
370 random oracle model, we now ask which properties we require from the hash
371 function. This at least demonstrates that the protocol isn't deeply flawed,
372 and suggests an efficient implementation in terms of conventional hash
375 Here we investigate more carefully the properties required of the hash
376 function, and provide a more quantitative analysis of the protocol.
378 Looking at the proofs of the previous two sections, we see that the random
379 oracles are mainly a device which allow our constructions to `grab hold' of
380 the hashing operations performed by the adversary.
382 %%%--------------------------------------------------------------------------
384 \section{A key-exchange protocol}
385 % Present the Wrestlers protocol in all its glory. Show, by means of the
386 % previous proofs, that the Wrestlers protocol is simulatable in the
387 % authenticated model using a much simpler protocol. Show that the simpler
388 % protocol is SK-secure.
394 % cookie: g^b, h(cookie, g^b')
395 % challenge: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab')
396 % reply: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab'), E_k(g^a'b)
397 % switch: h(g^b), h(g^b'), E_k(g^a'b, h(switch-request, g^a, g^a'))
398 % switch-ok: E_k(g^ab, h(switch-confirm, g^a, g^a'))begin{
401 We now describe the full Wrestlers Protocol, in a multi-party setting. Fix a
402 cyclic group $G = \langle g \rangle$ of order $q = |G|$. Each player $P_i$
403 chooses a private key $\alpha_i \in \{ 1, 2, \ldots, q - 1 \}$ and publishes
404 the corresponding public key $a_i = g^{\alpha_i}$ to the other players.
409 %%%----- That's all, folks --------------------------------------------------
411 \bibliography{cryptography,mdw-crypto}
416 %%% TeX-master: "wrestlers"