From 90d03a8531584ba5467d13f28737e36d4afac658 Mon Sep 17 00:00:00 2001 Message-Id: <90d03a8531584ba5467d13f28737e36d4afac658.1715469315.git.mdw@distorted.org.uk> From: Mark Wooding Date: Fri, 22 Jun 2001 19:41:31 +0000 Subject: [PATCH 1/1] Restart with different structure and rather more formal objectives. Organization: Straylight/Edgeware From: mdw --- doc/wrestlers.tex | 266 +++++++++------------------------------------- 1 file changed, 53 insertions(+), 213 deletions(-) diff --git a/doc/wrestlers.tex b/doc/wrestlers.tex index 600b2fda..033f9fea 100644 --- a/doc/wrestlers.tex +++ b/doc/wrestlers.tex @@ -1,6 +1,6 @@ %%% -*-latex-*- %%% -%%% $Id: wrestlers.tex,v 1.2 2001/02/22 09:09:05 mdw Exp $ +%%% $Id: wrestlers.tex,v 1.3 2001/06/22 19:41:31 mdw Exp $ %%% %%% Description of the Wrestlers Protocol %%% @@ -10,6 +10,9 @@ %%%----- Revision history --------------------------------------------------- %%% %%% $Log: wrestlers.tex,v $ +%%% Revision 1.3 2001/06/22 19:41:31 mdw +%%% Restart with different structure and rather more formal objectives. +%%% %%% Revision 1.2 2001/02/22 09:09:05 mdw %%% Partially through reworking. %%% @@ -19,237 +22,74 @@ \documentclass{article} \usepackage{amssymb} -\title{The Wrestlers Protocol} -\author{Mark Wooding \\ Clive Jones} -\def\from{\leftarrow} +\usepackage{amstext} -\begin{document} +\errorcontextlines=999 +\makeatletter -\maketitle +\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange} +\author{Mark Wooding \and Clive Jones} -\begin{abstract} - We present a simple key-exchange protocol with of mutual authentication and - perfect forward-secrecy, which doesn't leave any long-lasting evidence of - participation in the exchange. The protocol's security depends on the - intractability of the Diffie-Hellman problem (in some cyclic group), and on - the strength of a hash function. -\end{abstract} +\bibliographystyle{alpha} -\section{Introduction} - -Current key-agreement protocols are all very well for securing generally -`honest' traffic (e.g., transmission of credit-card details to a merchant), -but they're less satisfactory if you actually have something to hide. +\newtheorem{theorem}{Theorem} +\newenvironment{proof}[1][Proof]{% + \par\noindent\textbf{#1.} % +}{% + \penalty\@M\hfill\vadjust{}% + \penalty\z@\relax\vadjust{}% + \penalty\@M\hfill$\square$% + \par% +} -In the UK, new key exchange protocols have been particularly motivated by the -new Regulation of Investigatory Powers Act, which allows `authorized persons' -to intercept communications and demand long-term encryption keys. - -Let's suppose that Alice and Bob are shady characters, and that their -communications are of great interest to the draconian r\'egime in which they -live. (They might be international arms smugglers, for example, because they -export cryptographic toolkits.) +\begin{document} -Alice could just invent a session key and transmit it to Bob, encrypted under -his public key, each time she wanted to talk to him. However, once the -secret police turn up at Bob's house and demand his private key, the game is -over and all of the communications can be recovered. +\maketitle +\begin{abstract} + Fill this in later. +\end{abstract} +\tableofcontents +\newpage -Alice and Bob would clearly be better off using a system which offers forward -secrecy, for example, Diffie-Hellman. However, in order to prevent active -attacks, the messages in the Diffie-Hellman exchange must be authenticated. -The way this usually works is that Alice and Bob pick a group $G$ of order -$q$ generated by $g$. When Alice and Bob want to communicate, they choose -exponents $\alpha$ and $\beta$ respectively ($1 < \alpha, \beta < q$), Alice -sends $S_A(g^\alpha)$ to Bob, Bob sends $S_B(g^\beta)$ to Alice, and, after -verifying each other's signatures, they each compute a shared key $K = -g^{\alpha \beta}$. They dispose of their secrets $\alpha$ and $\beta$ -forthwith, and destroy $K$ when the conversation finishes. Now the secret -police can demand all they like: they still can't decrypt old sessions, and -Alice and Bob, however badly tortured, can't help them. The secret police -might not even be all owed to demand their long-term signing keys: for -example, the RIPA grants special protection to authentication-only keys. +%%%-------------------------------------------------------------------------- -This is fine, except that sending $S_A(g^\alpha)$ is a wonderful way of -shouting `Alice was here' to all of the spooks tapping Bob's network -connection. The Wrestlers Protocol\footnote{% - Named after the excellent pub in Cambridge where most of the design was - done.} -fixes these problems. It provides perfect forward secrecy, just like -Diffie-Hellman, without leaving signatures around for the spooks. +\section{Introduction} +% Some waffle here about the desirability of a key-exchange protocol that +% doesn't leave signatures lying around, followed by an extended report of +% the various results. +%%%-------------------------------------------------------------------------- \section{A simple authentication protocol} +% Present the basic Diffie-Hellman-based authenticator, and prove that an +% authentication oracle is useless if the hash function has appropriate +% properties. -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} +Suppose that $G$ is some cyclic group of order $q$, generated by an element +$g$, in which the decision Diffie-Hellman problem \cite{Boneh:1998:DDP} is +hard. Alice can choose a private key $1 < \alpha < q$ and publish her +corresponding public key $A = g^\alpha$. Later, Bob can verify that he's +talking to Alice by choosing a random $1 < \beta < q$ and sending Alice a +\emph{challenge} $B = g^\beta$. If she replies with $B^\alpha$, Bob accepts +that he's talking to Alice, otherwise he doesn't. +%%%-------------------------------------------------------------------------- -\section{Conclusions and further work} +\section{An MT-authenticator} +% Use the protocol of the previous section as an MT-authenticator, within the +% meaning of [Canetti:2001:AKE]. -We have presented a new key exchange protocol based upon a novel use of -Diffie-Hellman key exchange as a means of authentication. +%%%-------------------------------------------------------------------------- -The arguments given in the previous section sound fairly convincing, but they -don't provide a formal proof of the security of the Wrestlers Protocol. The -authors are unaware of a logic system for verifying protocols which correctly -capture the properties of hash functions. +\section{A key-exchange protocol} +% Present the Wrestlers protocol in all its glory. Show, by means of the +% previous proofs, that the Wrestlers protocol is simulatable in the +% authenticated model using a much simpler protocol. Show that the simpler +% protocol is SK-secure. %%%----- That's all, folks -------------------------------------------------- +\bibliography{cryptography,mdw-crypto} \end{document} %%% Local Variables: -- [mdw]