Initial versions of documentation.

[tripe] / doc / wrestlers.tex

%%% -*-latex-*-
%%%
%%% $Id: wrestlers.tex,v 1.1 2001/02/16 21:43:33 mdw Exp $
%%%
%%% Description of the Wrestlers Protocol
%%%
%%% (c) 2001 Mark Wooding
%%%

%%%----- Revision history ---------------------------------------------------
%%%
%%% $Log: wrestlers.tex,v $
%%% Revision 1.1  2001/02/16 21:43:33  mdw
%%% Initial versions of documentation.
%%%

\documentclass{article}
\usepackage{amssymb}
\title{The Wrestlers Protocol}
\author{Mark Wooding \\ Clive Jones}
\def\from{\leftarrow}

\begin{document}

\maketitle

\begin{abstract}
  We present a simple key-exchange protocol with of mutual authentication and
  perfect forward-secrecy, which doesn't leave any long-lasting evidence of
  participation in the exchange.  The protocol's security depends on the
  intractability of the Diffie-Hellman problem (in some cyclic group), and on
  the strength of a hash function.
\end{abstract}

\section{Introduction}

Current key-agreement protocols are all very well for securing generally
`honest' traffic (e.g., transmission of credit-card details to a merchant),
but they're less satisfactory if you actually have something to hide.

In the UK, new key exchange protocols have been particularly motivated by the
new Regulation of Investigatory Powers Act, which allows `authorized persons'
to intercept communications and demand long-term encryption keys.

Let's suppose that Alice and Bob are shady characters, and that their
communications are of great interest to the draconian r\'egime in which they
live.  (They might be international arms smugglers, for example, because they
export cryptographic toolkits.)

Alice could just invent a session key and transmit it to Bob, encrypted under
his public key, each time she wanted to talk to him.  However, once the
secret police turn up at Bob's house and demand his private key, the game is
over and all of the communications can be recovered.

Alice and Bob would clearly be better off using a system which offers forward
secrecy, for example, Diffie-Hellman.  However, in order to prevent active
attacks, the messages in the Diffie-Hellman exchange must be authenticated.
The way this usually works is that Alice and Bob pick a group $G$ of order
$q$ generated by $g$.  When Alice and Bob want to communicate, they choose
exponents $\alpha$ and $\beta$ respectively ($1 < \alpha, \beta < q$), Alice
sends $S_A(g^\alpha)$ to Bob, Bob sends $S_B(g^\beta)$ to Alice, and, after
verifying each other's signatures, they each compute a shared key $K =
g^{\alpha \beta}$.  They dispose of their secrets $\alpha$ and $\beta$
forthwith, and destroy $K$ when the conversation finishes.  Now the secret
police can demand all they like: they still can't decrypt old sessions, and
Alice and Bob, however badly tortured, can't help them.  The secret police
might not even be all owed to demand their long-term signing keys: for
example, the RIPA grants special protection to authentication-only keys.

This is fine, except that sending $S_A(g^\alpha)$ is a wonderful way of
shouting `Alice was here' to all of the spooks tapping Bob's network
connection.  The Wrestlers Protocol\footnote{%
  Named after the excellent pub in Cambridge where most of the design was
  done.}
fixes these problems.  It provides perfect forward secrecy, just like
Diffie-Hellman, without leaving signatures around for the spooks.


\section{A simple authentication protocol}

As a building-block, we construct a simple authentication protocol based on
Diffie-Hellman key exchange.  As before, let's use a group $G$ of order $q$
(for some prime $q$), generated by a group element $g$.

A Diffie-Hellman key exchange allows two parties to compute the same value,
with different knowledge.  We'll use this to make an authentication protocol.

Alice chooses a private key $1 < a < q$.  Her public key is $A = g^a$.  She
can prove her knowledge of $a$ to Bob like this:
\begin{enumerate}
\item Bob makes up a random $1 < \beta < q$.  He sends a challenge $C =
  g^\beta$ to Alice.
\item Alice computes the response $R = C^a = g^{a \beta}$.  This would
  be the shared key if we were doing proper Diffie-Hellman, but we aren't.
  Instead, she just sends $R$ back to Bob.
\item Bob checks that $R = A^\beta$.  If it is, he accepts that the person
  he's talking to has Alice's private key, and hence is presumably Alice.
\end{enumerate}

This protocol has nice properties.  It's not terribly difficult to implement,
given the usual tools like modular exponentiation or elliptic curve
point-addition.

An eavesdropper -- let's call her Eve, for tradition's sake -- doesn't learn
anything terribly interesting from watching the exchange.  She sees $C$ going
one way and then $C^a$ coming back.  If she finds this illuminating, she can
program her computer to generate random numbers $\gamma$ and show her pairs
$C = g^\gamma$ and $R = A^\gamma = C^a$.  So Eve learns nothing useful she
couldn't have worked out for herself.  In fact, she doesn't even learn that
Alice is involved in the conversation!  Bob can fake up an authentication
with Alice by secretly agreeing which value of $\beta$ he's going to use with
an accomplice.

Bob's in a better position than Eve.  If he computes his challenges honestly
then he doesn't learn much except that he's talking to Alice, because as
we've seen, she only tells him $R$, which he knew already.  However, if Bob
carefully chooses a challenge $C$ without knowing its discrete log $\beta$,
then Alice's response might tell him useful information about her private
key that he couldn't have worked out just by sitting at home computing
discrete logs.

We can fix this little problem easily enough if we make Bob transmit a hash
of his expected answer.  Let $H \colon \mathbb{Z} \to \{\,0, 1\,\}^n$ be a
hash function.  The property we require from $H$ is that Bob can't compute
$H(g^{a \beta})$ given only $C = g^\beta$ and $A = g^a$ with more than
negligible probability; a random function would fit the bill fine.  This
does, of course, also assume that the Diffie-Hellman problem is difficult.
The new protocol looks very much like the old one:
\begin{enumerate}
\item Bob chooses a random $1 < \beta < q$.  He computes $C = g^\beta$ and $R
  = A^\beta$, and sends $C, H(R)$ to Alice.
\item Alice computes $R' = C^a$ and checks that it matches the hash which Bob
  sent.  If it doesn't, he's trying to cheat, and she should refuse to
  answer.  Otherwise, she sends her response $R'$ back to Bob.
\item Bob checks that Alice's reply matches the one he computed back in step
  1.  If it does, he knows that he's talking to Alice.
\end{enumerate}


\section{The Wrestlers Protocol}

We observe a useful side-effect of the authentication protocol just
described: Bob should be convinved that Alice received his challenge $C$
correctly.  The idea of the Wrestlers Protocol is to use this to construct a
full Diffie-Hellman key exchange with mutual authentication.  We maintain the
useful properties of the previous protocol.

Before they can use the protocol, Alice and Bob must agree on a group $G$ as
before.  Alice chooses a private key $1 < a < q$, and publishes her public
key $A = g^a$; Bob similarly chooses a private key $1 < b < q$ and publishes
his public key $B = g^b$.

Here's the actual protocol in summary:
\begin{enumerate}
\item $A \to   B$:\quad $g^\alpha$
\item $A \from B$:\quad $g^\beta$, $H(g^\alpha, g^\beta, g^{a \beta})$
\item $A \to   B$:\quad $g^{a \beta}$, $H(g^\beta, g^\alpha, g^{\alpha b})$
\item $A \from B$:\quad $g^{\alpha b}$
\end{enumerate}

And now in detail:
\begin{enumerate}

\item Alice invents a temporary secret $1 < \alpha < q$.  She computes her
  challenge $C_A = g^\alpha$, and sends it to Bob.
  
\item Bob receives the $C_A$, and stores it away.  He invents a temporary
  secret $1 < \beta < q$ of his own, and computes both his challenge $C_B =
  g^\beta$ and the expected response $R_B = A^\beta = g^{a \beta}$.  He
  hashes both challenges (hers first) and the expected response $R_B$, and
  sends his challenge and the hash back to Alice.
  
\item Alice reads Bob's challenge.  She computes her response $R_B' = C_B^a =
  g^{a \beta}$ and ensures that the Bob's hash is correct.  If it isn't, she
  stops talking to Bob.  If the hash matches, she sends back her response,
  together with a hash of Bob's challenge, her original challenge from step
  1, and her expected response $R_A = B^\alpha = g^{\alpha b}$.

\item Bob reads Alice's response.  If it's wrong then he stops talking.
  Otherwise he computes his response to Alice's challenge $R_A' = C_A^b =
  g^{\alpha b}$ and checks Alice's hash.  If the hash is wrong, he also stops
  talking.  Otherwise he sends the response back to Alice.

\end{enumerate}
Finally, Alice checks Bob's response, stopping the conversation if it's
wrong.  Then both sides compute their shared key $K = C_A^\beta = C_B^\alpha
= g^{\alpha \beta}$, and discard their temporary secrets.

The protocol is essentially symmetrical: each side sends and receives both a
challenge and hash pair, and a response, but it doesn't look that simple
because the hashes include both sides' challenges.  Looking at it from one
side at a time will make things clearer, so let's just take Alice's point of
view.

Alice constructs her challenge in step 1, and sends it off.  She receives a
challenge and hash in step 2.  When she computes the response to the
challenge, she verifies the hash she received.  If it matches, she knows that
\begin{itemize}
\item whoever she's talking to hasn't attempted to cheat her by sending a
  challenge for which he doesn't know the answer; and
\item he has successfully received her challenge.
\end{itemize}
Because she's now received a challenge, she can work out her hash.  She sends
off her response to the challenge, together with the hash, and awaits the
response.

In step 4, the response arrives.  If it's correct, she knows that it's from
Bob, and that he (Bob) received her challenge OK.  Tying everything else
together is the tricky bit.

If we assume that Bob is playing by the rules, the fact that he's sent his
response means that he verified it against Alice's hash and decided that
\begin{itemize}
\item Alice wasn't trying to cheat him and find out about his private key;
  and 
\item Alice correctly received his challenge.
\end{itemize}
Because Bob wouldn't have replied if these weren't true, Alice can therefore
believe that she has received Bob's challenge correctly.

To summarize: Alice has managed to get a challenge to Bob, and he responded;
Alice has also received Bob's challenge correctly.

What if Bob isn't honest?  The only hole in the protocol which can be
exploited by Bob is that he can send a response \emph{even though} it doesn't
match Alice's hash.  This means that the protocol will continue even if Alice
is attempting to cheat Bob and find information about his private key: this
is a penalty Bob has to pay for not following the rules.  The protocol still
aborts if an adversary interferes with the challenges: if Alice isn't given
Bob's challenge accurately, her response will be wrong, and Bob can abort the
exchange; similarly, if Bob isn't given Alice's challenge, she will detect
this and abort the exchange.


\section{Conclusions and further work}

We have presented a new key exchange protocol based upon a novel use of
Diffie-Hellman key exchange as a means of authentication.

The arguments given in the previous section sound fairly convincing, but they
don't provide a formal proof of the security of the Wrestlers Protocol.  The
authors are unaware of a logic system for verifying protocols which correctly
capture the properties of hash functions.

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

\end{document}

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