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