From 1a981bdb7da1f52ca5639e59610425f9d30ae860 Mon Sep 17 00:00:00 2001 Message-Id: <1a981bdb7da1f52ca5639e59610425f9d30ae860.1714799153.git.mdw@distorted.org.uk> From: Mark Wooding Date: Fri, 29 Jun 2001 19:36:05 +0000 Subject: [PATCH] Some progress made on laptop. Organization: Straylight/Edgeware From: mdw --- doc/wrestlers.tex | 169 +++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 159 insertions(+), 10 deletions(-) diff --git a/doc/wrestlers.tex b/doc/wrestlers.tex index 033f9fea..a37b6435 100644 --- a/doc/wrestlers.tex +++ b/doc/wrestlers.tex @@ -1,6 +1,6 @@ %%% -*-latex-*- %%% -%%% $Id: wrestlers.tex,v 1.3 2001/06/22 19:41:31 mdw Exp $ +%%% $Id: wrestlers.tex,v 1.4 2001/06/29 19:36:05 mdw Exp $ %%% %%% Description of the Wrestlers Protocol %%% @@ -10,6 +10,9 @@ %%%----- Revision history --------------------------------------------------- %%% %%% $Log: wrestlers.tex,v $ +%%% Revision 1.4 2001/06/29 19:36:05 mdw +%%% Some progress made on laptop. +%%% %%% Revision 1.3 2001/06/22 19:41:31 mdw %%% Restart with different structure and rather more formal objectives. %%% @@ -20,9 +23,11 @@ %%% Initial versions of documentation. %%% -\documentclass{article} +\documentclass[a4paper]{article} +\usepackage{a4wide} \usepackage{amssymb} \usepackage{amstext} +\usepackage{mdwtab} \errorcontextlines=999 \makeatletter @@ -34,7 +39,7 @@ \newtheorem{theorem}{Theorem} \newenvironment{proof}[1][Proof]{% - \par\noindent\textbf{#1.} % + \par\noindent\textbf{#1}\ % }{% \penalty\@M\hfill\vadjust{}% \penalty\z@\relax\vadjust{}% @@ -42,6 +47,21 @@ \par% } +\newcommand{\rgets}{\stackrel{\scriptscriptstyle R}{\gets}} +\newcommand{\oracle}[1]{\mathcal{#1}} + +\newcommand{\expt}[2]{\mathbf{Exp}^{\text{\normalfont#1}}_{#2}} +\newcommand{\adv}[2]{\mathbf{Adv}^{\text{\normalfont#1}}_{#2}} +\newcommand{\ord}{\mathop{\operator@font ord}} +\newcommand{\poly}{\mathrm{poly}} +\newcommand{\compind}{\stackrel{c}{\approx}} + +\newcolumntype{G}{p{0pt}} + +\newenvironment{program} + {\begin{tabbing}} + {\end{tabbing}} + \begin{document} \maketitle @@ -65,13 +85,142 @@ % authentication oracle is useless if the hash function has appropriate % properties. -Suppose that $G$ is some cyclic group of order $q$, generated by an element -$g$, in which the decision Diffie-Hellman problem \cite{Boneh:1998:DDP} is -hard. Alice can choose a private key $1 < \alpha < q$ and publish her -corresponding public key $A = g^\alpha$. Later, Bob can verify that he's -talking to Alice by choosing a random $1 < \beta < q$ and sending Alice a -\emph{challenge} $B = g^\beta$. If she replies with $B^\alpha$, Bob accepts -that he's talking to Alice, otherwise he doesn't. +We start by introducing a simple proof-of-identity protocol, based on the +Diffie-Hellman key-exchange protocol \cite{Diffie:1976:NDC} and prove some of +its useful properties. + +\subsection{Introduction} + +Suppose that $G$ is some cyclic group of prime order $q$, generated by an +element $g$, in which the decision Diffie-Hellman problem +\cite{Boneh:1998:DDP} is hard. + +Alice can choose a private key $1 < \alpha < q$ and publish her corresponding +public key $A = g^\alpha$. + +A simplistic proof-of-identity protocol might then proceed as follows: +\begin{enumerate} +\item Bob chooses a random exponent $1 < \beta < q$, and sends a + \emph{challenge} $B = g^\beta$ to Alice. +\item Alice computes $B^\alpha$ and returns it to Bob. +\item If Alice's response is equal to $A^\beta$ then Bob is satisfied. +\end{enumerate} +This is evidently secure if the Diffie-Hellman problem is hard: computing +$g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely the +Diffie-Hellman problem. + +This protocol has a flaw, though: by using Alice as an oracle for the +function $x \mapsto x^\alpha$, he could conceivably acquire information about +Alice's private key which he could later use to impersonate her. As an +example, Bob can submit $-g^\beta$ as a challenge: if the reply +$(-g^\beta)^\alpha = g^{\alpha\beta}$, Bob can conclude that $\alpha$ is +even. + +We fix this protocol by requiring that Bob prove that he already knows the +answer to his challenge. Instead of sending just his challenge $B$, he sends +the pair $(B, h(A^\beta))$ for some function $h$: Alice verifies that +$h(B^\alpha) = h(A^\beta)$ before returning her response. We need to choose +the function $h$ such that +\begin{itemize} +\item $h$ is one-way, so that providing $h(A^\beta)$ doesn't provide an + impersonator with an additional clue to guessing the correct response; and +\item providing $h(A^\beta)$ is hard without previously knowing the value of + $A^\beta$. +\end{itemize} + +\subsection{Analysis} + +We now examine the protocol in a more formal setting, with the objective of +characterizing our requirements for the function $\oracle{H}$. Fix a +\emph{group description} $\mathcal{G} = (G, q, g)$, where $G$ is a cyclic +group of prime order $q$ generated by $g \in G$, and a function +$\oracle{H}\colon \{ 0, 1 \}^* \to \{ 0, 1 \}^L$. Define the +\emph{authentication oracle} $\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, x, +h)$, where $\alpha \in \mathbb{Z} / q \mathbb{Z}$, $x \in g$ and $h \in \{ 0, +1 \}^L$, to return $x^\alpha$ if $h = \oracle{H}(x^\alpha)$ and the symbol +$\bot$ otherwise. + +We introduce two experiments: +\begin{tabular}[C]{@{}G|G@{}} + \begin{program} + \quad \= \quad \= \kill + Experiment $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$ \\ + \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\ + \> $R \gets + A_{\text{cca}} + ^{\oracle{O}_{\mathcal{G}, \oracle{H}}(\alpha, \cdot, \cdot), + \oracle{H} + (\cdot)} + (g^\alpha, g^\tau, \oracle{H}(g^{\alpha\tau}))$; \\ + \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\ + \> \textbf{else} \textbf{return} $0$; + \end{program} + & + \begin{program} + \quad \= \quad \= \kill + Experiment $\expt{uni-no}{A}(\mathcal{G})$ \\ + \> $\alpha, \tau \rgets \mathbb{Z}/q\mathbb{Z}$; \\ + \> $R \gets A(g^\alpha, g^\tau)$; \\ + \> \textbf{if} $R = g^{\alpha\tau}$ \textbf{then} \textbf{return} $1$; \\ + \> \textbf{else} \textbf{return} $0$; + \end{program} +\end{tabular} +We mandate that the adversary $A_{\text{cca}}$ never query its authentication +oracle with the test challenge $g^\tau$. + +We will consider a function $\oracle{H}$ to be suitable for our purposes if +for any adversary $A_{\text{cca}}$, there is an adversary $A$ for which the +distributions of $\expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G})$ +and $\expt{uni-no}{A}(\mathcal{G})$ are computationally indistinguishable. +Intuitively, this means that the authentication oracle isn't useful in +attacking the protocol: any adversary which has access to an oracle can be +replaced by one which has approximately the same probability of success but +without oracle access. + +We first prove that a random oracle \cite{Bellare:1993:ROP} makes a +`suitable' function. + +\begin{theorem} + If $\oracle{H}$ is a random oracle with $L$-bit output, where $L$ is some + polynomial function of the length of $q$, then, for any adversary + $A_{\text{cca}}$, there exists an adversary $A$ such that + \[ \expt{uni-cca}{A_{\text{cca}}, \oracle{H}}(\mathcal{G}) + \compind \expt{uni-no}{A}(\mathcal{G}) \] +\end{theorem} +\begin{proof} + The idea behind the proof is that we construct an adversary $A$ in terms of + the given adversary $A_{\text{cca}}$ with the same output in all but + negligibly few cases. + + Our adversary $A$ isn't provided with either oracle supplied to + $A_{\text{cca}}$. + + Simulating the random oracle is easy. $A$ maintains a table, initially + empty, of pairs $(q, r)$. When the oracle is invoked on input $q$, we look + it up in the table: if there is some entry $(q, r)$, it returns $r$; + otherwise we toss coins to choose a new output $r$ and add $(q, r)$ to the + table. This is obviously a polynomial-time activity, since + $A_{\text{cca}}$ makes only polynomially many queries, and answering each + one takes polynomial time. + + The authentication oracle is a little harder. Suppose $A_{\text{cca}}$ + makes a query $(x, h)$. If there is an entry $(q, h)$ in the random oracle + table, the authentication oracle returns $q$; otherwise it returns $\bot$. + + It remains to show that this is a valid thing to do. +\end{proof} + + + + + + + + + + + + %%%-------------------------------------------------------------------------- -- [mdw]