chiark / gitweb /
More incomplete stuff.
[tripe] / doc / wrestlers.tex
74eb47db 1%%% -*-latex-*-
d7d62ac0 3%%% $Id: wrestlers.tex,v 1.5 2002/01/13 14:55:31 mdw Exp $
74eb47db 4%%%
5%%% Description of the Wrestlers Protocol
7%%% (c) 2001 Mark Wooding
10%%%----- Revision history ---------------------------------------------------
12%%% $Log: wrestlers.tex,v $
d7d62ac0 13%%% Revision 1.5 2002/01/13 14:55:31 mdw
14%%% More incomplete stuff.
1a981bdb 16%%% Revision 1.4 2001/06/29 19:36:05 mdw
17%%% Some progress made on laptop.
90d03a85 19%%% Revision 1.3 2001/06/22 19:41:31 mdw
20%%% Restart with different structure and rather more formal objectives.
874aed51 22%%% Revision 1.2 2001/02/22 09:09:05 mdw
23%%% Partially through reworking.
74eb47db 25%%% Revision 1.1 2001/02/16 21:43:33 mdw
26%%% Initial versions of documentation.
d7d62ac0 29\newif\iffancystyle\fancystylefalse
32 \documentclass
33 [a4paper, article, 10pt, numbering, noherefloats, notitlepage]
34 {strayman}
35 \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
36 \usepackage[margin]{amsthm}
38 \documentclass[a4paper]{article}
39 \usepackage{a4wide}
40 \usepackage{amsthm}
43\usepackage{amssymb, amstext}
44\usepackage{mdwtab, mathenv}
74eb47db 45
90d03a85 46\errorcontextlines=999
d7d62ac0 47\showboxbreadth=999
90d03a85 49\makeatletter
74eb47db 50
90d03a85 51\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
52\author{Mark Wooding \and Clive Jones}
74eb47db 53
90d03a85 54\bibliographystyle{alpha}
74eb47db 55
90d03a85 56\newtheorem{theorem}{Theorem}
d7d62ac0 57\renewcommand{\qedsymbol}{$\square$}
59\newcommand{\getsr}{\stackrel{\scriptscriptstyle R}{\gets}}
60\newcommand{\inr}{\in_{\scriptscriptstyle R}}
1a981bdb 61\newcommand{\oracle}[1]{\mathcal{#1}}
65\newcommand{\ord}{\mathop{\operator@font ord}}
d7d62ac0 66\newcommand{\poly}[1]{\mathop{\operator@font poly}({#1})}
67\newcommand{\negl}[1]{\mathop{\operator@font negl}({#1})}
1a981bdb 68\newcommand{\compind}{\stackrel{c}{\approx}}
d7d62ac0 72\newcommand{\xor}{\oplus}
1a981bdb 75\newenvironment{program}
d7d62ac0 76 {\begin{tabular}[C]{|G|}\hlx{hv[][\tabcolsep]}\begin{tabbing}}
77 {\end{tabbing}\\\hlx{v[][\tabcolsep]h}\end{tabular}}
1a981bdb 78
90d03a85 79\begin{document}
74eb47db 80
90d03a85 81\maketitle
83 Fill this in later.
74eb47db 87
90d03a85 88%%%--------------------------------------------------------------------------
74eb47db 89
90d03a85 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.
74eb47db 94
90d03a85 95%%%--------------------------------------------------------------------------
74eb47db 96
97\section{A simple authentication protocol}
90d03a85 98% Present the basic Diffie-Hellman-based authenticator, and prove that an
99% authentication oracle is useless if the hash function has appropriate
100% properties.
74eb47db 101
d7d62ac0 102We begin by introducing a simple proof-of-identity protocol, based on the
1a981bdb 103Diffie-Hellman key-exchange protocol \cite{Diffie:1976:NDC} and prove some of
104its useful properties.
d7d62ac0 108We 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
110Diffie-Hellman problem is assumed to be hard \cite{Boneh:1998:DDP}; we
111require that $q$ is a $k$-bit number. Suitable groups include elliptic
112curves over finite fields and prime-order subgroups of prime fields.
113Throughout, we shall write the group operation as multiplication, and we
114shall assume that group elements are interchangeable with their binary
1a981bdb 116
d7d62ac0 117Alice can choose a private key $\alpha$ from the set $\{ 1, 2, \ldots, q - 1
118\}$ and publish her corresponding public key $a = g^\alpha$.
1a981bdb 119
120A simplistic proof-of-identity protocol might then proceed as follows:
d7d62ac0 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.
1a981bdb 126\end{enumerate}
d7d62ac0 127If Bob always plays by the rules then this protocol is evidently secure,
128since computing $g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely
129the Diffie-Hellman problem.
1a981bdb 130
131This protocol has a flaw, though: by using Alice as an oracle for the
132function $x \mapsto x^\alpha$, he could conceivably acquire information about
133Alice's private key which he could later use to impersonate her. As an
134example, Bob can submit $-g^\beta$ as a challenge: if the reply
135$(-g^\beta)^\alpha = g^{\alpha\beta}$, Bob can conclude that $\alpha$ is
d7d62ac0 138We fix the protocol by requiring that Bob prove that he already knows the
139answer to his challenge. We introduce a hash function $h$ whose properties
140we 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
150 to Alice.
152We show that the introduction of the check value has indeed patched up the
153weakness described above, and that the check value itself hasn't made an
154impersonator's job much easier.
156\subsection{Analysis in the random oracle model}
158Here, we prove that the Wrestlers Authentication Protocol is secure if $h$ is
159implemented by a public \emph{random oracle} \cite{Bellare:1993:ROP}.
161Fix a private key $\alpha \inr \{ 1, 2, \ldots, q - 1\}$ and the corresponding public
162key $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
165from the set of all functions with that signature; the other is an
166authentication oracle $\oracle{O}\colon G \times \{0, 1\}^k \to G \cup \{
167\bot \}$ defined by:
169\oracle{O}^(b, c) = \begin{cases}
170 b^\alpha & if $b = g^{c \xor h(b^\alpha)}$ \\
171 \bot & otherwise
174The authentication oracle will play the part of Alice in the following. We
175first show that access to this authentication oracle can't help an adversary
176learn how to impersonate Alice.
1a981bdb 177
d7d62ac0 179 The Wrestlers Authentication Protocol with random oracle is computational
180 zero knowledge \cite{Brassard:1989:SZK}.
181 \label{thm:wap-czk}
1a981bdb 182\end{theorem}
d7d62ac0 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}}
189 %
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}.
198 \begin{figure}
199 \begin{program}
200 \quad \= \kill
201 Adversary $A'^{\H(\cdot)}$: \+ \\
202 $\Hlist \gets \emptyset$; \\
203 $r \gets A^{\Hsim(\cdot), \Osim(\cdot, \cdot)}$; \\
204 \textbf{return} $r$; \- \\[\medskipamount]
205 %
206 Simulated random oracle $\Hsim(q)$: \+ \\
207 \textbf{if} $\exists r : (q, r) \in \Hlist$ \textbf{then}
208 \textbf{return} $r$; \\
209 $r \getsr \H(q)$; \\
210 $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
211 \textbf{return} $r$; \- \\[\medskipamount]
212 %
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$;
219 \end{program}
220 %
221 \caption{The algorithm and simulated oracles for the proof of
222 theorem~\ref{thm:wap-czk}.}
223 \label{fig:wap-czk-sim}
224 \end{figure}
1a981bdb 225
d7d62ac0 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
237 oracle.
1a981bdb 238
d7d62ac0 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.
1a981bdb 265\end{proof}
d7d62ac0 267Our next objective is to show that pretending to be Alice is hard without
268knowledge of her secret $\alpha$. We say that an adversary $A$
269\emph{impersonates} in the Wrestlers Authentication Protocol with probability
270$\epsilon$ if
271\[ \Pr[A^{\oracle{H}(\cdot)}(g^\alpha, g^\beta,
272 \beta \xor h(g^{\alpha\beta}))
273 = g^{\alpha\beta}]
274 = \epsilon
276where the probability is taken over all choices of $\alpha, \beta \in \{ 1,
2772, \ldots, q - 1 \}$ and random oracles $\oracle{H}$.
1a981bdb 278
d7d62ac0 279\begin{theorem}
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.
283 \label{thm:wap-dhp}
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}}
290 %
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
305 \begin{figure}
306 \begin{program}
307 \quad \= \kill
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]
315 %
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 \}$; \\
322 \textbf{return} $r$;
323 \end{program}
324 %
325 \caption{The algorithm for the proof of theorem~\ref{thm:wap-dhp}}
326 \label{fig:wap-dhp-rdc}
327 \end{figure}
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.
1a981bdb 361
d7d62ac0 362We conclude here that the Wrestlers Authentication Protocol is a secure
363authentication protocol in the random oracle model: impersonation is hard if
364the Diffie-Hellman problem is hard, and proving one's identity doesn't leak
365secret key information.
1a981bdb 366
d7d62ac0 367\subsection{Requirements on hash functions}
1a981bdb 368
d7d62ac0 369Having seen that the Wrestlers Authentication Protocol is secure in the
370random oracle model, we now ask which properties we require from the hash
371function. This at least demonstrates that the protocol isn't deeply flawed,
372and suggests an efficient implementation in terms of conventional hash
1a981bdb 374
d7d62ac0 375Here we investigate more carefully the properties required of the hash
376function, and provide a more quantitative analysis of the protocol.
1a981bdb 377
d7d62ac0 378Looking at the proofs of the previous two sections, we see that the random
379oracles are mainly a device which allow our constructions to `grab hold' of
380the hashing operations performed by the adversary.
1a981bdb 381
d7d62ac0 382%%%--------------------------------------------------------------------------
1a981bdb 383
d7d62ac0 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.
1a981bdb 389
d7d62ac0 391% messages
393% pre-challenge: g^b
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{
1a981bdb 399
874aed51 400
d7d62ac0 401We now describe the full Wrestlers Protocol, in a multi-party setting. Fix a
402cyclic group $G = \langle g \rangle$ of order $q = |G|$. Each player $P_i$
403chooses a private key $\alpha_i \in \{ 1, 2, \ldots, q - 1 \}$ and publishes
404the corresponding public key $a_i = g^{\alpha_i}$ to the other players.
874aed51 405
74eb47db 406
74eb47db 407
74eb47db 408
409%%%----- That's all, folks --------------------------------------------------
90d03a85 411\bibliography{cryptography,mdw-crypto}
74eb47db 412\end{document}
414%%% Local Variables:
415%%% mode: latex
416%%% TeX-master: "wrestlers"
d7d62ac0 417%%% End: