| 1 | %%% -*-latex-*- |
| 2 | %%% |
| 3 | %%% $Id: wrestlers.tex,v 1.4 2001/06/29 19:36:05 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.4 2001/06/29 19:36:05 mdw |
| 14 | %%% Some progress made on laptop. |
| 15 | %%% |
| 16 | %%% Revision 1.3 2001/06/22 19:41:31 mdw |
| 17 | %%% Restart with different structure and rather more formal objectives. |
| 18 | %%% |
| 19 | %%% Revision 1.2 2001/02/22 09:09:05 mdw |
| 20 | %%% Partially through reworking. |
| 21 | %%% |
| 22 | %%% Revision 1.1 2001/02/16 21:43:33 mdw |
| 23 | %%% Initial versions of documentation. |
| 24 | %%% |
| 25 | |
| 26 | \documentclass[a4paper]{article} |
| 27 | \usepackage{a4wide} |
| 28 | \usepackage{amssymb} |
| 29 | \usepackage{amstext} |
| 30 | \usepackage{mdwtab} |
| 31 | |
| 32 | \errorcontextlines=999 |
| 33 | \makeatletter |
| 34 | |
| 35 | \title{The Wrestlers Protocol: proof-of-receipt and secure key exchange} |
| 36 | \author{Mark Wooding \and Clive Jones} |
| 37 | |
| 38 | \bibliographystyle{alpha} |
| 39 | |
| 40 | \newtheorem{theorem}{Theorem} |
| 41 | \newenvironment{proof}[1][Proof]{% |
| 42 | \par\noindent\textbf{#1}\ % |
| 43 | }{% |
| 44 | \penalty\@M\hfill\vadjust{}% |
| 45 | \penalty\z@\relax\vadjust{}% |
| 46 | \penalty\@M\hfill$\square$% |
| 47 | \par% |
| 48 | } |
| 49 | |
| 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 | |
| 65 | \begin{document} |
| 66 | |
| 67 | \maketitle |
| 68 | \begin{abstract} |
| 69 | Fill this in later. |
| 70 | \end{abstract} |
| 71 | \tableofcontents |
| 72 | \newpage |
| 73 | |
| 74 | %%%-------------------------------------------------------------------------- |
| 75 | |
| 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. |
| 80 | |
| 81 | %%%-------------------------------------------------------------------------- |
| 82 | |
| 83 | \section{A simple authentication protocol} |
| 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. |
| 87 | |
| 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 | |
| 224 | |
| 225 | %%%-------------------------------------------------------------------------- |
| 226 | |
| 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]. |
| 230 | |
| 231 | %%%-------------------------------------------------------------------------- |
| 232 | |
| 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. |
| 238 | |
| 239 | %%%----- That's all, folks -------------------------------------------------- |
| 240 | |
| 241 | \bibliography{cryptography,mdw-crypto} |
| 242 | \end{document} |
| 243 | |
| 244 | %%% Local Variables: |
| 245 | %%% mode: latex |
| 246 | %%% TeX-master: "wrestlers" |
| 247 | %%% End: |