X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/tripe/blobdiff_plain/74eb47db34cb72d98808afb40caced375f348f11..96e12a8165129bfe385e6ec233317ada460a271d:/doc/wrestlers.tex diff --git a/doc/wrestlers.tex b/doc/wrestlers.tex index d71e4306..c175b1a9 100644 --- a/doc/wrestlers.tex +++ b/doc/wrestlers.tex @@ -1,6 +1,6 @@ %%% -*-latex-*- %%% -%%% $Id: wrestlers.tex,v 1.1 2001/02/16 21:43:33 mdw Exp $ +%%% $Id: wrestlers.tex,v 1.5 2002/01/13 14:55:31 mdw Exp $ %%% %%% Description of the Wrestlers Protocol %%% @@ -10,243 +10,408 @@ %%%----- Revision history --------------------------------------------------- %%% %%% $Log: wrestlers.tex,v $ +%%% Revision 1.5 2002/01/13 14:55:31 mdw +%%% More incomplete stuff. +%%% +%%% Revision 1.4 2001/06/29 19:36:05 mdw +%%% Some progress made on laptop. +%%% +%%% 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. +%%% %%% Revision 1.1 2001/02/16 21:43:33 mdw %%% Initial versions of documentation. %%% -\documentclass{article} -\usepackage{amssymb} -\title{The Wrestlers Protocol} -\author{Mark Wooding \\ Clive Jones} -\def\from{\leftarrow} +\newif\iffancystyle\fancystylefalse + +\iffancystyle + \documentclass + [a4paper, article, 10pt, numbering, noherefloats, notitlepage] + {strayman} + \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts} + \usepackage[margin]{amsthm} +\else + \documentclass[a4paper]{article} + \usepackage{a4wide} + \usepackage{amsthm} +\fi + +\usepackage{amssymb, amstext} +\usepackage{mdwtab, mathenv} + +\errorcontextlines=999 +\showboxbreadth=999 +\showboxdepth=999 +\makeatletter + +\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange} +\author{Mark Wooding \and Clive Jones} + +\bibliographystyle{alpha} + +\newtheorem{theorem}{Theorem} +\renewcommand{\qedsymbol}{$\square$} + +\newcommand{\getsr}{\stackrel{\scriptscriptstyle R}{\gets}} +\newcommand{\inr}{\in_{\scriptscriptstyle R}} +\newcommand{\oracle}[1]{\mathcal{#1}} + +\newcommand{\expt}[2]{\mathbf{Exp}^{\text{\normalfont#1}}_{#2}} +\newcommand{\adv}[2]{\mathbf{Adv}^{\text{\normalfont#1}}_{#2}} +\newcommand{\ord}{\mathop{\operator@font ord}} +\newcommand{\poly}[1]{\mathop{\operator@font poly}({#1})} +\newcommand{\negl}[1]{\mathop{\operator@font negl}({#1})} +\newcommand{\compind}{\stackrel{c}{\approx}} + +\newcolumntype{G}{p{0pt}} + +\newcommand{\xor}{\oplus} +\renewcommand{\epsilon}{\varepsilon} + +\newenvironment{program} + {\begin{tabular}[C]{|G|}\hlx{hv[][\tabcolsep]}\begin{tabbing}} + {\end{tabbing}\\\hlx{v[][\tabcolsep]h}\end{tabular}} \begin{document} \maketitle - \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. + Fill this in later. \end{abstract} +\tableofcontents +\newpage -\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. - -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.) - -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. - -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. + +We begin by introducing a simple proof-of-identity protocol, based on the +Diffie-Hellman key-exchange protocol \cite{Diffie:1976:NDC} and prove some of +its useful 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$. +\subsection{Introduction} -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. +We start by selecting a security parameter $k$. We choose a cyclic group $G += \langle g \rangle$ with $q = |G|$ prime, in which the decision +Diffie-Hellman problem is assumed to be hard \cite{Boneh:1998:DDP}; we +require that $q$ is a $k$-bit number. Suitable groups include elliptic +curves over finite fields and prime-order subgroups of prime fields. +Throughout, we shall write the group operation as multiplication, and we +shall assume that group elements are interchangeable with their binary +representations. -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: +Alice can choose a private key $\alpha$ from the set $\{ 1, 2, \ldots, q - 1 +\}$ and publish her corresponding public key $a = g^\alpha$. + +A simplistic proof-of-identity protocol might then proceed as follows: \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. +\item Bob chooses a random exponent $\beta$, also from $\{ 1, 2, \ldots, q - + 1 \}$, and sends a \emph{challenge} $b = g^\beta$ to Alice. +\item Alice computes her \emph{response} $b^\alpha$ and returns it to Bob. +\item If Alice's response is equal to $a^\beta$ then Bob is satisfied. \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: +If Bob always plays by the rules then this protocol is evidently secure, +since computing $g^{\alpha\beta}$ given $g^\alpha$ and $g^\beta$ is precisely +the Diffie-Hellman problem. + +This protocol has a flaw, though: by using Alice as an oracle for the +function $x \mapsto x^\alpha$, he could conceivably acquire information about +Alice's private key which he could later use to impersonate her. As an +example, Bob can submit $-g^\beta$ as a challenge: if the reply +$(-g^\beta)^\alpha = g^{\alpha\beta}$, Bob can conclude that $\alpha$ is +even. + +We fix the protocol by requiring that Bob prove that he already knows the +answer to his challenge. We introduce a hash function $h$ whose properties +we shall investigate later. The \emph{Wrestlers Authentication Protocol} is +then: \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. +\item Bob chooses a secret $\beta \getsr \{ 1, 2, \ldots, q - 1 \}$. He + computes his \emph{challenge} $b \gets g^\beta$ and also a \emph{check + value} $c \gets \beta \xor h(a^\beta)$. He sends the pair $(b, c)$. +\item Alice receives $(b', c')$. She computes $r \gets b'^\alpha$ and + $\gamma \gets c' \xor h(R)$. If $b' = g^\gamma$, she sends $r$ back as her + \emph{response}; otherwise she sends the distinguished value $\bot$. +\item Bob receives $r'$. If $r' = a^\beta$ then he accepts that he's talking + to Alice. \end{enumerate} +We show that the introduction of the check value has indeed patched up the +weakness described above, and that the check value itself hasn't made an +impersonator's job much easier. + +\subsection{Analysis in the random oracle model} + +Here, we prove that the Wrestlers Authentication Protocol is secure if $h$ is +implemented by a public \emph{random oracle} \cite{Bellare:1993:ROP}. + +Fix a private key $\alpha \inr \{ 1, 2, \ldots, q - 1\}$ and the corresponding public +key $a = g^\alpha$, and consider a probabilistic polynomial-time adversary +$A$, equipped with two oracles. One is a random oracle $\oracle{H}\colon +\{0, 1\}^* \to \{0, 1\}^k$, which implements a function $h$ randomly selected +from the set of all functions with that signature; the other is an +authentication oracle $\oracle{O}\colon G \times \{0, 1\}^k \to G \cup \{ +\bot \}$ defined by: +\[ +\oracle{O}^(b, c) = \begin{cases} + b^\alpha & if $b = g^{c \xor h(b^\alpha)}$ \\ + \bot & otherwise +\end{cases} +\] +The authentication oracle will play the part of Alice in the following. We +first show that access to this authentication oracle can't help an adversary +learn how to impersonate Alice. + +\begin{theorem} + The Wrestlers Authentication Protocol with random oracle is computational + zero knowledge \cite{Brassard:1989:SZK}. + \label{thm:wap-czk} +\end{theorem} +\begin{proof} + \newcommand{\Hlist}{\textit{$\oracle{H}$-list}} + \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}} + \newcommand{\Osim}{\textit{$\oracle{O}$-sim}} + \renewcommand{\H}{\oracle{H}} + \renewcommand{\O}{\oracle{O}} + % + Let $A$ be any probabilistic polynomial-time adversary with access to a + random. We shall construct a probabilistic polynomial-time adversary $A'$ + without either oracle such that the probability distributions on the output + of $A$ and $A'$ are equal. Specifically, $A'$ runs $A$ with simulated + random and authentication oracles whose behaviour is computationally + indistinguishable from the originals. The algorithm for $A'$ and the + simulated oracles is shown in figure~\ref{fig:wap-czk-sim}. + + \begin{figure} + \begin{program} + \quad \= \kill + Adversary $A'^{\H(\cdot)}$: \+ \\ + $\Hlist \gets \emptyset$; \\ + $r \gets A^{\Hsim(\cdot), \Osim(\cdot, \cdot)}$; \\ + \textbf{return} $r$; \- \\[\medskipamount] + % + Simulated random oracle $\Hsim(q)$: \+ \\ + \textbf{if} $\exists r : (q, r) \in \Hlist$ \textbf{then} + \textbf{return} $r$; \\ + $r \getsr \H(q)$; \\ + $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\ + \textbf{return} $r$; \- \\[\medskipamount] + % + Simulated authentication oracle $\Osim(b, c)$: \+ \\ + \textbf{if} $\exists q, r : (q, r) \in \Hlist \wedge + b = g^{c \xor r} \wedge + q = a^{c \xor r}$ \textbf{then} + \textbf{return} $a^{c \xor r}$; \\ + \textbf{else} \textbf{return} $\bot$; + \end{program} + % + \caption{The algorithm and simulated oracles for the proof of + theorem~\ref{thm:wap-czk}.} + \label{fig:wap-czk-sim} + \end{figure} + + Firstly we show that $A'$ runs in polynomial time. The only modifications + to $\Hlist$ are in $\Hsim$, which adds at most one element for each oracle + query. Since $\Hlist$ is initially empty and $A$ can only make $\poly{k}$ + queries to $\Hsim$, this implies that $|\Hlist|$ is always + polynomially-bounded. Each query can be answered in polynomial time: + indeed, the search implied by the test $\exists r : (q, r) \in \Hlist$ can + be performed in $O(\log q)$ time by indexing $\Hlist$ on $q$ using a radix + tree. Now, since $|\Hlist|$ is polynomially bounded, the test $\exists q, + r : (q, r) \in \Hlist \wedge b = g^{c \xor r} \wedge q = a^{c \xor r}$ at + the start of $\Osim$ runs in polynomial time even though it requires an + exhaustive search of the history of $A$'s queries to its simulated random + oracle. + + Next, we examine the behaviour of the simulated oracles. Since $\Hsim$ is + implemented in terms of the public random oracle $\H$, and returns the same + answers to queries, its probability distribution must be identical. + + We turn our attention to the simulation of the authentication oracle. + Consider a query $(b, c)$ made by $A$ to its authentication oracle. + + Firstly, suppose that there is a $\beta$ such that $b = g^\beta$ and $c = + \beta \xor r$ where $r$ is the response to a previous query made by $A$ to + its random oracle on $a^\beta$. Then the true authentication oracle $\O$ + is satisfied because $b = g^\beta = g^{c \xor r} = g^{c \xor h(a^\beta)} = + g^{c \xor h(b^\alpha)}$, and returns $b^\alpha$. Similarly, the simulated + authentication oracle $\Osim$ will find the pair $(a^\beta, r) \in \Hlist$, + recover $\beta = c \xor r$, confirm that $b = g^\beta$, and return + $a^\beta$ as required. These events all occur with probability 1. + + Conversely, suppose that there is no such $\beta$. Then the simulated + oracle $\Osim$ will reject the query, returning $\bot$, again with + probability 1. However, a genuine authentication oracle $\O$ will succeed + and return $b^\alpha$ with probability $2^{-k}$. To see this, note that $b + = g^\gamma$ for some $\gamma \in \{ 0, 1, \ldots, q - 1 \}$, and the + probability that $h(b^\alpha) = c \xor \gamma$ is precisely $2^{-k}$, since + $c$ and $\gamma$ are $k$-bit strings. Since this probability is + negligible, we have shown that the distributions of the simulated oracles + $\Hsim$ and $\Osim$ are computationally indistinguishable from the genuine + oracles $\H$ and $\O$. The theorem follows. +\end{proof} + +Our next objective is to show that pretending to be Alice is hard without +knowledge of her secret $\alpha$. We say that an adversary $A$ +\emph{impersonates} in the Wrestlers Authentication Protocol with probability +$\epsilon$ if +\[ \Pr[A^{\oracle{H}(\cdot)}(g^\alpha, g^\beta, + \beta \xor h(g^{\alpha\beta})) + = g^{\alpha\beta}] + = \epsilon +\] +where the probability is taken over all choices of $\alpha, \beta \in \{ 1, +2, \ldots, q - 1 \}$ and random oracles $\oracle{H}$. + +\begin{theorem} + Assuming that the Diffie-Hellman problem is hard in $G$, no probabilistic + polynomial-time adversary can impersonate in the Wrestlers Authentication + Protocol with random oracle with better than negligible probability. + \label{thm:wap-dhp} +\end{theorem} +\begin{proof} + \newcommand{\Hlist}{\textit{$\oracle{H}$-list}} + \newcommand{\Hqueries}{\textit{$\oracle{H}$-queries}} + \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}} + \renewcommand{\H}{\oracle{H}} + % + We prove the theorem by contradiction. Given a polynomial-time adversary + $A$ which impersonates Alice with non-negligible probability $\epsilon$, we + construct an adversary which solves the Diffie-Hellman problem with + probability no less than $\epsilon \poly{k}$, i.e., + \[ \Pr[A'(g^\alpha, g^\beta) = g^{\alpha\beta}] \ge \epsilon \poly{k}. \] + Thus, if there is any polynomial-time $A$ which impersonates with better + than negligible probability, then there is a polynomial-time $A'$ which + solves Diffie-Hellman with essentially the same probability, which would + violate our assumption of the hardness of Diffie-Hellman. + + The idea behind the proof is that the check value is only useful to $A$ + once it has discovered the correct response to the challenge, which it must + have done by solving the Diffie-Hellman problem. Hence, our Diffie-Hellman + + \begin{figure} + \begin{program} + \quad \= \kill + Adversary $A'(a, b)$: \+ \\ + $\Hlist \gets \emptyset$; \\ + $\Hqueries \gets \emptyset$; \\ + $r \getsr \{ 0, 1 \}^k$; \\ + $x \gets A^{\Hsim(\cdot)}(a, b, r)$; \\ + $c \getsr (\Hlist \cup \{ x \}) \cap G$; \\ + \textbf{return} $c$; \- \\[\medskipamount] + % + Simulated random oracle $\Hsim(q)$: \+ \\ + \textbf{if} $\exists r : (q, r) \in \Hlist$ + \textbf{then} \textbf{return} $r$; \\ + $r \gets \{ 0, 1 \}^k$; \\ + $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\ + $\Hqueries \gets \Hqueries \cup \{ q \}$; \\ + \textbf{return} $r$; + \end{program} + % + \caption{The algorithm for the proof of theorem~\ref{thm:wap-dhp}} + \label{fig:wap-dhp-rdc} + \end{figure} + + The adversary $A'$ is shown in figure~\ref{fig:wap-dhp-rdc}. It generates + a random check-value and runs the impersonator $A$. + + The simulated random oracle $\Hsim$ gathers together the results of all of + the random oracle queries made by $A$. The final result returned by $A'$ + is randomly chosen from among all of the `plausible' random oracle queries + and $A$'s output, i.e., those queries which are actually members of the + group. The check value given to $A$ is most likely incorrect (with + probability $1 - 2^{-k}$): the intuition is that $A$ can only notice if it + actually computes the right answer and then checks explicitly. + + If $A$ does compute the correct answer $g^{\alpha\beta}$ and either returns + it or queries $\Hsim$ on it, then $A'$ succeeds with probability $\epsilon + / |(\Hlist \cup \{ x \}) \cap G| = \epsilon \poly{k}$, since $|\Hlist|$ is + no greater than the number of random oracle queries made by $A$ (which must + be polynomially bounded).\footnote{% + This polynomial factor introduces a loss in the perceived security of the + authentication protocol. It appears that this loss is only caused by the + possibility of the adversary $A$ being deliberately awkward and checking + the value of $c$ after having computed the answer. However, we can't see + a way to improve the security bound on the scheme without imposing + artificial requirements on $A$.} % + + It remains to show that if $A$ never queries its random oracle on + $g^{\alpha\beta}$ then it cannot distinguish the random check value $r$ + from the correct one $\beta \xor \H(g^{\alpha\beta})$, and hence won't + notice that $A'$ is lying to it. But this is obvious: $A$'s probability of + guessing the random value that would have been returned had it actually + queried $\Hsim$ on the input $g^{\alpha\beta}$ is equal to the probability + of it guessing $\beta \xor r$ instead, since $\Hsim$ chooses its responses + uniformly at random. This completes the proof. +\end{proof} +We conclude here that the Wrestlers Authentication Protocol is a secure +authentication protocol in the random oracle model: impersonation is hard if +the Diffie-Hellman problem is hard, and proving one's identity doesn't leak +secret key information. -\section{The Wrestlers Protocol} +\subsection{Requirements on hash functions} -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. +Having seen that the Wrestlers Authentication Protocol is secure in the +random oracle model, we now ask which properties we require from the hash +function. This at least demonstrates that the protocol isn't deeply flawed, +and suggests an efficient implementation in terms of conventional hash +functions. -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 we investigate more carefully the properties required of the hash +function, and provide a more quantitative analysis of the protocol. -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} +Looking at the proofs of the previous two sections, we see that the random +oracles are mainly a device which allow our constructions to `grab hold' of +the hashing operations performed by the adversary. -And now in detail: -\begin{enumerate} +%%%-------------------------------------------------------------------------- + +\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. + + +% messages +% +% pre-challenge: g^b +% cookie: g^b, h(cookie, g^b') +% challenge: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab') +% reply: g^b, h(g^b'), b + h(reply-check, g^b, g^b', g^ab'), E_k(g^a'b) +% switch: h(g^b), h(g^b'), E_k(g^a'b, h(switch-request, g^a, g^a')) +% switch-ok: E_k(g^ab, h(switch-confirm, g^a, g^a'))begin{ + + +We now describe the full Wrestlers Protocol, in a multi-party setting. Fix a +cyclic group $G = \langle g \rangle$ of order $q = |G|$. Each player $P_i$ +chooses a private key $\alpha_i \in \{ 1, 2, \ldots, q - 1 \}$ and publishes +the corresponding public key $a_i = g^{\alpha_i}$ to the other players. -\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{Conclusions and further work} - -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. %%%----- That's all, folks -------------------------------------------------- +\bibliography{cryptography,mdw-crypto} \end{document} %%% Local Variables: %%% mode: latex %%% TeX-master: "wrestlers" -%%% End: +%%% End: