Rearrange so as not to include Linux headers unless we need to.

[tripe] / doc / wrestlers.tex

%%% -*-latex-*-
%%%
%%% $Id: wrestlers.tex,v 1.5 2002/01/13 14:55:31 mdw Exp $
%%%
%%% Description of the Wrestlers Protocol
%%%
%%% (c) 2001 Mark Wooding
%%%

%%%----- Revision history ---------------------------------------------------
%%%
%%% $Log: wrestlers.tex,v $
%%% Revision 1.5  2002/01/13 14:55:31  mdw
%%% More incomplete stuff.
%%%
%%% 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.
%%%
%%% Revision 1.2  2001/02/22 09:09:05  mdw
%%% Partially through reworking.
%%%
%%% Revision 1.1  2001/02/16 21:43:33  mdw
%%% Initial versions of documentation.
%%%

\newif\iffancystyle\fancystylefalse

\iffancystyle
  \documentclass
    [a4paper, article, 10pt, numbering, noherefloats, notitlepage]
    {strayman}
  \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
  \usepackage[margin]{amsthm}
\else
  \documentclass[a4paper]{article}
  \usepackage{a4wide}
  \usepackage{amsthm}
\fi

\usepackage{amssymb, amstext}
\usepackage{mdwtab, mathenv}

\errorcontextlines=999
\showboxbreadth=999
\showboxdepth=999
\makeatletter

\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
\author{Mark Wooding \and Clive Jones}

\bibliographystyle{alpha}

\newtheorem{theorem}{Theorem}
\renewcommand{\qedsymbol}{$\square$}

\newcommand{\getsr}{\stackrel{\scriptscriptstyle R}{\gets}}
\newcommand{\inr}{\in_{\scriptscriptstyle R}}
\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}[1]{\mathop{\operator@font poly}({#1})}
\newcommand{\negl}[1]{\mathop{\operator@font negl}({#1})}
\newcommand{\compind}{\stackrel{c}{\approx}}

\newcolumntype{G}{p{0pt}}

\newcommand{\xor}{\oplus}
\renewcommand{\epsilon}{\varepsilon}

\newenvironment{program}
  {\begin{tabular}[C]{|G|}\hlx{hv[][\tabcolsep]}\begin{tabbing}}
  {\end{tabbing}\\\hlx{v[][\tabcolsep]h}\end{tabular}}

\begin{document}

\maketitle
\begin{abstract}
  Fill this in later.
\end{abstract}
\tableofcontents
\newpage

%%%--------------------------------------------------------------------------

\section{Introduction}
% Some waffle here about the desirability of a key-exchange protocol that
% doesn't leave signatures lying around, followed by an extended report of
% the various results.

%%%--------------------------------------------------------------------------

\section{A simple authentication protocol}
% Present the basic Diffie-Hellman-based authenticator, and prove that an
% authentication oracle is useless if the hash function has appropriate
% properties.

We begin 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}

We start by selecting a security parameter $k$.  We choose a cyclic group $G
= \langle g \rangle$ with $q = |G|$ prime, in which the decision
Diffie-Hellman problem is assumed to be hard \cite{Boneh:1998:DDP}; we
require that $q$ is a $k$-bit number.  Suitable groups include elliptic
curves over finite fields and prime-order subgroups of prime fields.
Throughout, we shall write the group operation as multiplication, and we
shall assume that group elements are interchangeable with their binary
representations.

Alice can choose a private key $\alpha$ from the set $\{ 1, 2, \ldots, q - 1
\}$ 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 $\beta$, also from $\{ 1, 2, \ldots, q -
  1 \}$, and sends a \emph{challenge} $b = g^\beta$ to Alice.
\item Alice computes her \emph{response} $b^\alpha$ and returns it to Bob.
\item If Alice's response is equal to $a^\beta$ then Bob is satisfied.
\end{enumerate}
If Bob always plays by the rules then this protocol is evidently secure,
since 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 the protocol by requiring that Bob prove that he already knows the
answer to his challenge.  We introduce a hash function $h$ whose properties
we shall investigate later.  The \emph{Wrestlers Authentication Protocol} is
then:
\begin{enumerate}
\item Bob chooses a secret $\beta \getsr \{ 1, 2, \ldots, q - 1 \}$.  He
  computes his \emph{challenge} $b \gets g^\beta$ and also a \emph{check
    value} $c \gets \beta \xor h(a^\beta)$.  He sends the pair $(b, c)$.
\item Alice receives $(b', c')$.  She computes $r \gets b'^\alpha$ and
  $\gamma \gets c' \xor h(R)$.  If $b' = g^\gamma$, she sends $r$ back as her
  \emph{response}; otherwise she sends the distinguished value $\bot$.
\item Bob receives $r'$.  If $r' = a^\beta$ then he accepts that he's talking
  to Alice.
\end{enumerate}
We show that the introduction of the check value has indeed patched up the
weakness described above, and that the check value itself hasn't made an
impersonator's job much easier.

\subsection{Analysis in the random oracle model}

Here, we prove that the Wrestlers Authentication Protocol is secure if $h$ is
implemented by a public \emph{random oracle} \cite{Bellare:1993:ROP}.

Fix a private key $\alpha \inr \{ 1, 2, \ldots, q - 1\}$ and the corresponding public
key $a = g^\alpha$, and consider a probabilistic polynomial-time adversary
$A$, equipped with two oracles.  One is a random oracle $\oracle{H}\colon
\{0, 1\}^* \to \{0, 1\}^k$, which implements a function $h$ randomly selected
from the set of all functions with that signature; the other is an
authentication oracle $\oracle{O}\colon G \times \{0, 1\}^k \to G \cup \{
\bot \}$ defined by:
\[
\oracle{O}^(b, c) = \begin{cases}
  b^\alpha & if $b = g^{c \xor h(b^\alpha)}$ \\
  \bot     & otherwise
\end{cases}
\]
The authentication oracle will play the part of Alice in the following.  We
first show that access to this authentication oracle can't help an adversary
learn how to impersonate Alice.

\begin{theorem}
  The Wrestlers Authentication Protocol with random oracle is computational
  zero knowledge \cite{Brassard:1989:SZK}.
  \label{thm:wap-czk}
\end{theorem}
\begin{proof}
  \newcommand{\Hlist}{\textit{$\oracle{H}$-list}}
  \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}}
  \newcommand{\Osim}{\textit{$\oracle{O}$-sim}}
  \renewcommand{\H}{\oracle{H}}
  \renewcommand{\O}{\oracle{O}}
  %
  Let $A$ be any probabilistic polynomial-time adversary with access to a
  random.  We shall construct a probabilistic polynomial-time adversary $A'$
  without either oracle such that the probability distributions on the output
  of $A$ and $A'$ are equal.  Specifically, $A'$ runs $A$ with simulated
  random and authentication oracles whose behaviour is computationally
  indistinguishable from the originals.  The algorithm for $A'$ and the
  simulated oracles is shown in figure~\ref{fig:wap-czk-sim}.

  \begin{figure}
    \begin{program}
      \quad \= \kill
      Adversary $A'^{\H(\cdot)}$: \+ \\
        $\Hlist \gets \emptyset$; \\
        $r \gets A^{\Hsim(\cdot), \Osim(\cdot, \cdot)}$; \\
        \textbf{return} $r$; \- \\[\medskipamount]
      %
      Simulated random oracle $\Hsim(q)$: \+ \\
        \textbf{if} $\exists r : (q, r) \in \Hlist$ \textbf{then}
          \textbf{return} $r$; \\
        $r \getsr \H(q)$; \\
        $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
        \textbf{return} $r$; \- \\[\medskipamount]
      %
      Simulated authentication oracle $\Osim(b, c)$: \+ \\
        \textbf{if} $\exists q, r : (q, r) \in \Hlist \wedge
                                    b = g^{c \xor r} \wedge
                                    q = a^{c \xor r}$ \textbf{then}
          \textbf{return} $a^{c \xor r}$; \\
        \textbf{else} \textbf{return} $\bot$;
    \end{program}
    %
    \caption{The algorithm and simulated oracles for the proof of
        theorem~\ref{thm:wap-czk}.}
    \label{fig:wap-czk-sim}
  \end{figure}
  
  Firstly we show that $A'$ runs in polynomial time.  The only modifications
  to $\Hlist$ are in $\Hsim$, which adds at most one element for each oracle
  query.  Since $\Hlist$ is initially empty and $A$ can only make $\poly{k}$
  queries to $\Hsim$, this implies that $|\Hlist|$ is always
  polynomially-bounded.  Each query can be answered in polynomial time:
  indeed, the search implied by the test $\exists r : (q, r) \in \Hlist$ can
  be performed in $O(\log q)$ time by indexing $\Hlist$ on $q$ using a radix
  tree.  Now, since $|\Hlist|$ is polynomially bounded, the test $\exists q,
  r : (q, r) \in \Hlist \wedge b = g^{c \xor r} \wedge q = a^{c \xor r}$ at
  the start of $\Osim$ runs in polynomial time even though it requires an
  exhaustive search of the history of $A$'s queries to its simulated random
  oracle.
  
  Next, we examine the behaviour of the simulated oracles.  Since $\Hsim$ is
  implemented in terms of the public random oracle $\H$, and returns the same
  answers to queries, its probability distribution must be identical.
  
  We turn our attention to the simulation of the authentication oracle.
  Consider a query $(b, c)$ made by $A$ to its authentication oracle.
  
  Firstly, suppose that there is a $\beta$ such that $b = g^\beta$ and $c =
  \beta \xor r$ where $r$ is the response to a previous query made by $A$ to
  its random oracle on $a^\beta$.  Then the true authentication oracle $\O$
  is satisfied because $b = g^\beta = g^{c \xor r} = g^{c \xor h(a^\beta)} =
  g^{c \xor h(b^\alpha)}$, and returns $b^\alpha$.  Similarly, the simulated
  authentication oracle $\Osim$ will find the pair $(a^\beta, r) \in \Hlist$,
  recover $\beta = c \xor r$, confirm that $b = g^\beta$, and return
  $a^\beta$ as required.  These events all occur with probability 1.

  Conversely, suppose that there is no such $\beta$.  Then the simulated
  oracle $\Osim$ will reject the query, returning $\bot$, again with
  probability 1.  However, a genuine authentication oracle $\O$ will succeed
  and return $b^\alpha$ with probability $2^{-k}$.  To see this, note that $b
  = g^\gamma$ for some $\gamma \in \{ 0, 1, \ldots, q - 1 \}$, and the
  probability that $h(b^\alpha) = c \xor \gamma$ is precisely $2^{-k}$, since
  $c$ and $\gamma$ are $k$-bit strings.  Since this probability is
  negligible, we have shown that the distributions of the simulated oracles
  $\Hsim$ and $\Osim$ are computationally indistinguishable from the genuine
  oracles $\H$ and $\O$.  The theorem follows.
\end{proof}

Our next objective is to show that pretending to be Alice is hard without
knowledge of her secret $\alpha$.  We say that an adversary $A$
\emph{impersonates} in the Wrestlers Authentication Protocol with probability
$\epsilon$ if
\[ \Pr[A^{\oracle{H}(\cdot)}(g^\alpha, g^\beta,
                             \beta \xor h(g^{\alpha\beta}))
         = g^{\alpha\beta}]
     = \epsilon
\]
where the probability is taken over all choices of $\alpha, \beta \in \{ 1,
2, \ldots, q - 1 \}$ and random oracles $\oracle{H}$.

\begin{theorem}
  Assuming that the Diffie-Hellman problem is hard in $G$, no probabilistic
  polynomial-time adversary can impersonate in the Wrestlers Authentication
  Protocol with random oracle with better than negligible probability.
  \label{thm:wap-dhp}
\end{theorem}
\begin{proof}
  \newcommand{\Hlist}{\textit{$\oracle{H}$-list}}
  \newcommand{\Hqueries}{\textit{$\oracle{H}$-queries}}
  \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}}
  \renewcommand{\H}{\oracle{H}}
  %
  We prove the theorem by contradiction.  Given a polynomial-time adversary
  $A$ which impersonates Alice with non-negligible probability $\epsilon$, we
  construct an adversary which solves the Diffie-Hellman problem with
  probability no less than $\epsilon \poly{k}$, i.e.,
  \[ \Pr[A'(g^\alpha, g^\beta) = g^{\alpha\beta}] \ge \epsilon \poly{k}. \]
  Thus, if there is any polynomial-time $A$ which impersonates with better
  than negligible probability, then there is a polynomial-time $A'$ which
  solves Diffie-Hellman with essentially the same probability, which would
  violate our assumption of the hardness of Diffie-Hellman.

  The idea behind the proof is that the check value is only useful to $A$
  once it has discovered the correct response to the challenge, which it must
  have done by solving the Diffie-Hellman problem.  Hence, our Diffie-Hellman

  \begin{figure}
    \begin{program}
      \quad \= \kill
      Adversary $A'(a, b)$: \+ \\
        $\Hlist \gets \emptyset$; \\
        $\Hqueries \gets \emptyset$; \\
        $r \getsr \{ 0, 1 \}^k$; \\
        $x \gets A^{\Hsim(\cdot)}(a, b, r)$; \\
        $c \getsr (\Hlist \cup \{ x \}) \cap G$; \\
        \textbf{return} $c$; \- \\[\medskipamount]
      %
      Simulated random oracle $\Hsim(q)$: \+ \\
        \textbf{if} $\exists r : (q, r) \in \Hlist$
          \textbf{then} \textbf{return} $r$; \\
        $r \gets \{ 0, 1 \}^k$; \\
        $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
        $\Hqueries \gets \Hqueries \cup \{ q \}$; \\
        \textbf{return} $r$;
    \end{program}
    %
    \caption{The algorithm for the proof of theorem~\ref{thm:wap-dhp}}
    \label{fig:wap-dhp-rdc}
  \end{figure}

  The adversary $A'$ is shown in figure~\ref{fig:wap-dhp-rdc}.  It generates
  a random check-value and runs the impersonator $A$.
  
  The simulated random oracle $\Hsim$ gathers together the results of all of
  the random oracle queries made by $A$.  The final result returned by $A'$
  is randomly chosen from among all of the `plausible' random oracle queries
  and $A$'s output, i.e., those queries which are actually members of the
  group.  The check value given to $A$ is most likely incorrect (with
  probability $1 - 2^{-k}$): the intuition is that $A$ can only notice if it
  actually computes the right answer and then checks explicitly.

  If $A$ does compute the correct answer $g^{\alpha\beta}$ and either returns
  it or queries $\Hsim$ on it, then $A'$ succeeds with probability $\epsilon
  / |(\Hlist \cup \{ x \}) \cap G| = \epsilon \poly{k}$, since $|\Hlist|$ is
  no greater than the number of random oracle queries made by $A$ (which must
  be polynomially bounded).\footnote{%
    This polynomial factor introduces a loss in the perceived security of the
    authentication protocol.  It appears that this loss is only caused by the
    possibility of the adversary $A$ being deliberately awkward and checking
    the value of $c$ after having computed the answer.  However, we can't see
    a way to improve the security bound on the scheme without imposing
    artificial requirements on $A$.} %
  
  It remains to show that if $A$ never queries its random oracle on
  $g^{\alpha\beta}$ then it cannot distinguish the random check value $r$
  from the correct one $\beta \xor \H(g^{\alpha\beta})$, and hence won't
  notice that $A'$ is lying to it.  But this is obvious: $A$'s probability of
  guessing the random value that would have been returned had it actually
  queried $\Hsim$ on the input $g^{\alpha\beta}$ is equal to the probability
  of it guessing $\beta \xor r$ instead, since $\Hsim$ chooses its responses
  uniformly at random.  This completes the proof.
\end{proof}

We conclude here that the Wrestlers Authentication Protocol is a secure
authentication protocol in the random oracle model: impersonation is hard if
the Diffie-Hellman problem is hard, and proving one's identity doesn't leak
secret key information.

\subsection{Requirements on hash functions}

Having seen that the Wrestlers Authentication Protocol is secure in the
random oracle model, we now ask which properties we require from the hash
function.  This at least demonstrates that the protocol isn't deeply flawed,
and suggests an efficient implementation in terms of conventional hash
functions.

Here we investigate more carefully the properties required of the hash
function, and provide a more quantitative analysis of the protocol.

Looking at the proofs of the previous two sections, we see that the random
oracles are mainly a device which allow our constructions to `grab hold' of
the hashing operations performed by the adversary.

%%%--------------------------------------------------------------------------

\section{A key-exchange protocol}
% Present the Wrestlers protocol in all its glory.  Show, by means of the
% previous proofs, that the Wrestlers protocol is simulatable in the
% authenticated model using a much simpler protocol.  Show that the simpler
% protocol is SK-secure.


% messages
%
% pre-challenge: g^b
% cookie: g^b, h(cookie, g^b')
% challenge: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab')
% reply: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab'), E_k(g^a'b)
% switch: h(g^b), h(g^b'), E_k(g^a'b, h(switch-request, g^a, g^a'))
% switch-ok: E_k(g^ab, h(switch-confirm, g^a, g^a'))begin{


We now describe the full Wrestlers Protocol, in a multi-party setting.  Fix a
cyclic group $G = \langle g \rangle$ of order $q = |G|$.  Each player $P_i$
chooses a private key $\alpha_i \in \{ 1, 2, \ldots, q - 1 \}$ and publishes
the corresponding public key $a_i = g^{\alpha_i}$ to the other players.




%%%----- That's all, folks --------------------------------------------------

\bibliography{cryptography,mdw-crypto}
\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "wrestlers"
%%% End: