chiark / gitweb /
Initial versions of documentation.
[tripe] / doc / wrestlers.tex
74eb47db 1%%% -*-latex-*-
3%%% $Id: wrestlers.tex,v 1.1 2001/02/16 21:43:33 mdw Exp $
5%%% Description of the Wrestlers Protocol
7%%% (c) 2001 Mark Wooding
10%%%----- Revision history ---------------------------------------------------
12%%% $Log: wrestlers.tex,v $
13%%% Revision 1.1 2001/02/16 21:43:33 mdw
14%%% Initial versions of documentation.
19\title{The Wrestlers Protocol}
20\author{Mark Wooding \\ Clive Jones}
28 We present a simple key-exchange protocol with of mutual authentication and
29 perfect forward-secrecy, which doesn't leave any long-lasting evidence of
30 participation in the exchange. The protocol's security depends on the
31 intractability of the Diffie-Hellman problem (in some cyclic group), and on
32 the strength of a hash function.
37Current key-agreement protocols are all very well for securing generally
38`honest' traffic (e.g., transmission of credit-card details to a merchant),
39but they're less satisfactory if you actually have something to hide.
41In the UK, new key exchange protocols have been particularly motivated by the
42new Regulation of Investigatory Powers Act, which allows `authorized persons'
43to intercept communications and demand long-term encryption keys.
45Let's suppose that Alice and Bob are shady characters, and that their
46communications are of great interest to the draconian r\'egime in which they
47live. (They might be international arms smugglers, for example, because they
48export cryptographic toolkits.)
50Alice could just invent a session key and transmit it to Bob, encrypted under
51his public key, each time she wanted to talk to him. However, once the
52secret police turn up at Bob's house and demand his private key, the game is
53over and all of the communications can be recovered.
55Alice and Bob would clearly be better off using a system which offers forward
56secrecy, for example, Diffie-Hellman. However, in order to prevent active
57attacks, the messages in the Diffie-Hellman exchange must be authenticated.
58The way this usually works is that Alice and Bob pick a group $G$ of order
59$q$ generated by $g$. When Alice and Bob want to communicate, they choose
60exponents $\alpha$ and $\beta$ respectively ($1 < \alpha, \beta < q$), Alice
61sends $S_A(g^\alpha)$ to Bob, Bob sends $S_B(g^\beta)$ to Alice, and, after
62verifying each other's signatures, they each compute a shared key $K =
63g^{\alpha \beta}$. They dispose of their secrets $\alpha$ and $\beta$
64forthwith, and destroy $K$ when the conversation finishes. Now the secret
65police can demand all they like: they still can't decrypt old sessions, and
66Alice and Bob, however badly tortured, can't help them. The secret police
67might not even be all owed to demand their long-term signing keys: for
68example, the RIPA grants special protection to authentication-only keys.
70This is fine, except that sending $S_A(g^\alpha)$ is a wonderful way of
71shouting `Alice was here' to all of the spooks tapping Bob's network
72connection. The Wrestlers Protocol\footnote{%
73 Named after the excellent pub in Cambridge where most of the design was
74 done.}
75fixes these problems. It provides perfect forward secrecy, just like
76Diffie-Hellman, without leaving signatures around for the spooks.
79\section{A simple authentication protocol}
81As a building-block, we construct a simple authentication protocol based on
82Diffie-Hellman key exchange. As before, let's use a group $G$ of order $q$
83(for some prime $q$), generated by a group element $g$.
85A Diffie-Hellman key exchange allows two parties to compute the same value,
86with different knowledge. We'll use this to make an authentication protocol.
88Alice chooses a private key $1 < a < q$. Her public key is $A = g^a$. She
89can prove her knowledge of $a$ to Bob like this:
91\item Bob makes up a random $1 < \beta < q$. He sends a challenge $C =
92 g^\beta$ to Alice.
93\item Alice computes the response $R = C^a = g^{a \beta}$. This would
94 be the shared key if we were doing proper Diffie-Hellman, but we aren't.
95 Instead, she just sends $R$ back to Bob.
96\item Bob checks that $R = A^\beta$. If it is, he accepts that the person
97 he's talking to has Alice's private key, and hence is presumably Alice.
100This protocol has nice properties. It's not terribly difficult to implement,
101given the usual tools like modular exponentiation or elliptic curve
104An eavesdropper -- let's call her Eve, for tradition's sake -- doesn't learn
105anything terribly interesting from watching the exchange. She sees $C$ going
106one way and then $C^a$ coming back. If she finds this illuminating, she can
107program her computer to generate random numbers $\gamma$ and show her pairs
108$C = g^\gamma$ and $R = A^\gamma = C^a$. So Eve learns nothing useful she
109couldn't have worked out for herself. In fact, she doesn't even learn that
110Alice is involved in the conversation! Bob can fake up an authentication
111with Alice by secretly agreeing which value of $\beta$ he's going to use with
112an accomplice.
114Bob's in a better position than Eve. If he computes his challenges honestly
115then he doesn't learn much except that he's talking to Alice, because as
116we've seen, she only tells him $R$, which he knew already. However, if Bob
117carefully chooses a challenge $C$ without knowing its discrete log $\beta$,
118then Alice's response might tell him useful information about her private
119key that he couldn't have worked out just by sitting at home computing
120discrete logs.
122We can fix this little problem easily enough if we make Bob transmit a hash
123of his expected answer. Let $H \colon \mathbb{Z} \to \{\,0, 1\,\}^n$ be a
124hash function. The property we require from $H$ is that Bob can't compute
125$H(g^{a \beta})$ given only $C = g^\beta$ and $A = g^a$ with more than
126negligible probability; a random function would fit the bill fine. This
127does, of course, also assume that the Diffie-Hellman problem is difficult.
128The new protocol looks very much like the old one:
130\item Bob chooses a random $1 < \beta < q$. He computes $C = g^\beta$ and $R
131 = A^\beta$, and sends $C, H(R)$ to Alice.
132\item Alice computes $R' = C^a$ and checks that it matches the hash which Bob
133 sent. If it doesn't, he's trying to cheat, and she should refuse to
134 answer. Otherwise, she sends her response $R'$ back to Bob.
135\item Bob checks that Alice's reply matches the one he computed back in step
136 1. If it does, he knows that he's talking to Alice.
140\section{The Wrestlers Protocol}
142We observe a useful side-effect of the authentication protocol just
143described: Bob should be convinved that Alice received his challenge $C$
144correctly. The idea of the Wrestlers Protocol is to use this to construct a
145full Diffie-Hellman key exchange with mutual authentication. We maintain the
146useful properties of the previous protocol.
148Before they can use the protocol, Alice and Bob must agree on a group $G$ as
149before. Alice chooses a private key $1 < a < q$, and publishes her public
150key $A = g^a$; Bob similarly chooses a private key $1 < b < q$ and publishes
151his public key $B = g^b$.
153Here's the actual protocol in summary:
155\item $A \to B$:\quad $g^\alpha$
156\item $A \from B$:\quad $g^\beta$, $H(g^\alpha, g^\beta, g^{a \beta})$
157\item $A \to B$:\quad $g^{a \beta}$, $H(g^\beta, g^\alpha, g^{\alpha b})$
158\item $A \from B$:\quad $g^{\alpha b}$
161And now in detail:
164\item Alice invents a temporary secret $1 < \alpha < q$. She computes her
165 challenge $C_A = g^\alpha$, and sends it to Bob.
167\item Bob receives the $C_A$, and stores it away. He invents a temporary
168 secret $1 < \beta < q$ of his own, and computes both his challenge $C_B =
169 g^\beta$ and the expected response $R_B = A^\beta = g^{a \beta}$. He
170 hashes both challenges (hers first) and the expected response $R_B$, and
171 sends his challenge and the hash back to Alice.
173\item Alice reads Bob's challenge. She computes her response $R_B' = C_B^a =
174 g^{a \beta}$ and ensures that the Bob's hash is correct. If it isn't, she
175 stops talking to Bob. If the hash matches, she sends back her response,
176 together with a hash of Bob's challenge, her original challenge from step
177 1, and her expected response $R_A = B^\alpha = g^{\alpha b}$.
179\item Bob reads Alice's response. If it's wrong then he stops talking.
180 Otherwise he computes his response to Alice's challenge $R_A' = C_A^b =
181 g^{\alpha b}$ and checks Alice's hash. If the hash is wrong, he also stops
182 talking. Otherwise he sends the response back to Alice.
185Finally, Alice checks Bob's response, stopping the conversation if it's
186wrong. Then both sides compute their shared key $K = C_A^\beta = C_B^\alpha
187= g^{\alpha \beta}$, and discard their temporary secrets.
189The protocol is essentially symmetrical: each side sends and receives both a
190challenge and hash pair, and a response, but it doesn't look that simple
191because the hashes include both sides' challenges. Looking at it from one
192side at a time will make things clearer, so let's just take Alice's point of
195Alice constructs her challenge in step 1, and sends it off. She receives a
196challenge and hash in step 2. When she computes the response to the
197challenge, she verifies the hash she received. If it matches, she knows that
199\item whoever she's talking to hasn't attempted to cheat her by sending a
200 challenge for which he doesn't know the answer; and
201\item he has successfully received her challenge.
203Because she's now received a challenge, she can work out her hash. She sends
204off her response to the challenge, together with the hash, and awaits the
207In step 4, the response arrives. If it's correct, she knows that it's from
208Bob, and that he (Bob) received her challenge OK. Tying everything else
209together is the tricky bit.
211If we assume that Bob is playing by the rules, the fact that he's sent his
212response means that he verified it against Alice's hash and decided that
214\item Alice wasn't trying to cheat him and find out about his private key;
215 and
216\item Alice correctly received his challenge.
218Because Bob wouldn't have replied if these weren't true, Alice can therefore
219believe that she has received Bob's challenge correctly.
221To summarize: Alice has managed to get a challenge to Bob, and he responded;
222Alice has also received Bob's challenge correctly.
224What if Bob isn't honest? The only hole in the protocol which can be
225exploited by Bob is that he can send a response \emph{even though} it doesn't
226match Alice's hash. This means that the protocol will continue even if Alice
227is attempting to cheat Bob and find information about his private key: this
228is a penalty Bob has to pay for not following the rules. The protocol still
229aborts if an adversary interferes with the challenges: if Alice isn't given
230Bob's challenge accurately, her response will be wrong, and Bob can abort the
231exchange; similarly, if Bob isn't given Alice's challenge, she will detect
232this and abort the exchange.
235\section{Conclusions and further work}
237We have presented a new key exchange protocol based upon a novel use of
238Diffie-Hellman key exchange as a means of authentication.
240The arguments given in the previous section sound fairly convincing, but they
241don't provide a formal proof of the security of the Wrestlers Protocol. The
242authors are unaware of a logic system for verifying protocols which correctly
243capture the properties of hash functions.
245%%%----- That's all, folks --------------------------------------------------
249%%% Local Variables:
250%%% mode: latex
251%%% TeX-master: "wrestlers"
252%%% End: