Commit | Line | Data |
---|---|---|

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 | ||

40 | Current key-agreement protocols are all very well for securing generally | |

41 | `honest' traffic (e.g., transmission of credit-card details to a merchant), | |

42 | but they're less satisfactory if you actually have something to hide. | |

43 | ||

44 | In the UK, new key exchange protocols have been particularly motivated by the | |

45 | new Regulation of Investigatory Powers Act, which allows `authorized persons' | |

46 | to intercept communications and demand long-term encryption keys. | |

47 | ||

48 | Let's suppose that Alice and Bob are shady characters, and that their | |

49 | communications are of great interest to the draconian r\'egime in which they | |

50 | live. (They might be international arms smugglers, for example, because they | |

51 | export cryptographic toolkits.) | |

52 | ||

53 | Alice could just invent a session key and transmit it to Bob, encrypted under | |

54 | his public key, each time she wanted to talk to him. However, once the | |

55 | secret police turn up at Bob's house and demand his private key, the game is | |

56 | over and all of the communications can be recovered. | |

57 | ||

58 | Alice and Bob would clearly be better off using a system which offers forward | |

59 | secrecy, for example, Diffie-Hellman. However, in order to prevent active | |

60 | attacks, the messages in the Diffie-Hellman exchange must be authenticated. | |

61 | The 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 | |

63 | exponents $\alpha$ and $\beta$ respectively ($1 < \alpha, \beta < q$), Alice | |

64 | sends $S_A(g^\alpha)$ to Bob, Bob sends $S_B(g^\beta)$ to Alice, and, after | |

65 | verifying each other's signatures, they each compute a shared key $K = | |

66 | g^{\alpha \beta}$. They dispose of their secrets $\alpha$ and $\beta$ | |

67 | forthwith, and destroy $K$ when the conversation finishes. Now the secret | |

68 | police can demand all they like: they still can't decrypt old sessions, and | |

69 | Alice and Bob, however badly tortured, can't help them. The secret police | |

70 | might not even be all owed to demand their long-term signing keys: for | |

71 | example, the RIPA grants special protection to authentication-only keys. | |

72 | ||

73 | This is fine, except that sending $S_A(g^\alpha)$ is a wonderful way of | |

74 | shouting `Alice was here' to all of the spooks tapping Bob's network | |

75 | connection. The Wrestlers Protocol\footnote{% | |

76 | Named after the excellent pub in Cambridge where most of the design was | |

77 | done.} | |

78 | fixes these problems. It provides perfect forward secrecy, just like | |

79 | Diffie-Hellman, without leaving signatures around for the spooks. | |

80 | ||

81 | ||

82 | \section{A simple authentication protocol} | |

83 | ||

84 | As a building-block, we construct a simple authentication protocol based on | |

85 | Diffie-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 | ||

88 | A Diffie-Hellman key exchange allows two parties to compute the same value, | |

89 | with different knowledge. We'll use this to make an authentication protocol. | |

90 | ||

91 | Alice chooses a private key $1 < a < q$. Her public key is $A = g^a$. She | |

92 | can 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 | ||

103 | This protocol has nice properties. It's not terribly difficult to implement, | |

104 | given the usual tools like modular exponentiation or elliptic curve | |

105 | point-addition. | |

106 | ||

107 | An eavesdropper -- let's call her Eve, for tradition's sake -- doesn't learn | |

108 | anything terribly interesting from watching the exchange. She sees $C$ going | |

109 | one way and then $C^a$ coming back. If she finds this illuminating, she can | |

110 | program 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 | |

112 | couldn't have worked out for herself. In fact, she doesn't even learn that | |

113 | Alice is involved in the conversation! Bob can fake up an authentication | |

114 | with Alice by secretly agreeing which value of $\beta$ he's going to use with | |

115 | an accomplice. | |

116 | ||

117 | Bob's in a better position than Eve. If he computes his challenges honestly | |

118 | then he doesn't learn much except that he's talking to Alice, because as | |

119 | we've seen, she only tells him $R$, which he knew already. However, if Bob | |

120 | carefully chooses a challenge $C$ without knowing its discrete log $\beta$, | |

121 | then Alice's response might tell him useful information about her private | |

122 | key that he couldn't have worked out just by sitting at home computing | |

123 | discrete logs. | |

124 | ||

125 | We can fix this little problem easily enough if we make Bob transmit a hash | |

126 | of his expected answer. Let $H \colon \mathbb{Z} \to \{\,0, 1\,\}^n$ be a | |

127 | hash 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 | |

129 | negligible probability; a random function would fit the bill fine. This | |

130 | does, of course, also assume that the Diffie-Hellman problem is difficult. | |

131 | The 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 | |

145 | We observe a useful side-effect of the authentication protocol just | |

146 | described: Bob should be convinved that Alice received his challenge $C$ | |

147 | correctly. The idea of the Wrestlers Protocol is to use this to construct a | |

148 | full Diffie-Hellman key exchange with mutual authentication. We maintain the | |

149 | useful properties of the previous protocol. | |

150 | ||

151 | Before they can use the protocol, Alice and Bob must agree on a group $G$ as | |

152 | before. Alice chooses a private key $1 < a < q$, and publishes her public | |

153 | key $A = g^a$; Bob similarly chooses a private key $1 < b < q$ and publishes | |

154 | his public key $B = g^b$. | |

155 | ||

156 | Here'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 | ||

164 | And 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} | |

188 | Finally, Alice checks Bob's response, stopping the conversation if it's | |

189 | wrong. Then both sides compute their shared key $K = C_A^\beta = C_B^\alpha | |

190 | = g^{\alpha \beta}$, and discard their temporary secrets. | |

191 | ||

192 | The protocol is essentially symmetrical: each side sends and receives both a | |

193 | challenge and hash pair, and a response, but it doesn't look that simple | |

194 | because the hashes include both sides' challenges. Looking at it from one | |

195 | side at a time will make things clearer, so let's just take Alice's point of | |

196 | view. | |

197 | ||

198 | Alice constructs her challenge in step 1, and sends it off. She receives a | |

199 | challenge and hash in step 2. When she computes the response to the | |

200 | challenge, 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} | |

206 | Because she's now received a challenge, she can work out her hash. She sends | |

207 | off her response to the challenge, together with the hash, and awaits the | |

208 | response. | |

209 | ||

210 | In step 4, the response arrives. If it's correct, she knows that it's from | |

211 | Bob, and that he (Bob) received her challenge OK. Tying everything else | |

212 | together is the tricky bit. | |

213 | ||

214 | If we assume that Bob is playing by the rules, the fact that he's sent his | |

215 | response 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} | |

221 | Because Bob wouldn't have replied if these weren't true, Alice can therefore | |

222 | believe that she has received Bob's challenge correctly. | |

223 | ||

224 | To summarize: Alice has managed to get a challenge to Bob, and he responded; | |

225 | Alice has also received Bob's challenge correctly. | |

226 | ||

227 | What if Bob isn't honest? The only hole in the protocol which can be | |

228 | exploited by Bob is that he can send a response \emph{even though} it doesn't | |

229 | match Alice's hash. This means that the protocol will continue even if Alice | |

230 | is attempting to cheat Bob and find information about his private key: this | |

231 | is a penalty Bob has to pay for not following the rules. The protocol still | |

232 | aborts if an adversary interferes with the challenges: if Alice isn't given | |

233 | Bob's challenge accurately, her response will be wrong, and Bob can abort the | |

234 | exchange; similarly, if Bob isn't given Alice's challenge, she will detect | |

235 | this and abort the exchange. | |

236 | ||

237 | ||

874aed51 | 238 | \section{Practical considerations} |

239 | ||

240 | ||

74eb47db | 241 | \section{Conclusions and further work} |

242 | ||

243 | We have presented a new key exchange protocol based upon a novel use of | |

244 | Diffie-Hellman key exchange as a means of authentication. | |

245 | ||

246 | The arguments given in the previous section sound fairly convincing, but they | |

247 | don't provide a formal proof of the security of the Wrestlers Protocol. The | |

248 | authors are unaware of a logic system for verifying protocols which correctly | |

249 | capture 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: |