-As a building-block, we construct a simple authentication protocol based on
-Diffie-Hellman key exchange. As before, let's use a group $G$ of order $q$
-(for some prime $q$), generated by a group element $g$.
-
-A Diffie-Hellman 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 Diffie-Hellman, 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
-point-addition.
-
-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 Diffie-Hellman 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 side-effect 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 Diffie-Hellman 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}