From 90d03a8531584ba5467d13f28737e36d4afac658 Mon Sep 17 00:00:00 2001
From: mdw
Date: Fri, 22 Jun 2001 19:41:31 +0000
Subject: [PATCH] Restart with different structure and rather more formal
objectives.
Organization: Straylight/Edgeware

doc/wrestlers.tex  266 +++++++++++
1 file changed, 53 insertions(+), 213 deletions()
diff git a/doc/wrestlers.tex b/doc/wrestlers.tex
index 600b2fd..033f9fe 100644
 a/doc/wrestlers.tex
+++ b/doc/wrestlers.tex
@@ 1,6 +1,6 @@
%%% *latex*
%%%
%%% $Id: wrestlers.tex,v 1.2 2001/02/22 09:09:05 mdw Exp $
+%%% $Id: wrestlers.tex,v 1.3 2001/06/22 19:41:31 mdw Exp $
%%%
%%% Description of the Wrestlers Protocol
%%%
@@ 10,6 +10,9 @@
%%% Revision history 
%%%
%%% $Log: wrestlers.tex,v $
+%%% 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.
%%%
@@ 19,237 +22,74 @@
\documentclass{article}
\usepackage{amssymb}
\title{The Wrestlers Protocol}
\author{Mark Wooding \\ Clive Jones}
\def\from{\leftarrow}
+\usepackage{amstext}
\begin{document}
+\errorcontextlines=999
+\makeatletter
\maketitle
+\title{The Wrestlers Protocol: proofofreceipt and secure key exchange}
+\author{Mark Wooding \and Clive Jones}
\begin{abstract}
 We present a simple keyexchange protocol with of mutual authentication and
 perfect forwardsecrecy, which doesn't leave any longlasting evidence of
 participation in the exchange. The protocol's security depends on the
 intractability of the DiffieHellman problem (in some cyclic group), and on
 the strength of a hash function.
\end{abstract}
+\bibliographystyle{alpha}
\section{Introduction}

Current keyagreement protocols are all very well for securing generally
`honest' traffic (e.g., transmission of creditcard details to a merchant),
but they're less satisfactory if you actually have something to hide.
+\newtheorem{theorem}{Theorem}
+\newenvironment{proof}[1][Proof]{%
+ \par\noindent\textbf{#1.} %
+}{%
+ \penalty\@M\hfill\vadjust{}%
+ \penalty\z@\relax\vadjust{}%
+ \penalty\@M\hfill$\square$%
+ \par%
+}
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 longterm 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.)
+\begin{document}
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.
+\maketitle
+\begin{abstract}
+ Fill this in later.
+\end{abstract}
+\tableofcontents
+\newpage
Alice and Bob would clearly be better off using a system which offers forward
secrecy, for example, DiffieHellman. However, in order to prevent active
attacks, the messages in the DiffieHellman 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 longterm signing keys: for
example, the RIPA grants special protection to authenticationonly 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
DiffieHellman, without leaving signatures around for the spooks.
+\section{Introduction}
+% Some waffle here about the desirability of a keyexchange 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 DiffieHellmanbased authenticator, and prove that an
+% authentication oracle is useless if the hash function has appropriate
+% properties.
As a buildingblock, we construct a simple authentication protocol based on
DiffieHellman key exchange. As before, let's use a group $G$ of order $q$
(for some prime $q$), generated by a group element $g$.

A DiffieHellman 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 DiffieHellman, 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
pointaddition.

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 DiffieHellman 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{A key exchange protocol}

We observe a useful sideeffect 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 DiffieHellman 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{Practical considerations}
+Suppose that $G$ is some cyclic group of order $q$, generated by an element
+$g$, in which the decision DiffieHellman 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.
+%%%
\section{Conclusions and further work}
+\section{An MTauthenticator}
+% Use the protocol of the previous section as an MTauthenticator, within the
+% meaning of [Canetti:2001:AKE].
We have presented a new key exchange protocol based upon a novel use of
DiffieHellman 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.
+\section{A keyexchange 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 SKsecure.
%%% That's all, folks 
+\bibliography{cryptography,mdwcrypto}
\end{document}
%%% Local Variables:

2.1.4