chiark / gitweb /
More incomplete stuff.
[tripe] / doc / wrestlers.tex
1 %%% -*-latex-*-
2 %%%
3 %%% $Id: wrestlers.tex,v 1.5 2002/01/13 14:55:31 mdw Exp $
4 %%%
5 %%% Description of the Wrestlers Protocol
6 %%%
7 %%% (c) 2001 Mark Wooding
8 %%%
9
10 %%%----- Revision history ---------------------------------------------------
11 %%%
12 %%% $Log: wrestlers.tex,v $
13 %%% Revision 1.5  2002/01/13 14:55:31  mdw
14 %%% More incomplete stuff.
15 %%%
16 %%% Revision 1.4  2001/06/29 19:36:05  mdw
17 %%% Some progress made on laptop.
18 %%%
19 %%% Revision 1.3  2001/06/22 19:41:31  mdw
20 %%% Restart with different structure and rather more formal objectives.
21 %%%
22 %%% Revision 1.2  2001/02/22 09:09:05  mdw
23 %%% Partially through reworking.
24 %%%
25 %%% Revision 1.1  2001/02/16 21:43:33  mdw
26 %%% Initial versions of documentation.
27 %%%
28
29 \newif\iffancystyle\fancystylefalse
30
31 \iffancystyle
32   \documentclass
33     [a4paper, article, 10pt, numbering, noherefloats, notitlepage]
34     {strayman}
35   \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
36   \usepackage[margin]{amsthm}
37 \else
38   \documentclass[a4paper]{article}
39   \usepackage{a4wide}
40   \usepackage{amsthm}
41 \fi
42
43 \usepackage{amssymb, amstext}
44 \usepackage{mdwtab, mathenv}
45
46 \errorcontextlines=999
47 \showboxbreadth=999
48 \showboxdepth=999
49 \makeatletter
50
51 \title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
52 \author{Mark Wooding \and Clive Jones}
53
54 \bibliographystyle{alpha}
55
56 \newtheorem{theorem}{Theorem}
57 \renewcommand{\qedsymbol}{$\square$}
58
59 \newcommand{\getsr}{\stackrel{\scriptscriptstyle R}{\gets}}
60 \newcommand{\inr}{\in_{\scriptscriptstyle R}}
61 \newcommand{\oracle}[1]{\mathcal{#1}}
62
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}}
69
70 \newcolumntype{G}{p{0pt}}
71
72 \newcommand{\xor}{\oplus}
73 \renewcommand{\epsilon}{\varepsilon}
74
75 \newenvironment{program}
76   {\begin{tabular}[C]{|G|}\hlx{hv[][\tabcolsep]}\begin{tabbing}}
77   {\end{tabbing}\\\hlx{v[][\tabcolsep]h}\end{tabular}}
78
79 \begin{document}
80
81 \maketitle
82 \begin{abstract}
83   Fill this in later.
84 \end{abstract}
85 \tableofcontents
86 \newpage
87
88 %%%--------------------------------------------------------------------------
89
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.
94
95 %%%--------------------------------------------------------------------------
96
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
100 % properties.
101
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.
105
106 \subsection{Introduction}
107
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
115 representations.
116
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$.
119
120 A simplistic proof-of-identity protocol might then proceed as follows:
121 \begin{enumerate}
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.
126 \end{enumerate}
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.
130
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
136 even.
137
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
141 then:
142 \begin{enumerate}
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.
151 \end{enumerate}
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.
155
156 \subsection{Analysis in the random oracle model}
157
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}.
160
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 \{
167 \bot \}$ defined by:
168 \[
169 \oracle{O}^(b, c) = \begin{cases}
170   b^\alpha & if $b = g^{c \xor h(b^\alpha)}$ \\
171   \bot     & otherwise
172 \end{cases}
173 \]
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.
177
178 \begin{theorem}
179   The Wrestlers Authentication Protocol with random oracle is computational
180   zero knowledge \cite{Brassard:1989:SZK}.
181   \label{thm:wap-czk}
182 \end{theorem}
183 \begin{proof}
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}.
197
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}
225   
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.
238   
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.
242   
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.
245   
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.
254
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.
265 \end{proof}
266
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
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
275 \]
276 where the probability is taken over all choices of $\alpha, \beta \in \{ 1,
277 2, \ldots, q - 1 \}$ and random oracles $\oracle{H}$.
278
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}
284 \end{theorem}
285 \begin{proof}
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.
300
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
304
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}
328
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$.
331   
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.
339
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$.} %
351   
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.
360 \end{proof}
361
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.
366
367 \subsection{Requirements on hash functions}
368
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
373 functions.
374
375 Here we investigate more carefully the properties required of the hash
376 function, and provide a more quantitative analysis of the protocol.
377
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.
381
382 %%%--------------------------------------------------------------------------
383
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.
389
390
391 % messages
392 %
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{
399
400
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.
405
406
407
408
409 %%%----- That's all, folks --------------------------------------------------
410
411 \bibliography{cryptography,mdw-crypto}
412 \end{document}
413
414 %%% Local Variables: 
415 %%% mode: latex
416 %%% TeX-master: "wrestlers"
417 %%% End: