74eb47db |
1 | %%% -*-latex-*- |
2 | %%% |
1a981bdb |
3 | %%% $Id: wrestlers.tex,v 1.4 2001/06/29 19:36:05 mdw Exp $ |
74eb47db |
4 | %%% |
5 | %%% Description of the Wrestlers Protocol |
6 | %%% |
7 | %%% (c) 2001 Mark Wooding |
8 | %%% |
9 | |
10 | %%%----- Revision history --------------------------------------------------- |
11 | %%% |
12 | %%% $Log: wrestlers.tex,v $ |
1a981bdb |
13 | %%% Revision 1.4 2001/06/29 19:36:05 mdw |
14 | %%% Some progress made on laptop. |
15 | %%% |
90d03a85 |
16 | %%% Revision 1.3 2001/06/22 19:41:31 mdw |
17 | %%% Restart with different structure and rather more formal objectives. |
18 | %%% |
874aed51 |
19 | %%% Revision 1.2 2001/02/22 09:09:05 mdw |
20 | %%% Partially through reworking. |
21 | %%% |
74eb47db |
22 | %%% Revision 1.1 2001/02/16 21:43:33 mdw |
23 | %%% Initial versions of documentation. |
24 | %%% |
25 | |
1a981bdb |
26 | \documentclass[a4paper]{article} |
27 | \usepackage{a4wide} |
74eb47db |
28 | \usepackage{amssymb} |
90d03a85 |
29 | \usepackage{amstext} |
1a981bdb |
30 | \usepackage{mdwtab} |
74eb47db |
31 | |
90d03a85 |
32 | \errorcontextlines=999 |
33 | \makeatletter |
74eb47db |
34 | |
90d03a85 |
35 | \title{The Wrestlers Protocol: proof-of-receipt and secure key exchange} |
36 | \author{Mark Wooding \and Clive Jones} |
74eb47db |
37 | |
90d03a85 |
38 | \bibliographystyle{alpha} |
74eb47db |
39 | |
90d03a85 |
40 | \newtheorem{theorem}{Theorem} |
41 | \newenvironment{proof}[1][Proof]{% |
1a981bdb |
42 | \par\noindent\textbf{#1}\ % |
90d03a85 |
43 | }{% |
44 | \penalty\@M\hfill\vadjust{}% |
45 | \penalty\z@\relax\vadjust{}% |
46 | \penalty\@M\hfill$\square$% |
47 | \par% |
48 | } |
74eb47db |
49 | |
1a981bdb |
50 | \newcommand{\rgets}{\stackrel{\scriptscriptstyle R}{\gets}} |
51 | \newcommand{\oracle}[1]{\mathcal{#1}} |
52 | |
53 | \newcommand{\expt}[2]{\mathbf{Exp}^{\text{\normalfont#1}}_{#2}} |
54 | \newcommand{\adv}[2]{\mathbf{Adv}^{\text{\normalfont#1}}_{#2}} |
55 | \newcommand{\ord}{\mathop{\operator@font ord}} |
56 | \newcommand{\poly}{\mathrm{poly}} |
57 | \newcommand{\compind}{\stackrel{c}{\approx}} |
58 | |
59 | \newcolumntype{G}{p{0pt}} |
60 | |
61 | \newenvironment{program} |
62 | {\begin{tabbing}} |
63 | {\end{tabbing}} |
64 | |
90d03a85 |
65 | \begin{document} |
74eb47db |
66 | |
90d03a85 |
67 | \maketitle |
68 | \begin{abstract} |
69 | Fill this in later. |
70 | \end{abstract} |
71 | \tableofcontents |
72 | \newpage |
74eb47db |
73 | |
90d03a85 |
74 | %%%-------------------------------------------------------------------------- |
74eb47db |
75 | |
90d03a85 |
76 | \section{Introduction} |
77 | % Some waffle here about the desirability of a key-exchange protocol that |
78 | % doesn't leave signatures lying around, followed by an extended report of |
79 | % the various results. |
74eb47db |
80 | |
90d03a85 |
81 | %%%-------------------------------------------------------------------------- |
74eb47db |
82 | |
83 | \section{A simple authentication protocol} |
90d03a85 |
84 | % Present the basic Diffie-Hellman-based authenticator, and prove that an |
85 | % authentication oracle is useless if the hash function has appropriate |
86 | % properties. |
74eb47db |
87 | |
1a981bdb |
88 | We start by introducing a simple proof-of-identity protocol, based on the |
89 | Diffie-Hellman key-exchange protocol \cite{Diffie:1976:NDC} and prove some of |
90 | its useful properties. |
91 | |
92 | \subsection{Introduction} |
93 | |
94 | Suppose that $G$ is some cyclic group of prime order $q$, generated by an |
95 | element $g$, in which the decision Diffie-Hellman problem |
96 | \cite{Boneh:1998:DDP} is hard. |
97 | |
98 | Alice can choose a private key $1 < \alpha < q$ and publish her corresponding |
99 | public key $A = g^\alpha$. |
100 | |
101 | A simplistic proof-of-identity protocol might then proceed as follows: |
102 | \begin{enumerate} |
103 | \item Bob chooses a random exponent $1 < \beta < q$, and sends a |
104 | \emph{challenge} $B = g^\beta$ to Alice. |
105 | \item Alice computes $B^\alpha$ and returns it to Bob. |
106 | \item If Alice's response is equal to $A^\beta$ then Bob is satisfied. |
107 | \end{enumerate} |
108 | This is evidently secure if the Diffie-Hellman problem is hard: computing |
109 | $g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely the |
110 | Diffie-Hellman problem. |
111 | |
112 | This protocol has a flaw, though: by using Alice as an oracle for the |
113 | function $x \mapsto x^\alpha$, he could conceivably acquire information about |
114 | Alice's private key which he could later use to impersonate her. As an |
115 | example, Bob can submit $-g^\beta$ as a challenge: if the reply |
116 | $(-g^\beta)^\alpha = g^{\alpha\beta}$, Bob can conclude that $\alpha$ is |
117 | even. |
118 | |
119 | We fix this protocol by requiring that Bob prove that he already knows the |
120 | answer to his challenge. Instead of sending just his challenge $B$, he sends |
121 | the pair $(B, h(A^\beta))$ for some function $h$: Alice verifies that |
122 | $h(B^\alpha) = h(A^\beta)$ before returning her response. We need to choose |
123 | the function $h$ such that |
124 | \begin{itemize} |
125 | \item $h$ is one-way, so that providing $h(A^\beta)$ doesn't provide an |
126 | impersonator with an additional clue to guessing the correct response; and |
127 | \item providing $h(A^\beta)$ is hard without previously knowing the value of |
128 | $A^\beta$. |
129 | \end{itemize} |
130 | |
131 | \subsection{Analysis} |
132 | |
133 | We now examine the protocol in a more formal setting, with the objective of |
134 | characterizing our requirements for the function $\oracle{H}$. Fix a |
135 | \emph{group description} $\mathcal{G} = (G, q, g)$, where $G$ is a cyclic |
136 | group of prime order $q$ generated by $g \in G$, and a function |
137 | $\oracle{H}\colon \{ 0, 1 \}^* \to \{ 0, 1 \}^L$. Define the |
138 | \emph{authentication oracle} $\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, x, |
139 | h)$, where $\alpha \in \mathbb{Z} / q \mathbb{Z}$, $x \in g$ and $h \in \{ 0, |
140 | 1 \}^L$, to return $x^\alpha$ if $h = \oracle{H}(x^\alpha)$ and the symbol |
141 | $\bot$ otherwise. |
142 | |
143 | We introduce two experiments: |
144 | \begin{tabular}[C]{@{}G|G@{}} |
145 | \begin{program} |
146 | \quad \= \quad \= \kill |
147 | Experiment $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$ \\ |
148 | \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\ |
149 | \> $R \gets |
150 | A_{\text{cca}} |
151 | ^{\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, \cdot, \cdot), |
152 | \oracle{H} |
153 | (\cdot)} |
154 | (g^\alpha, g^\tau, \oracle{H}(g^{\alpha\tau}))$; \\ |
155 | \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\ |
156 | \> \textbf{else} \textbf{return} $0$; |
157 | \end{program} |
158 | & |
159 | \begin{program} |
160 | \quad \= \quad \= \kill |
161 | Experiment $\expt{uni-no}{A}(\mathcal{G})$ \\ |
162 | \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\ |
163 | \> $R \gets A(g^\alpha, g^\tau)$; \\ |
164 | \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\ |
165 | \> \textbf{else} \textbf{return} $0$; |
166 | \end{program} |
167 | \end{tabular} |
168 | We mandate that the adversary $A_{\text{cca}}$ never query its authentication |
169 | oracle with the test challenge $g^\tau$. |
170 | |
171 | We will consider a function $\oracle{H}$ to be suitable for our purposes if |
172 | for any adversary $A_{\text{cca}}$, there is an adversary $A$ for which the |
173 | distributions of $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$ |
174 | and $\expt{uni-no}{A}(\mathcal{G})$ are computationally indistinguishable. |
175 | Intuitively, this means that the authentication oracle isn't useful in |
176 | attacking the protocol: any adversary which has access to an oracle can be |
177 | replaced by one which has approximately the same probability of success but |
178 | without oracle access. |
179 | |
180 | We first prove that a random oracle \cite{Bellare:1993:ROP} makes a |
181 | `suitable' function. |
182 | |
183 | \begin{theorem} |
184 | If $\oracle{H}$ is a random oracle with $L$-bit output, where $L$ is some |
185 | polynomial function of the length of $q$, then, for any adversary |
186 | $A_{\text{cca}}$, there exists an adversary $A$ such that |
187 | \[ \expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G}) |
188 | \compind \expt{uni-no}{A}(\mathcal{G}) \] |
189 | \end{theorem} |
190 | \begin{proof} |
191 | The idea behind the proof is that we construct an adversary $A$ in terms of |
192 | the given adversary $A_{\text{cca}}$ with the same output in all but |
193 | negligibly few cases. |
194 | |
195 | Our adversary $A$ isn't provided with either oracle supplied to |
196 | $A_{\text{cca}}$. |
197 | |
198 | Simulating the random oracle is easy. $A$ maintains a table, initially |
199 | empty, of pairs $(q, r)$. When the oracle is invoked on input $q$, we look |
200 | it up in the table: if there is some entry $(q, r)$, it returns $r$; |
201 | otherwise we toss coins to choose a new output $r$ and add $(q, r)$ to the |
202 | table. This is obviously a polynomial-time activity, since |
203 | $A_{\text{cca}}$ makes only polynomially many queries, and answering each |
204 | one takes polynomial time. |
205 | |
206 | The authentication oracle is a little harder. Suppose $A_{\text{cca}}$ |
207 | makes a query $(x, h)$. If there is an entry $(q, h)$ in the random oracle |
208 | table, the authentication oracle returns $q$; otherwise it returns $\bot$. |
209 | |
210 | It remains to show that this is a valid thing to do. |
211 | \end{proof} |
212 | |
213 | |
214 | |
215 | |
216 | |
217 | |
218 | |
219 | |
220 | |
221 | |
222 | |
223 | |
874aed51 |
224 | |
90d03a85 |
225 | %%%-------------------------------------------------------------------------- |
874aed51 |
226 | |
90d03a85 |
227 | \section{An MT-authenticator} |
228 | % Use the protocol of the previous section as an MT-authenticator, within the |
229 | % meaning of [Canetti:2001:AKE]. |
74eb47db |
230 | |
90d03a85 |
231 | %%%-------------------------------------------------------------------------- |
74eb47db |
232 | |
90d03a85 |
233 | \section{A key-exchange protocol} |
234 | % Present the Wrestlers protocol in all its glory. Show, by means of the |
235 | % previous proofs, that the Wrestlers protocol is simulatable in the |
236 | % authenticated model using a much simpler protocol. Show that the simpler |
237 | % protocol is SK-secure. |
74eb47db |
238 | |
239 | %%%----- That's all, folks -------------------------------------------------- |
240 | |
90d03a85 |
241 | \bibliography{cryptography,mdw-crypto} |
74eb47db |
242 | \end{document} |
243 | |
244 | %%% Local Variables: |
245 | %%% mode: latex |
246 | %%% TeX-master: "wrestlers" |
247 | %%% End: |