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