From a6e375a6211f5c082a45c9424a96820054219a55 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Wed, 1 Nov 2006 14:51:06 +0000 Subject: [PATCH] Initial commit -- work in progress. --- .gitignore | 13 + Makefile | 10 + background.tex | 766 +++++++++++++ ecc.mp | 134 +++ wrestlers.tex | 3273 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ wrshortsl.tex | 6 + wrslide.tex | 346 ++++++ wrslides.cls | 75 ++ wrslides.tex | 32 + 9 files changed, 4655 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 background.tex create mode 100644 ecc.mp create mode 100644 wrestlers.tex create mode 100644 wrshortsl.tex create mode 100644 wrslide.tex create mode 100644 wrslides.cls create mode 100644 wrslides.tex diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..79b2cef --- /dev/null +++ b/.gitignore @@ -0,0 +1,13 @@ +*.pdf +*.[0-9] +*.ps +*.dvi +*.log +*.lof +*.lot +*.aux +*~ +*.bbl +*.blg +*.tmp +*.toc diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..2c5c168 --- /dev/null +++ b/Makefile @@ -0,0 +1,10 @@ +all: \ + wrestlers.ps wrestlers.pdf \ + wrslides.pdf \ + wrslides-full.pdf + +%.ps: %.dvi + dvips -o $@ $+ + +%.dvi: %.tex + latex \ No newline at end of file diff --git a/background.tex b/background.tex new file mode 100644 index 0000000..f2a6554 --- /dev/null +++ b/background.tex @@ -0,0 +1,766 @@ +\xcalways\section{Cryptographic background}\x + +\xcalways\subsection{Groups}\x + +\begin{slide} + \resetseq + \head{Groups \seq: definition} + \topic{definitions} + + A \emph{group} is a set $G$ of objects, and a binary operation $\op$, with + the following properties. + \begin{description} + \item [Closure] If $a$ and $b$ are elements of $G$, then so is $a \op b$. + \item [Associativity] For any $a$, $b$ and $c$ in $G$, + \[ a \op (b \op c) = (a \op b) \op c. \] + \item [Identity] There exists an element $e$ so that, for any $a$ in $G$, + \[ a \op e = a = e \op a. \] + \item [Inverses] For any $a$ in $G$, there exists a $b$ so that + \[ a \op b = e = b \op a. \] + \end{description} +\end{slide} + +\begin{slide} + \head{Groups \seq: abelian groups} + + A group $(G, \op)$ is \emph{commutative}, or \emph{abelian}, if it has the + following additional property. + \begin{description} + \item [Commutativity] For any $a$ and $b$ in $G$, + \[ a \op b = b \op a. \] + \end{description} + We usually write the operator of an abelian group using some familiar + symbol, like $+$ or $\times$. +\end{slide} + +\begin{slide} + \head{Groups \seq: notation} + + Let $(G, +)$ be a group written additively. For $A, B \in G$, we do the + obvious things and write $0_G$, or just $0$, for the identity, and $-A$ for + the inverse of $A$; we also write + \[ A - B \equiv A + (- B) \qquad + 2 A \equiv A + A \qquad + n A \equiv \underbrace{A + A + \cdots + A}_\text{$n$ times}. + \] + Similarly, if $(H, \times)$ is a group written multiplicatively, and + $\alpha, \beta \in H$, we do the obvious things and write $1_H$, or just + $1$, for the identity, and $\alpha^{-1}$ for the inverse of $\alpha$; we + also write + \[ \alpha \beta \equiv \alpha \times \beta \qquad + \alpha/\beta \equiv \alpha \times \beta^{-1} \qquad + \alpha^2 \equiv \alpha \times \alpha \qquad + \alpha^n \equiv \underbrace{\alpha \times \alpha \times \cdots + \alpha}_\text{$n$ times}. + \] + The number of elements of a group $G$ is written $|G|$ (or sometimes + $\#G$), and is called the \emph{order} of $G$. +\end{slide} + +\begin{slide} + \head{Groups \seq: cyclic groups and discrete logs} + \topic{cyclic groups and discrete logs} + + A \emph{cyclic} group $(G, +)$ consists only of elements $n P$ for a single + $P$ and varying $n \in \Z$. We call $P$ a \emph{generator} of the group. + + Cyclic groups are always abelian. + + If $G$ is finite, then for any $A \in G$, there is a \emph{unique} $a \in + \Nupto{|G|}$ for which $A = a P$. We call $a$ the \emph{discrete + logarithm} of $A$ to the base $P$. + + This makes more sense if you consider a multiplicative group $(H, \times)$. + Then there's a $\gamma \in H$, and for any $\alpha$, a unique $a \in + \Nupto{|H|}$ such that $\alpha = \gamma^a$. + + Computing discrete logs seems to be difficult in some kinds of groups. +\end{slide} + +\begin{slide} + \head{Groups \seq: Diffie-Hellman} + \topic{Diffie-Hellman} + + Fix some cyclic group $(G, +)$, with generator $P$. + \begin{protocol} + Alice & Bob \\[\medskipamount] + $a \getsr \Nupto{|G|}$; & $b \getsr \Nupto{|G|}$; \\ + $A \gets a P$; & $B \gets b P$; \\ + \send{->}{A} + \send{<-}{B} + $Z \gets a B$; & $Z \gets b A$; + \end{protocol} + This works because + \[ Z = a B = a (b P) = (a b) P = (b a) P = b (a P) = b A. \] + Computing $a b P$ from $a P$ and $b P$ seems hard. This is the + (computational) \emph{Diffie-Hellman} problem. + + The best way we know is to work out $a$ or $b$ -- i.e., extract a discrete + logarithm. +\end{slide} + +\begin{slide} + \head{Groups \seq: ElGamal encryption} + \topic{ElGamal encryption} + + Suppose $H\colon G \to \Bin^n$ is a secure hash function. Alice has a + private key~$a \in \Nupto{|G|}$. Bob knows her public key~$A = a P$. He + has an $n$-bit message $m$ he wants to send her. + \begin{enumerate} + \item He chooses $r \inr \Nupto{|G|}$. + \item He computes $R = r P$. + \item He computes $Z = r A$. + \item He sends Alice the pair $(R, m \xor H(Z))$. + \end{enumerate} + Alice can decrypt because + \[ a R = (a r) P = r A = Z. \] +\end{slide} + +\begin{slide} + \head{Groups \seq: Schnorr groups} + \topic{examples} + + Let $p$ and $q$ be prime, with $p = q f + 1$. The residues modulo $p$ form + a \emph{finite field} $\F_p$. The nonzero elements form a cyclic group + $\F_p^*$ under multiplication mod~$p$. Let $\eta$ be a generator of + $\F_p^*$. + + Set $\gamma = \eta^f$. Then + \[ G = \langle \gamma \rangle = \{\, \gamma^n \mid 0 \le n < q \,\} \] + is a \emph{Schnorr group} of $q$ elements. $G$ is cyclic, with generator + $\gamma$. + + In practice, you don't need to find $\eta$. Pick $\alpha \in \F_p^*$ + arbitrarily (2 is a good first choice); if $\alpha^f \ne 1$ then use + $\gamma = \alpha^f$. +\end{slide} + +\begin{slide} + \head{Groups \seq: elliptic curves} + + Let $q = p^f$ be a prime power. Then there is a finite field $\F_q$ with + $q$ elements. + + Let $E$ be an \emph{elliptic curve} over $\F_q$: + \[ E(\F_q) = \{\, (x, y) \in \F_q^2 \mid y^2 = x^3 + a x + b \,\} \] + \begin{tabularx}{\linewidth}{@{}Xl} + \hrule height 0pt + The points of $E(\F_q)$ form a group with a peculiar kind of addition + (pictured right). + \parskip=1ex + + If $\#E(\F_q)$ has a large prime factor then we can + use a cyclic subgroup of $E(\F_q)$. The details are complicated\dots + & + \vtop{\hrule height 0pt \hbox{ + \ifpdf + \includegraphics[scale = 0.6]{ecc-0.pdf} + \else + \includegraphics[scale = 0.6]{ecc.0} + \fi + }} + \end{tabularx} +\end{slide} + + +\xcalways\subsection{Bilinear maps}\x + +\begin{slide} + \resetseq + \head{Bilinear maps \seq: definition} + \topic{definition} + + Let $(G, +)$, $(G', +)$ and $(G_T, \times)$ be three cyclic groups with the + same order. Let $P$ and $P'$ generate $G$ and $G'$ respectively. + + A map $\hat{e}\colon G \times G' \to G_T$ is \emph{bilinear} if + \begin{itemize} + \item for any $R \in G$ and $S', T' \in G'$, + \[ \hat{e}(R, S' + T') = \hat{e}(R, S') \, \hat{e}(R, T'), \] + and + \item for any $R, S \in G$ and $T' \in G'$, + \[ \hat{e}(R + S, T') = \hat{e}(R, T') \, \hat{e}(S, T'). \] + \end{itemize} + We say that $\hat{e}$ is \emph{non-degenerate} if + \[ \hat{e}(P, P') \ne 1. \] +\end{slide} + +\begin{slide} + \head{Bilinear maps \seq: properties} + \topic{properties} + + Define + \[ \gamma = \hat{e}(P, P'). \] + Then $\gamma$ generates $G_T$. + + For any $a$ and $b$: + \[ \hat{e}(a P, b P') = \gamma^{a b}. \] + If $\hat{e}$ is easy to compute then this is like a Diffie-Hellman + computation combined with an isomorphism to a different group. +\end{slide} + +\begin{slide} + \head{Bilinear maps \seq: the Bilinear Diffie-Hellman problem} + \topic{bilinear Diffie-Hellman problem} + + The \emph{bilinear} Diffie-Hellman problem is this: given + \begin{itemize} + \item $a P$ and $b P$ in $G$, and + \item $a P'$ and $c P'$ in $G'$, + \end{itemize} + compute + \[ \zeta = \gamma^{abc}. \] + + This can be done if the Diffie-Hellman problem can be solved in \emph{any} + of $G$, $G'$ or $G_T$. + \begin{itemize} + \item If DHP easy in $G$, then compute $\zeta = \hat{e}(a b P, c P')$. + \item If DHP easy in $G'$, then compute $\zeta = \hat{e}(b P, a c P')$. + \item If DHP easy in $G_T$, then compute $\alpha = \hat{e}(a P, P') = + \gamma^a$, $\beta = \hat{e}(b P, c P') = \gamma^{b c}$ and $\zeta$ from + $\alpha$ and $\beta$. + \end{itemize} +\end{slide} + +\begin{slide} + \head{Bilinear maps \seq: Boneh-Franklin identity-based encryption} + \topic{Boneh-Franklin identity-based encryption} + + We need two hashes: $H \colon G_T \to \Bin^n$ and $H_\text{id} \colon + \Bin^* \to G'$. + + There is a \emph{trusted third party}. It has a private key $t \inr + \Nupto{|G|}$ and a public key $T = t P$. + + Alice's public key is $A = H_\text{id}(\texttt{Alice})$. Her private key + is $K_A = t A$. + + Bob wants to send Alice a message $m \in \Bin^n$. + \begin{enumerate} + \item He chooses $r \inr \Nupto{|G|}$. + \item He computes $R = r P$. + \item He computes $\psi = \hat{e}(T, A)^r$. + \item He sends Alice the pair $(R, m \xor H(\psi))$. + \end{enumerate} + Alice can decrypt because + \[ \hat{e}(R, K_A) = \hat{e}(r P, t A) + = \hat{e}(P, A)^{rt} + = \hat{e}(t P, A)^r + = \hat{e}(T, A)^r + = \psi. \] +\end{slide} + +\begin{slide} + \head{Bilinear maps \seq: examples} + \topic{examples} + + The major examples of bilinear maps are the \emph{Weil} and \emph{Tate + pairings} on torsion groups of elliptic curves. +\end{slide} + + +\xcalways\subsection{Zero-knowledge}\x + +\begin{slide} + \resetseq + \head{Zero-knowledge \seq: interactive proofs} + \topic{interactive proofs} + + Prover and verifier exchange messages. Verifier decides whether to + \emph{accept} or \emph{reject} the proof. + + An interactive proof system must have the following properties. + \begin{description} + \item [Completeness] If the prover is honest, the verifier (almost always) + accepts. + \item [Soundness] If the prover is \emph{dishonest}, the verifier + (sometimes) rejects. + \end{description} + Repeat protocol several times to reduce soundness error. +\end{slide} + +\begin{slide} + \head{Zero-knowledge \seq: simulation} + \topic{simulation} + + We have a prover $P$ and a verifier $V$. Write + \[ x \gets V^P() \] + to mean that $V$ outputs $x$ after interacting with $P$. + + Suppose that there is a simulator~$S$ so that, for all $y$, + \[ |\Pr[x \gets V^P() : x = y] - \Pr[x \gets S() : x = y]| \le \epsilon. \] + If $\epsilon$ is small, then $V$ is unlikely to be able to persuade anyone + that he learned anything from $P$. + + in particular, if $\epsilon = 0$ then we say that the proof has + \emph{perfect zero knowledge}. +\end{slide} + +\begin{slide} + \head{Zero-knowledge \seq: an example} + \topic{example} + + Prover $P$ knows that $\alpha = \beta^2 \in \Z/n\Z$ for some composite $n$. + \begin{protocol} + Prover $P$ & Verifier $V$ \\[\medskipamount] + $\gamma \getsr \Z/n\Z$; \\ + \send{->}{\kappa = \gamma^2 \alpha} + \send{<-}{c \inr \Bin} + \send{->}{\rho = \gamma \beta^c} + & Check: $\kappa = \rho^2 \alpha^{1 - c}$ + \end{protocol} + + \begin{itemize} + \item Completeness: + \[ \rho \alpha^{1 - c} = (\gamma \beta^c)^2 \alpha^{1 - c} + = \gamma^2 \beta^{2c} \alpha^{1 - c} + = \gamma^2 \alpha^c \alpha^{1 - c} + = \gamma^2 \alpha + = \kappa. + \] + \item Soundness: if $P^*$ convinces $V$ with probability $p > \frac{1}{2}$ + then we can, in theory, run $P^*$ with (say) $c = 0$ and get $\gamma$. + We then \emph{rewind} $P^*$, give it $c = 1$, and get $\gamma \beta$, + from which we compute $\beta$. This works with probability at least $p - + \frac{1}{2}$. + \end{itemize} +\end{slide} + +This statement could use some proof. + +Firstly, consider a simple abstract game. There is a secret table, with two +columns and $r$ rows. Exactly $n$ of the entries in the table contain $1$; +the remaining entries contain zero. We have to pick a row, and you win if +both entries in that row contain $1$. + +Clearly, if $n \le r$, it's possible to arrange the ones so that each is in a +different row. If we're playing against someone unscrupulous, we are +guaranteed to lose. + +On the other hand, if $n > r$, there must be a winning row, because there are +too many ones to fit otherwise. In fact, there must be at least $n - r$ +winning rows. So our probability of winning must be at least $(n - r)/2r$. + +Apply this to the problem of our dishonest prover. The `table''s rows are +indexed by all the possible inputs to the prover -- the value $\alpha$ and +its own internal coin tosses. (We only consider provers running in bounded +time, so these are finite.) The columns are indexed by our coin $c$. We +know that $2 r p$ of the entries contain $1$. Hence, the probability that we +win is at least +\[ \frac{2 r p - r}{2 r} = p - \frac{1}{2}. \] + +\begin{slide} + \head{Zero-knowledge \seq: an example (cont.)} + + We now show zero-knowledge, by describing a simulator. + \begin{enumerate} + \item Simulator chooses $\rho \inr \Z/n\Z$ and $b \inr \Bin$ at random. It + runs $V$ and sends it $\kappa = \rho \alpha^{1 - b}$. + \item Verifier runs, returns bit $c$. + \item If $b = c$ then simulator sends back $\rho$. If $b \ne c$ then + simulator gives up and tries again. + \item Verifier (presumably) accepts, because + \[ \rho \alpha^{1 - c} = \rho \alpha^{1 - b}. \] + \end{enumerate} + Simulator fails (and retries) with probability $\frac{1}{2}$, because $b$ + is uniform and independent of $c$. +\end{slide} + +\begin{slide} + \head{Aside on KCDSA} + \topic{KCDSA} + + Let $(G, +)$ be a cyclic group of prime order $q$, with generator $P$. Let + $H\colon G \to \Bin^t$ and $H'\colon \Bin^* \to \Bin^t$ be cryptographic + hash functions. + + Alice's private key is $a \inr \F_q$. Her public key is $A = a P$. + Suppose Alice wants to sign a message $m \in \Bin^*$. + \begin{enumerate} + \item She chooses a random $k \inr \F_q$. She computes $K = k P$, and $r = + H(K)$. + \item Computes $h = H'(m)$, and $u = (h \xor r) \bmod q$. + \item Finally, she computes $s = (k - u)/a$. + \end{enumerate} + Her signature on $m$ is $\sigma = (r, s)$. + + To verify $(r, s)$, Bob can compute $h = H'(m)$; he checks that + \[ r = H(s A + u P). \] + Note that $s a = k - u$, so $s a + u = k$. Hence $s A + u P = (s + a + u) P = k P = K$. +\end{slide} + +\begin{slide} + \head{Zero-knowledge \seq: KCDSA as identification protocol} + + As before, let $(G, +)$ be a cyclic group, generated by $P$, of prime order + $q$, and let $H\colon G \to \Bin^t$ be a cryptographic hash function. + \begin{protocol} + Alice & Bob \\ + (private key $a \inr \F_q$) & (public key $A = a P$) \\[\medskipamount] + $k \getsr \F_q$; $K \gets k P$; \\ + \send{->}{r = H(K)} + \send{<-}{m \inr \Bin^{t}} + $u \gets (r \xor m) \bmod q$; & $u \gets (r \xor m) \bmod q$; \\ + \send{->}{s = (k - u)/x} + & Check: $r = H(s A + u P)$ + \end{protocol} +\end{slide} + +\begin{slide} + \head{Zero-knowledge \seq: KCDSA as identification protocol (cont.)} + + \begin{itemize} + \item Completeness: as for the KCDSA signature scheme. + \item Soundness: suppose some prover manages to impersonate Alice with + probability $\epsilon > 2^{-t}$. We choose some $m$ and send it to the + prover, getting $s$. Now we \emph{rewind} the prover and send it some + $m' \ne m$. With probability at least $\epsilon(\epsilon - 2^{-t})$, we + expect it to give us a valid $s'$. Let $u' = (m' \xor r) \bmod q$. + \begin{itemize} + \item If $s A + u P \ne s' A + u' P$ then we have a hash collision. So + assume $s a + u = s' a + u'$. + \item We chose $m \ne m'$, so $u = r \xor m \ne r \xor m' = u'$. We'd + notice if $a = 0$, so $s \ne s'$. + \item Therefore, we can derive + \[ a = \frac{u' - u}{s - s'}. \] + \end{itemize} + So our fake prover can compute discrete logs. + \end{itemize} +\end{slide} +It's worth proving the probability given above. I use the approach of +K\"asper, Laur and Lipmaa [KLL06]. + +Let's consider first a simple setting. Let $U$ and $V$ be two finite sets, +and let $G \subseteq U \times V$ be a set of `good pairs'. Suppose that $|G| += \epsilon |U| |V|$, i.e., +\[ \Pr[(u, v) \getsr U \times V : (u, v) \in G] = \epsilon. \] +We now perform the following simple experiment. Choose $u$ and $v$ uniformly +at random from $U$ and $V$ respectively. If $(u, v) \notin G$, then give up. +Otherwise, choose $v' \inr V$. If $(u, v') \in G$ and $v' \ne v$ then we +win. What's the probability that we win? + +Some more notation would be handy. For each $u \in U$, let $G_u = \{\, v \in +V \mid (u, v) \in G \,\}$, and $n_u = |G_u|$. Then +\[ |G| = \sum_{u \in U} n_u. \] +Suppose we're given $(u, v) \inr G$, and $v' \inr V$. We want $\Pr[v' \in +G_u \setminus \{v\}]$. Well, +\begin{eqnarray*}[rl] + \Pr[v \in G_u] + & = \sum_{u^* \in U} \Pr[v' \in G_{u^*} \setminus \{v\}] \Pr[u = u^*] \\ + & \ge \sum_{u^* \in U} \frac{n_{u^*} - 1}{|V|} \frac{n_{u^*}}{|G|} \\ + & = \sum_{u^* \in U} \frac{n_{u^*}^2 - n_{u^*}}{|V| |G|} +\end{eqnarray*} + +This is unpleasant, but the following lemma will sort us out. +\begin{lemma} + Let $s_0$, $s_1$, \dots, $s_{n-1}$ be given, such that $\sum_{0 \le i < n} + s_i = t$. Then $\sum_{0 \le i < n} s^2$ is minimum when $s_i = t/n$ for + all $0 \le i < n$. +\end{lemma} +\begin{proof} + The proof is by induction. If $n = 1$, the lemma is obviously true. Let + $s_i$ be given for $0 < i < n + 1$ be given, so that $\sum_i s_i = t$; we + claim that $\sum_i s_i^2$ is minimum when $s_i = t/(n + 1)$ for all $i$. + + Without loss of generality, suppose that $s_n \ge s_i$ for $0 \le i < n$. + Using the induction hypothesis, $\sum_{0\le i]\node{\bf Running\\(send message $\mu$)} ="run" + [d] + *+[F]\node{Deliver message $\mu'$} ="msg" + "msg" :[dll] + *+[F:<6pt>]\node{\bf Complete\\(output key $K$)} + :[d] + *+[F]\node{Expire session} + :[d] + *+[F:<6pt>]\node{\bf Expired} + "msg" :[drr] + *+[F:<6pt>]\node{\bf Aborted\\(no output)} + } + \ar @{->} @<1em> "run"; "msg" + \ar @{->} @<1em> "msg"; "run" + \end{xy} \] +\end{slide} + +\begin{slide} + \head{Key-exchange \seq: model -- SK-security} + + We play a game with the adversary. At the beginning, we choose a `hidden + bit' $b^* \inr \Bin$. + + The adversary can choose a \emph{challenge session} -- any completed, + unexposed session. If $b^* = 1$, we give the adversary the session's key, + just as if it revealed it. If $b^* = 0$, we give the adversary a + freshly-generated random key. + + The adversary may continue to create sessions, deliver messages, etc., but + may not \emph{expose} the challenge session. When it finishes, the + adversary outputs a \emph{guess} $b$. + + A key-exchange protocol $\Pi$ is \emph{SK-secure} if no adversary can + \begin{itemize} + \item with non-negligible probability, cause two matching, unexposed + sessions to \emph{accept}, but output different keys, or + \item with probability non-negligibly greater than $\frac{1}{2}$, guess the + \emph{hidden bit}, i.e., $b = b^*$. + \end{itemize} +\end{slide} + +\begin{slide} + \head{Key-exchange \seq: deniability} + \topic{deniability} + + Many key-exchange protocols use digital signatures. For example: + \begin{protocol} + Alice & Bob \\ + (Private key $\id{sk}_A$, public key $\id{pk}_A$) & + (Private key $\id{sk}_B$, public key $\id{pk}_B$) \\[\medskipamount] + $r_A \getsr \Nupto{|G|}$; & $r_B \getsr \Nupto{|G|}$; \\ + $R_A \gets r_A P$; & $R_B \gets r_B P$; \\ + \send{->}{R_A} + \send{<-}{R_B} + $\sigma_A \gets + S(\id{sk}_A, \texttt{Alice}, \texttt{Bob}, s, R_A, R_B)$; & + \llap{$\sigma_B \gets + S(\id{sk}_B, \texttt{Bob}, \texttt{Alice}, s, R_B, R_A)$;} \\ + \send{->}{\sigma_A} + \send{<-}{\sigma_B} + Check: $V(\id{pk}_B, \sigma_B, \texttt{Bob}, \texttt{Alice}, s, R_B, + R_A)$ + \\ & + \llap{Check: $V(\id{pk}_A, \sigma_A, + \texttt{Alice}, \texttt{Bob}, s, R_A, R_B)$} + \end{protocol} +\end{slide} + +\begin{slide} + \head{Key-exchange \seq: deniability (cont.)} + + Signatures have the property than anyone can verify them. So we could + later prove, to a judge maybe, that Alice and Bob were communicating. + + This is \emph{bad} if you don't want to leave evidence that you were + communicating with someone. + + A key-exchange protocol is \emph{deniable} if there's a simulator which + produces fake transcripts indistinguishable from real conversations + \begin{itemize} + \item \emph{without} being given the private keys of the parties involved, + and + \item even if some of the participants are corrupt. + \end{itemize} +\end{slide} + +\endinput + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "wrslides" +%%% End: diff --git a/ecc.mp b/ecc.mp new file mode 100644 index 0000000..03121fc --- /dev/null +++ b/ecc.mp @@ -0,0 +1,134 @@ +%% Elliptic curve messing about + +%% y^2 = x^3 + a x^2 + b + +numeric u, v; +numeric a, b; +numeric minx, maxx, miny, maxy; +transform gt; +pair O; +%% prologues := 1; +a = -2; b = 1; +scale = 2 cm; +labeloffset := 6 pt; + +ahlength := 2 mm; +ahangle := 30; + +O = (0, 0); + +vardef ecy(expr x) = sqrt (x*x*x + a*x + b) enddef; +vardef ecadd(expr u, v) = + numeric ux, uy, vx, vy; + numeric dx, dy; + numeric m; + ux := xpart u; uy = ypart u; + vx := xpart v; vy = ypart v; + if ux = vx: + m := (3*ux*ux + a)/(2*uy); + else: + m := (vy - uy)/(vx - ux); + fi + dx := m**2 - ux - vx; + dy := m * (ux - dx) - uy; + (dx, dy) +enddef; + +minx = -2; maxx = 3; +maxy = ecy(maxx); miny = -maxy; +u = 7/5 cm; +v = u * (maxx - minx)/(maxy - miny); +gt = identity xscaled u yscaled v shifted (10 cm, 10 cm); + +vardef eclabel@#(expr l, z) = + pickup pencircle scaled 1/4 pt; + draw fullcircle scaled 1 mm shifted (z transformed gt); + draw thelabel@#(l, z transformed gt); +enddef; + +vardef drawcurve = + boolean ok; + path p; + numeric t; + pickup pencircle scaled 1/4 pt; + drawarrow ((minx, 0) -- (maxx, 0)) transformed gt; + drawarrow ((0, miny) -- (0, maxy)) transformed gt; + ok := false; + pickup pencircle scaled 2/3 pt; + for x = minx step 0.01 until maxx: + t := x*x*x + a*x + b; + if t >= 0: + y := sqrt t; + if ok: + p := p .. (x, y); + else: + p := (x, y); + fi + ok := true; + else: + if ok: + draw (reverse p reflectedabout (O, O + right) .. p .. cycle) + transformed gt; + fi + ok := false; + fi + endfor + if ok: + draw (reverse p reflectedabout (O, O + right) .. p) transformed gt; + fi +enddef; + +vardef setbackground(expr c) = + save bboxmargin; + picture pic; + bboxmargin := 1/2 cm; + pic := currentpicture; + currentpicture := nullpicture; + fill (bbox pic) withcolor c; + draw pic; +enddef; + +beginfig(0); + drawcurve; + x0 := -5/4; x1 := 1/4; + y0 := -ecy(x0); y1 := ecy(x1); + z2 = ecadd(z0, z1); + x3 := x2; y3 := -y2; + pickup pencircle scaled 1/4 pt; + draw ((-0.1)[z0, z3] -- 1.1[z0, z3]) transformed gt dashed evenly; + draw ((-0.1)[z2, z3] -- 1.1[z2, z3]) transformed gt dashed evenly; + eclabel.bot(btex $P_0$ etex, z0); + eclabel.top(btex $P_1$ etex, z1); + eclabel.rt(btex $P'$ etex, z3); + eclabel.lft(btex $P_2 = -P' = P_0 + P_1$ etex, z2); + setbackground(white); +endfig; + +beginfig(1); + drawcurve; + x0 := -18/16; + y0 = ecy(x0); + z1 = ecadd(z0, z0); + x2 := x1; y2 := -y1; + pickup pencircle scaled 1/4 pt; + draw ((-0.1)[z0, z2] -- 1.1[z0, z2]) transformed gt dashed evenly; + draw ((-0.1)[z2, z1] -- 1.1[z2, z1]) transformed gt dashed evenly; + eclabel.top(btex $P_0$ etex, z0); + eclabel.rt(btex $P'$ etex, z2); + eclabel.lft(btex $P_1 = -P' = 2 P_0$ etex, z1); + setbackground(white); +endfig; + +beginfig(2); + drawcurve; + x0 := 5/2; + y0 = ecy(x0); + x1 := x0; y1 := -y0; + pickup pencircle scaled 1/4 pt; + draw ((x0, miny) -- (x0, maxy)) transformed gt dashed evenly; + eclabel.rt(btex $P_0$ etex, z0); + eclabel.rt(btex $P_1$ etex, z1); + setbackground(white); +endfig; + +end; diff --git a/wrestlers.tex b/wrestlers.tex new file mode 100644 index 0000000..633a93d --- /dev/null +++ b/wrestlers.tex @@ -0,0 +1,3273 @@ +%%% -*-latex-*- +%%% +%%% The Wrestlers Protocol: secure, deniable key-exchange +%%% +%%% (c) 2006 Mark Wooding +%%% + +\newif\iffancystyle\fancystylefalse +\fancystyletrue +\errorcontextlines=\maxdimen +\showboxdepth=\maxdimen +\showboxbreadth=\maxdimen + +\iffancystyle + \documentclass + [a4paper, article, 10pt, numbering, noherefloats, notitlepage, + runinsubsubsec] + {strayman} + \usepackage[T1]{fontenc} + \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts} + \usepackage[within = subsection, mdwmargin]{mdwthm} + \usepackage{mdwlist} + \usepackage{sverb} + \PassOptionsToPackage{dvips}{xy} +\else + \documentclass[a4paper]{llncs} + \usepackage{a4wide} +\fi + +\PassOptionsToPackage{show}{slowbox} +%\PassOptionsToPackage{hide}{slowbox} +\usepackage{mdwtab, mathenv, mdwmath, crypto} +\usepackage{slowbox} +\usepackage{amssymb, amstext} +\usepackage{url, multicol} +\usepackage{tabularx} +\DeclareUrlCommand\email{\urlstyle{tt}} +\ifslowboxshow + \usepackage[all]{xy} + \turnradius{4pt} +\fi + +\iffancystyle + \def\next{\title[The Wrestlers Protocol]} +\else + \def\next{\title} +\fi +\next + {The Wrestlers Protocol \\ + A simple, practical, secure, deniable protocol for key-exchange} +\iffancystyle + \author{Mark Wooding \\ \email{mdw@distorted.org.uk}} +\else + \author{Mark Wooding} + \institute{\email{mdw@distorted.org.uk}} +\fi + +\iffancystyle + \bibliographystyle{mdwalpha} + \let\epsilon\varepsilon + \let\emptyset\varnothing + \let\le\leqslant\let\leq\le + \let\ge\geqslant\let\geq\ge + \numberwithin{table}{section} + \numberwithin{figure}{section} + \numberwithin{equation}{subsection} + \let\random\$ +\else + \bibliographystyle{plain} + \expandafter\let\csname claim*\endcsname\claim + \expandafter\let\csname endclaim*\endcsname\endclaim +\fi + +\iffancystyle + \newcommand{\Nupto}[1]{\N_{<{#1}}} +\else + \newcommand{\Nupto}[1]{\{0, 1, \ldots, #1 - 1\}} +\fi +\let\Bin\Sigma +\let\emptystring\lambda +\edef\Pr{\expandafter\noexpand\Pr\nolimits} +\newcommand{\bitsto}{\mathbin{..}} +\newcommand{\E}{{\mathcal{E}}} +\newcommand{\M}{{\mathcal{M}}} +\iffancystyle + \def\description{% + \basedescript{% + \let\makelabel\textit% + \desclabelstyle\multilinelabel% + \desclabelwidth{1in}% + }% + } +\fi +\def\fixme#1{\marginpar{FIXME}[FIXME: #1]} +\def\hex#1{\texttt{#1}_{x}} + +\def\dbox#1{% + \vtop{% + \def\\{\unskip\egroup\hbox\bgroup\strut\ignorespaces}% + \hbox{\strut#1}% + }% +} + +\def\Wident{\Xid{W}{ident}} +\def\Wkx{\Xid{W}{kx}} +\def\Wdkx{\Xid{W}{dkx}} +\def\Func#1#2{\mathcal{F}[#1\to#2]} +\def\diff#1#2{\Delta_{#1, #2}} +\def\Hid{H_{\textit{ID}}} + +%% protocol run diagrams +\def\PRaction#1{#1\ar[r]} +\def\PRcreatex#1{\PRaction{\textsf{Create session\space}#1}} +\def\PRcreate#1#2#3{\PRcreatex{(\text{#1},\text{#2},#3)}} +\def\PRreceivex#1{\PRaction{\textsf{Receive\space}#1}} +\def\PRreceive#1#2{\PRreceivex{\msg{#1}{#2}}} +\def\PRsession#1{\relax\mathstrut#1\ar[r]} +\def\msg#1#2{(\cookie{#1},#2)} +\def\PRresult#1{#1} +\def\PRsendx#1{\PRresult{\textsf{Send\space}#1}} +\def\PRsend#1#2{\PRsendx{\msg{#1}{#2}}} +\def\PRcomplete#1{\textsf{Complete:\space}#1} +\def\PRstate#1{\textsf{State:\space}#1} +\def\PRignore{\textsf{(ignored)}} +\def\PRreveal{\textsf{Session-state reveal}\ar[r]} +\def\protocolrun#1{\[\xymatrix @R=0pt @C=2em {#1}\]} + +%% class-ids for proof of extractor lemma +\let\Cid=\Lambda +\let\Csession=S +\let\Cindex=r +\let\Cquery=Q +\let\Chash=H +\let\Ccheck=c +\let\Ccheckset=V +\let\Ccount=\nu + +\begin{document} + +%%%-------------------------------------------------------------------------- + +\maketitle + +\begin{abstract} + We describe and prove (in the random-oracle model) the security of a simple + but efficient zero-knowledge identification scheme, whose security is based + on the computational Diffie-Hellman problem. Unlike other recent proposals + for efficient identification protocols, we don't need any additional + assumptions, such as the Knowledge of Exponent assumption. + + From this beginning, we build a simple key-exchange protocol, and prove + that it achieves `SK-security' -- and hence security in Canetti's Universal + Composability framework. + + Finally, we show how to turn the simple key-exchange protocol into a + slightly more complex one which provides a number of valuable `real-life' + properties, without damaging its security. +\end{abstract} + +\iffancystyle +\newpage +\columnsep=2em \columnseprule=0pt +\tableofcontents[\begin{multicols}{2}\raggedright][\end{multicols}] +%%\listoffigures[\begin{multicols}{2}\raggedright][\end{multicols}] +%% \listoftables[\begin{multicols}{2}\raggedright][\end{multicols}] +\newpage +\fi + +%%%-------------------------------------------------------------------------- + +\section{Introduction} + +%% Blah... +%% Very brief discussion of key-exchange +%% models of secure key exchange +%% mutter about protocol actually being implemented + + + +In this paper, we concern ourselves mainly with \emph{authenticated key + exchange}. That is, we present a system whereby two parties, say Alice and +Bob, can communicate over an insecure channel, and end up knowing a shared +random key unknown to anyone else. \fixme{write the rest of this} + + +\subsection{Asymptotic and concrete security results} + +Most security definitions for identification (particularly zero-knowledge) +and key-exchange in the literature are \emph{asymptotic}. That is, they +consider a family of related protocols, indexed by a \emph{security +parameter}~$k$; they that any \emph{polynomially-bounded} adversary has only +\emph{negligible} advantage. A polynomially-bounded adversary is one whose +running time is a bounded by some polynomial~$t(k)$. The security definition +requires that, for any such polynomially-bounded adversary, and any +polynomial $p(k)$, there is a bound~$n$ such that the adversary's advantage +is less than $p(k)$ for all choices of $k > n$. + +Such asymptotic notions are theoretically interesting, and have obvious +connections to complexity theory. Unfortunately, such an asymptotic result +tells us nothing at all about the security of a particular instance of a +protocol, or what parameter sizes one needs to choose for a given level of +security against a particular kind of adversary. Koblitz and Menezes +\cite{Koblitz:2006:ALP} (among other useful observations) give examples of +protocols, proven to meet asymptotic notions of security, whose security +proofs guarantee nothing at all for the kinds of parameters typically used in +practice. + +Since, above all, we're interested in analysing a practical and implemented +protocol, we follow here the `practice-oriented provable security' approach +largely inspired by Bellare and Rogaway, and exemplified by +\cite{Bellare:1994:SCB, Bellare:1995:XMN, Bellare:1995:OAE, Bellare:1996:ESD, + Bellare:1996:KHF, Bellare:2000:CST}; see also \cite{Bellare:1999:POP}. +Rather than attempting to say, formally, whether or not a protocol is +`secure', we associate with each protocol an `insecurity function' which +gives an upper bound on the advantage of any adversary attacking the protocol +within given resource bounds. + + +\subsection{Desirable properties of our protocols} + +Our identification protocol has a number of desirable properties. +\begin{itemize} +\item It is \emph{simple} to understand and implement. In particular, it + requires only two messages. +\item It is fairly \emph{efficient}, requiring two scalar multiplications by + each of the prover and verifier. +\item It is provably \emph{secure} (in the random oracle model), assuming the + intractability of the computational Diffie-Hellman problem. +\end{itemize} + +Our key-exchange protocol also has a number of desirable properties. +\begin{itemize} +\item It is fairly \emph{simple} to understand and implement, though there + are a few subtleties. In particular, it is \emph{symmetrical}. We have + implemented a virtual private network system based on this protocol. +\item It is \emph{efficient}, requiring four scalar multiplications by each + participant. The communication can be reduced to three messages by + breaking the protocol's symmetry. +\item It is provably \emph{secure} (again, in the random oracle model), + assuming the intractability of the computational Diffie-Hellman problem, + and the security of a symmetric encryption scheme. +\item It provides \emph{perfect forward secrecy}. That is, even if a user's + long-term secrets are compromised, past sessions remain secure. +\item It is \emph{deniable}. It is possible to construct simulated + transcripts of protocol executions between any number of parties without + knowing any of their private keys. The simulated transcripts are (almost) + indistinguishable from real protocol transcripts. Hence, a transcript + does not provide useful evidence that a given party was really involved in + a given protocol execution. +\end{itemize} + + +\subsection{Formal models for key-exchange} + +Many proposed key-exchange protocols have turned out to have subtle security +flaws. Burrows, Abadi and Needham \cite{Burrows:1989:LA} presented a formal +logic for the analysis of authentication and key-exchange protocols. Formal +models for analysing the \emph{computational} security of key-exchange +protocols began with Bellare and Rogaway \cite{Bellare:1994:EAK}, extended in +\cite{Bellare:1995:PSS, Blake-Wilson:1997:KAP, Blake-Wilson:1998:EAA, + Bellare:1998:MAD}. + + + + +\subsection{Outline of the paper} + +The remaining sections of this paper are as follows. +\begin{itemize} +\item Section \ref{sec:prelim} provides the essential groundwork for the rest + of the paper. It introduces important notation, and describes security + notions and intractability assumptions. +\item Section \ref{sec:zk-ident} describes our zero-knowledge identification + protocol and proves its security. +\item Section \ref{sec:kx} describes the simple version of our key-exchange + protocol, and proves its security and deniability. It also describes some + minor modifications which bring practical benefits without damaging + security. +\item Finally, section \ref{sec:...} presents our conclusions. +\end{itemize} + +%%%-------------------------------------------------------------------------- + +\section{Preliminaries} +\label{sec:prelim} + +\subsection{Miscellaneous notation} + +We write $\Func{D}{R}$ for the set of all functions with domain $D$ and range +$R$. +\iffancystyle +We write $\Nupto{n} = \{\, i \in \Z \mid 0 \le i < n \,\} = \{0, 1, \ldots, n +- 1\}$ for the set of nonnegative integers less than $n$. +\fi + + +\subsection{Groups} + +Let $(G, +)$ be a cyclic group\footnote{ + We find that additive group notation is easier to read. In particular, in + multiplicative groups, one ends up with many interesting things tucked away + in little superscripts.}% +of prime order $q$, and generated by an element $P$. We shall write the +identity of $G$ as $0_G$, or simply as $0$ when no ambiguity is likely to +arise. Thus, we have $\langle P \rangle = G$ and $q P = 0$. Any $X \in G$ +can be written as $X = x P$ for some $x \in \Nupto{q}$. + + +\subsection{Bit strings and encodings} +\label{sec:bitenc} + +Let $\Bin = \{0, 1\}$ be the set of binary digits. Then $\Bin^n$ is the set +of $n$-bit strings, and $\Bin^*$ the set of all (finite) bit strings. If $x +\in \Bin^n$ is a bit string, we write its length as $|x| = n$. For a bit +string $x \in \Bin^n$, and for $0 \le i < n$, we write $x[i]$ as the $i$th +bit of $x$. The empty string is denoted $\emptystring$. + +Let $x$ and $y$ be two bit strings. If $|x| = |y| = n$, we write $x \xor y$ +to mean the bitwise exclusive-or of $x$ and $y$: if $z = x \xor y$ then $|z| += n$, and $z[i] = (x[i] + y[i]) \bmod 2$ for $0 \le i < n$. We write $x \cat +y$ to mean the concatenation of $x$ and $y$: if $z = x \cat y$ then $|z| = +|x| + |y|$ and $z[i] = x[i]$ if $0 \le i < |x|$ and $z[i] = y[i - |x|]$ if +$|x| < i \le |x| + |y|$. + +Finally, we let $\bot$ be a value distinct from any bit string. + +We shall want to encode group elements $X \in G$ and indices $x \in I = +\Nupto{|G|}$ as bit strings. To this end, we shall assume the existence of +integers $\ell_G, \ell_I > 0$ and functions +\[ + e_S\colon S \to \Bin^{\ell_S} + \quad \textrm{and} \quad + d_S\colon \Bin^{\ell_S} \to S \cup \{ \bot \} + \qquad + \textrm{for } S \in \{ G, I \}. +\] +with the following properties. +\begin{itemize} +\item The functions are \emph{unique} and \emph{unambiguous}, i.e., for any + $t \in \Bin^{\ell_S}$, we have + \[ d_S(t) = \begin{cases} + s & if there is some $s \in S$ such that $t = e_S(s)$, or \\ + \bot & if no such $s$ exists. + \end{cases} + \] +\item The functions should be \emph{efficient} to compute. Indeed, we shall + be assuming that the time taken for encoding and decoding is essentially + trivial. +\end{itemize} +Note that, as we have defined them, all encodings of group elements are the +same length, and similarly for encodings of indices. This is necessary for +the security of our protocols. + +We shall frequently abuse notation by omitting the encoding and decoding +functions where it is obvious that they are required. + + +\subsection{Games, adversaries, and oracles} +\label{sec:games} + +Many of the security definitions and results given here make use of +\emph{games}, played with an \emph{adversary}. An adversary is a +probabilistic algorithm. In some games, the adversary is additionally +equipped with \emph{oracles}, which perform computations with values chosen +by the adversary and secrets chosen by the game but not revealed to the +adversary. We impose limits on the adversary's resource usage: in +particular, the total time it takes, and the number of queries it makes to +its various oracles. Throughout, we include the size of the adversary's +program as part of its `time', in order to model adversaries which contain +large precomputed tables. + +The games provide models of someone trying to attack a construction or +protocol. For security, we will either define a notion of `winning' the +game, and require that all adversaries have only a very small probability of +winning, or we consider two different games and require that no adversary can +distinguish between the two except with very small probability. + +Our proofs make frequent use of sequences of games; see +\cite{Shoup:2004:SGT,Bellare:2004:CBG}. The presentation owes much to Shoup +\cite{Shoup:2004:SGT}. We begin with a game $\G0$ based directly on a +relevant security definition, and construct a sequence of games $\G1$, $\G2$, +\dots, each slightly different from the last. We define all of the games in +a sequence over the same underlying probability space -- the random coins +tossed by the algorithms involved -- though different games may have slightly +differently-defined events and random variables. Our goal in doing this is +to bound the probability of the adversary winning the initial game $\G0$ by +simultaneously (a) relating the probability of this event to that of +corresponding events in subsequent games, and (b) simplifying the game until +the probability of the corresponding event can be computed directly. + +The following simple lemma from \cite{Shoup:2001:OR} will be frequently +useful. +\begin{lemma}[Difference Lemma] + \label{lem:shoup} + Let $S$, $T$, $F$ be events. Suppose $\Pr[S|\bar F] = \Pr[T|\bar F]$. + Then $|\Pr[S] - \Pr[T]| \le \Pr[F]$. +\end{lemma} +\begin{proof} + A simple calculation: + \begin{eqnarray*}[rl] + |\Pr[S] - \Pr[T]| + & = |(\Pr[S|F]\Pr[F] + \Pr[S|\bar F]\Pr[\bar F]) - + (\Pr[T|F]\Pr[F] + \Pr[T|\bar F]\Pr[\bar F])| \\ + & = \Pr[F] \cdot |\Pr[S|F] - \Pr[T|F]| \\ + & \le \Pr[F] + \end{eqnarray*} + and we're done! +\end{proof} + + +\subsection{The random oracle model} +\label{sec:ro} + +In particular, most of our results will make use of the \emph{random oracle} +model \cite{Bellare:1993:ROP}, in which all the participants, including the +adversary, have access to a number of `random oracles'. A random oracle with +domain $D$ and range $R$ is an oracle which computes a function chosen +uniformly at random from the set of all such functions. (In the original +paper \cite{Bellare:1993:ROP}, random oracles are considered having domain +$\Bin^*$ and range $\Bin^\omega$; we use finite random oracles here, because +they're easier to work with.) + +Given a protocol proven secure in the random oracle model, we can instantiate +each random oracle by a supposedly-secure hash function and be fairly +confident that either our protocol will be similarly secure, or one of the +hash functions we chose has some unfortunate property. + +Proofs in the random oracle must be interpreted carefully. For example, +Canetti, Goldreich and Halevi \cite{Canetti:2004:ROM} show that there are +schemes which can be proven secure in the random oracle model but provably +have no secure instantiation in the standard model. + +The random oracle model is useful for constructing reductions and simulators +for two main reasons. +\begin{enumerate} +\item One can use the transcript of an adversary's queries to random oracles + in order to extract knowledge from it. +\item One can `program' a random oracle so as to avoid being bound by prior + `commitments', or to guide an adversary towards solving a selected instance + of some problem. +\end{enumerate} +Our proofs only make use of the first feature. This becomes particularly +important when we consider issues of zero-knowledge and deniability in a +concurrent setting, because we want to be able to claim that we retain these +features when the random oracle is instantiated using a cryptographic hash +function, and hash functions definitely aren't `programmable' in this way! +The former property seems rather more defensible -- one would indeed hope +that the only sensible way of working out (anything about) the hash of a +particular string is to actually compute the hash function, and the random +oracle model is, we hope, just giving us a `hook' into this process. + +(Our protocols can be modified to make use of bilinear pairings so as to +provide identity-based identification and key-exchange, using the techniques +of \cite{Boneh:2001:IBE}. Proving the security of the modifications we +discuss would involve `programming' random oracles, but this doesn't affect +the zero-knowledge or deniability of the resulting protocols.) + + +\subsection{Notation for algorithms} + +We shall have occasion to describe algorithms by means of a pseudocode. Our +choice of pseudocode is unlikely to be particularly controversial. We let $x +\gets y$ denote the action of setting $x$ to the value $y$; similarly, $x +\getsr Y$ denotes the action of sampling $x$ from the set $Y$ uniformly at +random. + +The expression $a \gets A^{O(\cdot, x)}(y)$ means `assign to $a$ the value +output by algorithm $A$ on input $y$, and with oracle access to the algorithm +which, given input $z$, computes $O(z, x)$'. + +We make use of conditional (\IF-\ELSE) and looping (\FOR-\DO and \WHILE-\DO) +constructions; in order to reduce the amount of space taken up, the bodies of +such constructions are shown by indentation only. + +We don't declare the types of our variables explicitly, assuming that these +will be obvious by inspection; also, we don't describe our variables' scopes +explicitly, leaving the reader to determine these from context. + +Finally, the notation $\Pr[\textit{algorithm} : \textit{condition}]$ denotes +the probability that \textit{condition} is true after running the given +\textit{algorithm}. + + +\subsection{Diffie-Hellman problems} +\label{sec:dhp} + +The security of our protocols is related to the hardness of the +computational, decisional, and gap Diffie-Hellman problems in the group $G$. +We define these problems and what it means for them to be `hard' here. + +The \emph{computational} Diffie-Hellman problem (CDH) is as follows: given +two group elements $X = x P$ and $Y = y P$, find $Z = x y P$. +\begin{definition}[The computational Diffie-Hellman problem] + Let $(G, +)$ be a cyclic group generated by $P$. For any adversary $A$, we + say that $A$'s \emph{success probability} at solving the computational + Diffie-Hellman problem in $G$ is + \[ \Succ{cdh}{G}(A) = + \Pr[ x \getsr I; y \getsr \Nupto{|G|} : A(x P, y P) = x y P ] + \] + where the probability is taken over the random choices of $x$ and $y$ and + any random decisions made by $A$. We say that the \emph{CDH insecurity + function} of $G$ is + \[ \InSec{cdh}(G; t) = \max_A \Succ{cdh}{G}(A) \] + where the maximum is taken over adversaries which complete in time $t$. +\end{definition} +Certainly, if one can compute discrete logarithms in the group $G$ (i.e., +given $x P$, find $x$), then one can solve the computational Diffie-Hellman +problem. The converse is not clear, though. Shoup \cite{Shoup:1997:LBD} +gives us some confidence in the difficulty of the problem by showing that a +\emph{generic} adversary -- i.e., one which makes no use of the specific +structure of a group -- has success probability no greater than $q^2/|G|$. + +This isn't quite sufficient for our purposes. Our proofs will be able to +come up with (possibly) a large number of guesses for the correct answer, and +at most one of them will be correct. Unfortunately, working out which one is +right seems, in general, to be difficult. This is the \emph{decision} +Diffie-Hellman problem (DDH), which \cite{Shoup:1997:LBD} shows, in the +generic group model, is about as hard as CDH. (See \cite{Boneh:1998:DDP} for +a survey of the decision Diffie-Hellman problem.) + +Our reference problem will be a `multiple-guess computational Diffie-Hellman +problem' (MCDH), which is captured by a game as follows. An adversary is +given a pair of group elements $(x P, y P)$, and an oracle $V(\cdot)$ which +accepts group elements as input. The adversary wins the game if it queries +$V(x y P)$. +\begin{definition}[The multiple-guess computational Diffie-Hellman problem] + \label{def:mcdh} + Let $(G, +)$ be a cyclic group generated by $P$. For some adversary $A$, + we say that $A$'s \emph{success probability} at solving the multiple-guess + computational Diffie-Hellman problem in $G$ is + \[ \Succ{mcdh}{G}(A) = \Pr[\Game{mcdh}{G}(A) = 1] \] + where $\Game{mcdh}{G}(A)$ is shown in figure~\ref{fig:mcdh}. We say that + the \emph{MCDH insecurity function of $G$} is + \[ \InSec{mcdh}(G; t, q_V) = \max_A \Succ{mcdh}{G}(A) \] + where the maximum is taken over adversaries which complete in time $t$ and + make at most $q_V$-oracle queries. +\end{definition} + +\begin{figure} + \begin{program} + $\Game{mcdh}{G}(A)$: \+ \\ + $w \gets 0$; \\ + $x \getsr \Nupto{|G|}$; $y \getsr \Nupto{|G|}$; \\ + $A^{V(\cdot)}(x P, y P)$; \\ + \RETURN $w$; + \next + Function $V(Z)$: \+ \\ + \IF $Z = x y P$ \THEN \\ \ind + $w \gets 1$; \\ + \RETURN $1$; \- \\ + \RETURN $0$; + \end{program} + + \caption{The multiple-guess computational Diffie-Hellman problem: + $\Game{mcdh}{G}(A)$} + \label{fig:mcdh} +\end{figure} + +Note that our MCDH problem is not quite the `gap Diffie-Hellman problem' +(GDH). The gap problem measures the intractibility of solving CDH even with +the assistance of an oracle for solving (restricted) decision Diffie-Hellman +problems in the group. Specifically, the adversary is given $(X, Y) = (x P, +y P)$ and tries to find $Z = x y P$, as for CDH, but now it has access to an +oracle $D(R, S)$ which answers $1$ if $S = x R$ and $0$ otherwise. + +Clearly MCDH is at least as hard as GDH, since our simple verification oracle +$V(Z)$ can be simulated with the gap problem's DDH oracle, as $D(Y, Z)$. +However, we can (loosely) relate the difficulty of MCDH to the difficulty of +CDH. +\begin{proposition}[Comparison of MCDH and CDH security] + For any cyclic group $(G, +)$, + \[ \InSec{mcdh}(G; t, q_V) \le q_V\cdot\InSec{cdh}(G; t + O(q_V)). \] +\end{proposition} +\begin{proof} + Let $A$ be an adversary attacking the multiple-guess computational + Diffie-Hellman problem in $G$, and suppose that it runs in time $t$ and + issues $q_V$ queries to its verification oracle. + + We use a sequence of games. Game $\G0$ is the original MCDH attack game. + In each game $\G{i}$, we let the event $S_i$ be the probability that the + adversary wins the game. + + Game $\G1$ is the same as $\G0$, except that we change the behaviour of the + verification oracle. Specifically, we make the oracle always return $0$. + We claim that this doesn't affect the adversary's probability of winning, + i.e., $\Pr[S_1] = \Pr[S_0]$. To see this, note that if none of the + adversary's $V(\cdot)$ queries was correct, then there is no change in the + game; conversely, if any query was correct, then the adversary will have + won regardless of its subsequent behaviour (which may differ arbitrarily + between the two games). + + We are now ready to construct from $A$ an adversary $B$ attacking the + standard computational Diffie-Hellman problem. + \begin{program} + Adversary $B(X, Y)$: \+ \\ + $n \gets 0$; \\ + \FOR $i \in \Nupto{q_V}$ \DO $Q_i \gets 0$; \\ + $A^{V(\cdot)}$; \\ + $r \getsr \Nupto{n}$; \\ + \RETURN $Q_r$; + \next + Function $D(Z')$: \+ \\ + $Q_n \gets Z'$; \\ + $n \gets n + 1$; \\ + \RETURN $0$; + \end{program} + Observe that $B$ provides $A$ with an accurate simulation of game $\G1$. + Moreover, at the end of the algorithm, we have $0 < n \le q_V$, the + output of $A$ is stored in $Q_{n-1}$ and the values $Q_0$, $Q_1$, \dots, + $Q_{n-1}$ are the values of $A$'s oracle queries. Hence, with probability + $Pr[S_1]$, at least of one of the $Q_i$ is the correct answer to the CDH + problem. Let $\epsilon = \Pr[S_1] = \Pr[S_0]$; we claim that $B$'s + probability of success is at least $\epsilon/q_V$. The proposition + follows directly from this claim and that, because $A$ was chosen + arbitrarily, we can maximize and count resources. + + We now prove the above claim. For $0 \le i < q_V$, let $W_i$ be the + event that $Q_i = x y P$, i.e., that $Q_i$ is the correct response. A + simple union bound shows that + \[ \sum_{0\le i +p$, we can encode $n$ as $e(p, \ell_G, n)$, as above. + +Alternatively, let $\F = \gf{p^f}$ be a finite field, and $E$ be an elliptic +curve defined over $\F$ such that the group $E(\F)$ of $\F$-rational points +of $E$ has a prime-order cyclic subgroup $G$. Elements of $G$ can be +represented as pairs of elements of $\F$. If $f = 1$, i.e., $\F = \Z/p\Z$ +then field elements can be encoded as above. If $p = 2$, we can represent +the field as $\F_2/(p(x))$ for some irreducible polynomial $p(x) \in \F_2[x]$ +of degree $f$. An element $r \in \F$ can then be represented by a polynomial +$r(x)$ with degree less than $f$, and coefficients $c_i \in \{0, 1\}$, i.e., +\[ r(x) = \sum_{0\le i 4$. However, in +the Schnorr groups used by Stinson and Wu, the cofactor is much larger than +$q$, and their new variant is more efficient.) + +We note that the zero-knowledge property of the Stinson-Wu protocol requires +the Diffie-Hellman knowledge of exponent assumption (KEA). Very briefly: +suppose $A$ is a randomized algorithm which takes as input $X \in G$ and +outputs a pair $(r P, r X)$; intuitively, the KEA asserts $A$ must have done +this by choosing $r$ somehow and then computing its output from it. +Formally, it asserts the existence of an `extractor' algorithm which takes as +input the element $X$ and the random coins used by $A$ and outputs $r$ with +high probability. This is a very strong assumption, and one which is +unnecessary for our protocol, since we can present an \emph{explicit} +extractor. + +The KEA assumption as stated in \cite{Stinson:2006:EST} allows the extractor +to fail with some negligible probability, over and above the probability that +a dishonest verifier managed to guess the correct $h = H(\rho, \psi)$ without +making this random-oracle query. Not only does our protocol achieve zero- +knowledge without the KEA, our extractor is, in this sense, `perfect'. + +Our protocol is just as strong as Stinson-Wu under attack from active +intruders: see table~\ref{tab:wident-active} for a very brief sketch of the +case-analysis which would be the basis of a proof of this. + +\begin{table} + \begin{tabular}[C]{|*{3}{c|}p{8cm}|} + \hlx{hv[1]} + \multicolumn{2}{|c|}{\textbf{Challenge}} & + \textbf{Response} & + \textbf{Security} + \\ \hlx{v[1]hv} + %% unpleasant hacking to make the R and c columns the same width :-( + \settowidth{\dimen0}{\textbf{Challenge}}% + \dimen0=.5\dimen0 + \advance\dimen0by-\tabcolsep + \advance\dimen0by-.5\arrayrulewidth + \hbox to\dimen0{\hfil$R$\hfil} + & $c$ & $Y$ & Nothing to prove. \\ \hlx{v} + $R$ & $c'$ & --- & Prover rejects by lemma~\ref{lem:unique-c}; + $Y'$ probably wrong by + theorem~\ref{thm:wident-sound}. \\ \hlx{v} + $R$ & $c$ & $Y'$ & Response is incorrect. \\ \hlx{v} + $R'$ & --- & $Y$ & Response is incorrect. \\ \hlx{v} + $R'$ & $c$ & $Y'$ & Prover rejects with probability $1 - 2^{-\ell_I}$; + $Y'$ probably wrong by + theorem~\ref{thm:wident-sound}. \\ \hlx{v} + $R'$ & $c'$ & $Y'$ & Simulate prover using extractor + (lemma~\ref{lem:dlext}); $Y'$ probably wrong by + theorem~\ref{thm:wident-sound}. \\ \hlx{vh} + \end{tabular} + + \caption{Security of $\Wident$ against active intruders (summary)} + \label{tab:wident-active} +\end{table} + +An identity-based analogue of Stinson-Wu can be defined using a bilinear +pairing, just as we did in section~\ref{sec:wident-id}. However, to prove +the zero-knowledge property, one needs to make a bilinear analogue of the +knowledge of exponent assumption. + +We suspect that a key-exchange protocol like ours can be constructed using +Stinson-Wu rather than the Wrestlers identification scheme. We haven't, +however, gone through all the details, since we believe our protocol is just +as efficient and is based on much more conservative assumptions. + +%%%-------------------------------------------------------------------------- + +\section{A simple key-exchange protocol} +\label{sec:kx} + +In this section, we describe a simple key-exchange protocol built out of the +identification protocol shown previously. + +The key-exchange protocol arises from the following observation. If Bob +sends a challenge, presumably to Alice, and gets a correct response, then not +only did he really send the challenge to Alice but he knows that she received +it correctly. + +So, if Alice and Bob authenticate each other, by the end of it, they should +each have chosen a random private value, sent the corresponding public value +to the other, and been convinced that it arrived safely. + +Unfortunately, life isn't quite this kind, and we have to do some more work +to make this scheme secure. + + +Our key exchange protocol essentially consists of two parallel instances of +the identification protocol. If Alice receives a correct response to her +challenge, she will know that Bob received her challenge correctly, and +\emph{vice versa}. If we let Alice's challenge be $R_0 = r_0 P$ and Bob's +challenge be $R_1 = r_1 P$ then each can compute a shared secret $Z = r_0 R_1 += r_0 r_1 P = r_1 R_0$ unknown to an adversary. There are, unfortunately, a +few subtleties involved in turning this intuition into a secure key-exchange +protocol, which we now describe. + + +\subsection{Overview} +\label{sec:kx-overview} + +We present a quick, informal description of our basic key-exchange protocol. +In addition to our group $G$, we shall also need a secure symmetric +encryption scheme $\E = (\kappa, E, D)$, and two secure hash functions +$H_I\colon \Bin^{2\ell_G} \to \Bin^{\ell_I}$ and $H_K\colon \Bin^{\ell_G+1} +\to \Bin^\kappa$. + +Suppose that Alice's and Bob's private keys are $a$ and $b$ respectively, and +their public keys are $A = a P$ and $B = b P$. +\begin{enumerate} +\item Alice chooses a random index $r \inr \Nupto{|G|}$. She computes $R = r + P$ and $c = r \xor H_I(R, r B)$. She sends the pair $(R, c)$ to Bob. +\item Similarly, Bob chooses a random $s \inr \Nupto{|G|}$. He computes $S + = s P$ and $d = s \xor H_I(S, s A)$. He sends $(S, d)$ to Alice. +\item Alice receives $(S', d')$ from Bob. She computes $s' = d' \xor H_I(S', + a S')$, and verifies that $S' = s' P$. If so, she computes $K_A = H_K(0 + \cat r S')$, and sends $R, E_{K_A}(a S')$ to Bob. +\item Similarly, Bob receives $(R', c')$ from Alice. He verifies that $R' = + \bigl( c' \xor H_I(R', b R') \bigr) P$. If so, he computes $K_B = H_K(0 + \cat s R')$ and sends S, $E_{K_B}(b R')$ to Alice. +\item Alice receives a ciphertext $(S'', \chi_B)$ from Bob. She checks that + $S'' = S'$, decrypts $\chi_B$, and checks that $D_{K_A}(\chi_B) = r B$. If + so, she uses $H_K(1 \cat r S')$ as her shared secret. +\item Similarly, Bob receives $(R'', \chi_A)$ from Alice, and checks $R'' = + R'$ and $D_{K_B}(\chi_A) = s A$. If so, he uses $H_K(1 \cat s R')$ as his + shared secret. +\end{enumerate} +This is the Wrestlers Key Exchange protocol, $\Wkx^{G, \E}$ (again, we omit +the superscripts when referring to the general protocol, or when confusion is +unlikely). A diagrammatic summary of the protocol is shown in +figure~\ref{fig:wkx}. + +\begin{figure} + \begin{description} + \item[Setup] Group $G = \langle P \rangle$; $|G| = q$ is prime. + $H_I(\cdot, \cdot)$ and $H_K(\cdot)$ are secure hashes. $\E = (\kappa, + E, D)$ is an IND-CCA2 symmetric encryption scheme. + \item[Parties] $U_i$ for $0 \le i < n$. + \item[Private keys] $x_i \inr \Nupto{q}$. + \item[Public keys] $X_i = x_i P$. + \end{description} + \[ \begin{graph} + !{0; <8cm, 0cm>: <0cm, 3cm>::} + *+[F]\dbox{$r_i \getsr I$; $R_i \gets r_i P$ \\ + $c_i \gets r_i \xor H_I(R_i, r_i X_j)$} ="i0" + [d] + *+[F]\dbox{Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$ \\ + $Z \gets r_i R_j$; $K \gets H_K(0, Z)$ \\ + $\chi_i \gets E_K(x_i R_j)$} ="i1" + [d] + *+[F]\dbox{Check $D_K(\chi_j) = r_i X_j$ \\ + Shared key is $H_K(1, Z)$} ="i2" + "i0" [r] + *+[F]\dbox{$r_j \getsr I$; $R_j \gets r_j P$ \\ + $c_j \gets r_j \xor H_I(R_j, r_j X_i)$} ="j0" + [d] + *+[F]\dbox{Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$ \\ + $Z \gets r_j R_i$; $K \gets H_K(0, Z)$ \\ + $\chi_j \gets E_K(x_j R_i)$} ="j1" + [d] + *+[F]\dbox{Check $D_K(\chi_i) = r_j X_i$ \\ + Shared key is $H_K(1, Z)$} ="j2" + % + "i0" : |(0)/3.25cm/*+{(R_i, c_i)} "j1" + "i1" : |(0)/3.25cm/*+{(R_i, \chi_i)} "j2" + "j0" : |(0)/3.25cm/*+{(R_j, c_j)} "i1" + "j1" : |(0)/3.25cm/*+{(R_j, \chi_j)} "i2" + \end{graph} \] + + \caption{Summary of the Wrestlers Key Exchange protocol, $\Wkx$} + \label{fig:wkx} +\end{figure} + +Assume, for the moment, that Alice and Bob's messages are relayed honestly. +Then: +\begin{itemize} +\item $a S' = a S = a (s P) = s (a P) = s A$, so $s' = d' \xor H_I(S' a S') = + d \xor H_I(S, s A) = s$, and $S' = S = s P = s' P$, and therefore Alice + responds to Bob's message; +\item similarly $b R' = r B$, so $r' = r$ and $R' = r' P$, and therefore Bob + responds to Alice's message; +\item $b R' = b R = b (r P) = r (b P) = r B$, and $a S' = a S = a (s P) = s + (a P) = s A$, and therefore both parties compute their responses correctly; + and +\item $r S' = r S = r (s P) = s (r P) = s R = s R'$, so $K_A = K_B$, and + therefore they can decrypt each others' responses, and agree the same + shared secret. +\end{itemize} +This shows that the protocol is basically valid, but says little about its +security. The remainder of this section will describe our protocol in more +formal detail, and prove its security in a model with multiple parties and an +adversary who controls the network. + +Observe that the protocol as we've presented here is \emph{symmetrical}. +There's no notion of `initiator' or `responder'. There are a total of four +messages which must be sent before both parties accept. However, this can be +reduced to three by breaking the symmetry of the protocol and combining one +or other party's challenge and response messages. We choose to analyse the +symmetrical version, since to do so, it suffices to consider only the two +different kinds of messages. Since our security model allows the messages to +be adversarially delayed and reordered, it is easy to show that the security +of an optimized, asymmetrical protocol is no worse than the symmetrical +version we present here. + + +\subsection{Security model and security definition} +\label{sec:um} + +Our model is very similar to that of Canetti and Krawczyk +\cite{Canetti:2002:???}, though we have modified it in two ways. +\begin{enumerate} +\item We allow all the participants (including the adversary) in the protocol + access to the various random oracles required to implement it. +\item Since we want to analyse a specific, practical scheme, asymptotic + results are useless. We measure the adversary's resource usage carefully, + and produce a quantitative bound on the adversary's advantage in the + SK-security game. +\end{enumerate} + +\subsubsection{Overview} +We briefly describe our modified model, pointing out the changes we have +made, and how they apply to our protocol. Much of Canetti and Krawczyk's +model (for example, the local and global outputs) is useful for proving more +general security properties such as demonstrating that SK-security suffices +for constructing secure channels, and we shall not concern ourselves with +such details. Other parts deal with issues such as security parameters and +ensuring that all the computation is polynomially bounded, which are +irrelevant since we are dealing with a single concrete protocol rather than a +family of them. + +The entities in the model are the \emph{adversary}~$A$, and a (fixed) number +of \emph{parties}~$P_i$, for $0 \le i < n$. If the protocol under +consideration makes use of random oracles, then all the participants -- the +adversary and the parties -- are all allowed access to the random oracles. + +The parties and the adversary play a `game'. At the beginning of the game, +the participants are given some inputs computed by a randomized +\emph{initialization procedure}~$\id{init}$. This produces as output a pair +$(i_U, \mathbf{i})$; the value $i_U$ is the \emph{global input}, and is given +to all the participants including the adversary. The vector $\mathbf{i}$ has +$n$ components, and party $P_i$ is given $(i_U, \mathbf{i}[i])$ as input. + +\subsubsection{Sessions} +Parties don't act directly. Instead, each party runs a number of +\emph{sessions}. A session a triple $S = (P_i, P_j, s)$, where $i, j \in +\Nupto{n}$ identify the owning party and a \emph{partner}, and $s \in +\Bin^{\ell_S}$ is a \emph{session-id}. (The original model includes a +r\^ole, for distinguishing between initiators and responders. Our protocol +is symmetrical, so this distinction isn't useful.) If $P_i$ runs a session +$S = (P_i, P_j, s)$ and $P_j$ runs a session $S' = (P_j, P_i, s)$ then we say +that $S$ and $S'$ are \emph{matching}, and that $P_j$ is $P_i$'s +\emph{partner} for the session. + +At most one participant in the game is \emph{active} at any given time. +Initially the adversary is active. The adversary may \emph{activate} a +session in one of two ways. +\begin{enumerate} +\item It may \emph{create a session} of a party~$P_i$, by selecting a + session-id~$s \in \Bin^{\ell_S}$ and a partner $j$. There is no + requirement that $P_j$ ever have a matching session. However, all sessions + of a party must be distinct, i.e., sessions with the same partner must have + different session-ids. +\item It may \emph{deliver a message}~$\mu \in \Bin^*$, from party~$P_j$, to + an existing session~$S = (P_i, P_j, s)$. There is no requirement that any + party previously sent $\mu$: the adversary is free to make up messages as + it sees fit. +\end{enumerate} +The adversary becomes inactive, and the session becomes active. The session +performs some computation, according to its protocol, and may request a +message~$\mu$ be delivered to the matching session running in its partner +(which may not exist). The session may also \emph{terminate}. In the case +we are interested in, of key-exchange protocols, a session~$S = (P_i, P_j, +s)$ may terminate in one of two ways: +\begin{enumerate} +\item it may \emph{complete}, outputting $(i, j, s, K)$, for some + \emph{session key}~$K$, or +\item it may \emph{abort}, outputting $(i, j, s, \bot)$. +\end{enumerate} +Once it has performed these actions, the session deactivates and the +adversary becomes active again. The adversary is given the message~$\mu$, if +any, and informed of whether the session completed or aborted, but, in the +case of completion, not of the value of the key~$K$. A session is +\emph{running} if it has been created and has not yet terminated. + +\subsubsection{Other adversarial actions} +As well as activating sessions, the adversary has other capabilities, as +follows. +\begin{itemize} +\item It may \emph{expire} any session~$S$, causing the owning party to + `forget' the session key output by that session. +\item It may \emph{corrupt} any party~$P_i$, at will: the adversary learns + the entire state of the corrupted party, including its initial + input~$\mathbf{i}[i]$, the state of any sessions it was running at the + time, and the session keys of any completed but unexpired sessions. Once + corrupted, a party can no longer be activated. Of course, the adversary + can continue to send messages allegedly from the corrupted party. +\item It may \emph{reveal the state} of a running session~$S$, learning any + interesting values specific to that session, but \emph{not} the owning + party's long-term secrets. +\item It may \emph{reveal the session-key} of a completed session~$S$. +\item It may elect to be \emph{challenged} with a completed session~$S$, + provided. Challenge sessions form part of the security notion for + key-exchange protocols. See below for more details. +\end{itemize} +We say that a session $S = (P_i, P_j, s)$ is \emph{locally exposed} if +\begin{itemize} +\item it has had its state revealed, +\item it has had its session-key revealed, or +\item $P_i$ has been corrupted, and $S$ had not been expired when this + happened. +\end{itemize} +A session is \emph{exposed} if it is locally exposed, or if its matching +session exists and has been locally exposed. + +At the beginning of the game, a bit $b^*$ is chosen at random. The adversary +may choose to be \emph{challenged} with any completed, unexposed +session;\footnote{% + The original Canetti-Krawczyk definition restricts the adversary to a + single challenge session, but our proof works independent of the number of + challenge sessions, so we get a stronger result by relaxing the requirement + here.)} +the adversary is then given either the session's key -- if $b^* = 1$ -- or a +string chosen at random and independently of the game so far from a +protocol-specific distribution -- if $b^* = 0$. At the end of the game, the +adversary outputs a single bit~$b$. + +\subsubsection{SK-security} +We've now described the game; it is time to explain the adversary's goal in +it. The adversary \emph{wins} the game if either +\begin{enumerate} +\item two unexposed, matching sessions complete, but output different + keys,\footnote{% + The original Canetti-Krawczyk definition differs slightly here. It + requires that `if two \emph{uncorrupted} parties complete matching + sessions then they both output the same key' [original emphasis]. This + can't be taken at face value, since none of the protocols they claim to + be secure actually meet this requirement: they meet only the weaker + requirement that parties completing matching sessions output different + keys with negligible probability. We assume here that this is what they + meant.} + or +\item the adversary correctly guesses the hidden bit~$b^*$. +\end{enumerate} +More formally, we make the following definition. +\begin{definition}[SK-security] + \label{def:sk} + Let $\Pi^{H_0(\cdot), H_1(\cdot), \ldots}$ be a key-exchange protocol + which makes use of random oracles $H_0(\cdot)$, $H_1(\cdot)$, \dots, and + let $A$ be an adversary playing the game described previously, where $n$ + parties run the protocol~$\Pi$. Let $V$ be the event that any pair of + matching, unexposed sessions completed, but output different session keys. + Let $W$ be the event that the adversary's output bit matches the game's + hidden bit~$b^*$. We define the adversary's \emph{advantage against the + SK-security of the protocol~$\Pi$} to be + \[ \Adv{sk}{\Pi}(A, n) = \max(\Pr[V], 2\Pr[W] - 1). \] + Furthermore, we define the \emph{SK insecurity function of the + protocol~$\Pi$} to be + \[ \InSec{sk}(\Pi; t, n, q_S, q_M, q_{H_0}, q_{H_1}, \dots) = + \max_A \Adv{sk}{\Pi}(A, n) + \] + where the maximum is taken over all adversaries~$A$ with total running + time~$t$ (not including time taken by the parties), create at most $q_S$ + sessions, deliver at most $q_M$~messages, and (if applicable) make at most + $q_{H_i}$ random-oracle queries to each random oracle $H_i(\cdot)$. +\end{definition} + + +\subsection{Security} + +In order to analyse our protocol $\Wkx^{G, \E}$ properly, we must describe +exactly how it fits into the formal model described in our formal model. + +\subsubsection{Sessions and session-ids} +Our formal model introduced the concept of sessions, which the informal +description of section~\ref{sec:kx-overview} neglected to do. (One could +argue that we described a single session only.) As we shall show in +section~\ref{sec:kx-insecure}, our protocol is \emph{insecure} unless we +carefully modify it to distinguish between multiple sessions. + +In the model, distinct key-exchange sessions are given distinct partners and +session-ids. In order to prevent sessions interfering with each other, we +shall make explicit use of the session-ids. + +Suppose the session-ids are $\ell_S$-bit strings. We expand the domain of +the random oracle $H_I$ so that it's now +\[ H_I\colon G \times \Bin^{\ell_S} \times G \times G \to \Bin_{\ell_I}. \] + +\subsubsection{Messages} +We split the messages our protocols into two parts: a \emph{type}~$\tau$ and +a \emph{body}~$\mu$. We assume some convenient, unambiguous encoding of +pairs $(\tau, \mu)$ as bit-strings. For readability, we present message +types as text strings, e.g., `\cookie{challenge}', though in practice one +could use numerical codes instead. + +The message body itself may be a tuple of values, which, again, we assume are +encoded as bit-strings in some convenient and unambiguous fashion. We shall +abuse the notation for the sake of readability by dropping a layer of nesting +in this case: for example, we write $(\cookie{hello}, x, y, z)$ rather than +$\bigl(\cookie{hello}, (x, y, z)\bigr)$. + +\subsubsection{The protocol} +Our protocol is represented by three functions, shown in +figure~\ref{fig:wkx-formal}. +\begin{itemize} +\item $\id{init}(n)$ is the initialization function, as described in + section~\ref{sec:um}. It outputs a pair $(\mathbf{p}, \mathbf{i})$, where + $\mathbf{i}[i]$ is the private key of party~$P_i$ and $\mathbf{p}[i]$ is + the corresponding public key. Only $P_i$ is given $\mathbf{i}[i]$, whereas + all parties and the adversary are given $\mathbf{p}$. +\item $\id{new-session}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\mathbf{p}, x, i, j, s)$ is the new-session function. This is executed by + party~$P_i$ when the adversary decides to create a new session~$S = (P_i, + P_j, s)$. It is also given the relevant outputs of $\id{init}$, and + allowed access to the random oracles $H_I$ and $H_K$. +\item $\id{message}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)} (\tau, + \mu)$ is the incoming-message function. This is executed by a session when + the adversary decides to deliver a message $(\tau, \mu)$ to it. It makes + use of the subsidiary functions $\id{msg-challenge}$ and + $\id{msg-response}$ to handle the messages. +\end{itemize} +We observe that the protocol never aborts. We could make it do so if it +receives an invalid message, but we prefer to ignore invalid messages for the +sake of robustness.\footnote{% + Note that this protocol would therefore require modification before it was + acceptable in the simulation-based model of \cite{Shoup:1999:OFM}. There + it is required that a key-exchange protocol terminate after a + polynomially-bounded number of messages are delivered to it.} + +\begin{figure} + \begin{program} + Function $\id{init}(n)$: \+ \\ + \FOR $i \in \Nupto{n}$ \DO \\ \ind + $x \getsr \Nupto{|G|}$; \\ + $\mathbf{i}[i] \gets x$; \\ + $\mathbf{p}[i] \gets x P$; \- \\ + \RETURN $(\mathbf{p}, \mathbf{i})$; + \- \\[\medskipamount] + Function $\id{new-session}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\mathbf{p}, x, i, j, s)$: \+ \\ + $X \gets \mathbf{p}[i]$; + $X' \gets \mathbf{p}[j]$; + $C \gets \emptyset$; \\ + $r \getsr \Nupto{|G|}$; + $R \gets r P$; + $Y \gets r X'$; \\ + $h \gets H_I(X, s, R, Y)$; + $c \gets r \xor h$; \\ + \SEND $(\cookie{challenge}, R, c)$; + \- \\[\medskipamount] + Function $\id{message}^{H_I(\cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\tau, \mu)$: \+ \\ + \IF $\tau = \cookie{challenge}$ \THEN $\id{msg-challenge}(\mu)$; \\ + \ELSE \IF $\tau = \cookie{response}$ \THEN $\id{msg-response}(\mu)$; + \next + Function $\id{msg-challenge}(\mu)$: \+ \\ + $(R', c') \gets \mu$; \\ + $Y' \gets x R'$; \\ + $h' \gets H_I(X', s, R', Y')$; \\ + $r' \gets c' \xor h'$; \\ + \IF $R' \ne r' P$ \THEN \RETURN; \\ + $C \gets C \cup \{R\}$; \\ + $Z \gets r R'$; \\ + $(K_0, K_1) \gets H_K(Z)$; \\ + $\chi \gets E_{K_0}(Y')$; \\ + \SEND $(\cookie{response}, R, \chi)$; + \- \\[\medskipamount] + Function $\id{msg-response}(\mu)$: \+ \\ + $(R', \chi') \gets \mu$; \\ + \IF $R' \notin C$ \THEN \RETURN; \\ + $Z \gets r R'$; \\ + $(K_0, K_1) \gets H_K(Z)$; \\ + $Y' \gets D_{K_0}(\chi')$; \\ + \IF $Y' \ne Y$ \THEN \RETURN; \\ + \OUTPUT $K_1$; + \STOP; + \end{program} + + \caption{Formalization of $\Wkx$} + \label{fig:wkx-formal} +\end{figure} + +\subsubsection{Session states} +We must specify what the adversary obtains when it chooses to reveal a +session's state. Given the program in figure~\ref{fig:wkx-formal}, we can +see that the session state consists of the variables $(x, X, X', r, R, Y, +C)$. + +However, $x$ is the owning party's long-term secret, and it seems +unreasonable to disclose this to an adversary who stops short of total +corruption. + +The public keys $X$ and $X'$ are part of the adversary's input anyway, so +revealing them doesn't help. Similarly, the set $C$ of valid challenges +could have been computed easily by the adversary, since a group element $R' +\in C$ if and only if the session $S$ responded to some message +$(\cookie{challenge}, R', c')$. + +The value $R = r P$ is easily computed given $r$, and besides is sent in the +clear in the session's first message. The expected response $Y = r X'$ is +also easily computed from $r$. The converse is also true, since $r$ can be +recovered from $R$ and $c$ in the session's challenge message and the value +$Y$. Besides, $r$ is necessary for computing $Z$ in response to incoming +challenges. + +We conclude that the only `interesting' session state is $r$. + +\subsubsection{Security} +Having formally presented the protocol, we can now state our main theorem +about its security. The proof is given in appendix~\ref{sec:sk-proof}. +\begin{theorem}[SK-security of $\Wkx$] + \label{thm:sk} + Let $G$ be a cyclic group. Let $\E = (\kappa, E, D)$ be a symmetric + encryption scheme. Then + \begin{spliteqn*} + \InSec{sk}(\Wkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) \le + \frac{n (n - 1)}{|G|} + + \frac{2 q_M}{2^{\ell_I}} + {}\\ + 2 q_S \bigl( \InSec{mcdh}(G; t', q_K) + + n \cdot \InSec{mcdh}(G; t', q_M + q_I) + + \InSec{ind-cca}(\E; t', q_M, q_M) \bigr) + \end{spliteqn*} + where $t' = t + O(n) + O(q_S) + O(q_M q_I) + O(q_K)$. +\end{theorem} + + +\subsection{Insecure protocol variants} +\label{sec:kx-insecure} + +It's important to feed the session-id and verifier's public key to the random +oracle $H_I$ when constructing the check-value~$c$. Without these, the +protocol is vulnerable to attack. In this section, we consider some variants +of our protocol which hash less information, and show attacks against them. + +To simplify the presentation, we shall consider Alice and Bob, and a third +character Carol. We shall be attacking a pair of matching sessions $A$ +and~$B$, run by Alice and Bob respectively. Let Alice and Bob's private keys +be $x_A$ and~$x_B$, and let their public keys be $X_A = x_A P$ and $X_B = x_B +P$ respectively. + +\subsubsection{Protocol diagram notation} +In order to keep the presentation as clear as possible, we use a simple +diagrammatic notation for describing protocol runs. A line of the form +\protocolrun{\textit{action} \ar[r] & \PRsession{S} & \textit{result}} +states that the adversary performs the given \textit{action} on session~$S$, +with the stated \textit{result}. The \textit{action} may be +\begin{itemize} +\item \textsf{Create session $(P_i, P_j, s)$}: the session is created, + running in party~$P_i$, with partner~$P_j$ and session-id~$s$. +\item \textsf{Receive $\mu$}: the session is activated with an incoming message~$\mu$. +\item \textsf{Session-state reveal}: The adversary requests the session's + internal state. +\end{itemize} +The \textit{result} may be +\begin{itemize} +\item \textsf{Send $\mu'$}: the session requests the delivery of the + message~$\mu'$. +\item \textsf{Complete: $K$}: the session completes, outputting the key~$K$. +\item \textsf{State: $\sigma$}: the session's state is revealed to + be~$\sigma$. +\item \textsf{(Ignore)}: the result of the action is unimportant. +\end{itemize} + +\subsubsection{Omitting the session-id} +Consider a protocol variant where session $S$ sets $h_S = H_I(X_N, R_S, +Y_S)$, where $N$ is the session's partner. That is, we've omitted the +session-id from the hash. An adversary can cross over two sessions between +Alice and Bob. Here's how. + +The attack assumes that Alice and Bob set up two pairs of matching sessions +with each other, thus. +\protocolrun{ + \PRcreate{Alice}{Bob}{s} & \PRsession{A} & + \PRsend{challenge}{R_A, c_A} \\ + \PRcreate{Bob}{Alice}{s} & \PRsession{B} & + \PRsend{challenge}{R_B, c_B} \\ + \PRcreate{Alice}{Bob}{s'} & \PRsession{A'} & + \PRsend{challenge}{R_{A'}, c_{A'}} \\ + \PRcreate{Bob}{Alice}{s'} & \PRsession{B'} & + \PRsend{challenge}{R_{B'}, c_{B'}} +} +Observe that the session pairs use distinct session-ids $s \ne s'$, so this +is allowed. Now the adversary crosses over the challenges, using the second +pair of sessions to provide responses to the challenges issued by the first +pair. By revealing the state in the second pair of sessions, the adversary +can work out the (probably different) session keys accepted by the first +pair. +\protocolrun{ + \PRreceive{challenge}{R_B, c_B} & \PRsession{A'} & + \PRsend{response}{R_{A'}, E_{K_{A'B,0}}(x_A R_B)} \\ + \PRreceive{challenge}{R_A, c_A} & \PRsession{B'} & + \PRsend{response}{R_{B'}, E_{K_{B'A,0}}(x_B R_A)} \\ + \PRreceive{challenge}{R_{A'}, c_{A'}} & \PRsession{A} & \PRignore \\ + \PRreceive{challenge}{R_{B'}, c_{B'}} & \PRsession{B} & \PRignore \\ + \PRreveal & \PRsession{A'} & r_{A'} \\ + \PRreveal & \PRsession{B'} & r_{B'} \\ + \PRreceive{response}{R_{B'}, E_{K_{B'A,0}}(x_B R_A)} & \PRsession{A} & + \PRcomplete{K_{AB',1}} \\ + \PRreceive{response}{R_{A'}, E_{K_{A'B,0}}(x_A R_B)} & \PRsession{B} & + \PRcomplete{K_{BA',1}} \\ +} +The adversary can now compute $K_{AB'} = H_K(r_{B'} R_A)$ and $K_{B'A} = +H_K(r_{A'} R_B)$. Safely in possession of both keys, the adversary can now +read and impersonate freely. + +\subsubsection{Omitting the partner's public key} +Now consider a protocol variant where session $S$ sets $h_S = H_I(s, R_S, +Y_S)$, where $s$ is the session-id. An adversary can use a sessions with +Carol to attack a session between Alice and Bob. Here's how the sessions are +set up. +\protocolrun{ + \PRcreate{Alice}{Bob}{s} & \PRsession{A} & + \PRsend{challenge}{R_A, c_A} \\ + \PRcreate{Bob}{Alice}{s} & \PRsession{B} & + \PRsend{challenge}{R_B, c_B} \\ + \PRcreate{Alice}{Carol}{s} & \PRsession{A'} & + \PRsend{challenge}{R_{A'}, c_{A'}} \\ + \PRcreate{Bob}{Carol}{s} & \PRsession{B'} & + \PRsend{challenge}{R_{B'}, c_{B'}} +} +Although each of Alice and Bob have two sessions with session-id~$s$, this is +allowed, since they are with different partners. The rest of the attack in +fact proceeds identically to the previous case. + + +\subsection{Deniability} +\label{sec:denial} + +We have claimed that the Wrestlers key-exchange protocol is \emph{deniable}. +In this section, we define what we mean, explain the limits of the +deniablility of the protocol as currently presented, fix the protocol with an +additional pass (which can be collapsed to a single message flow by breaking +the protocol's symmetry), and prove the deniability of the resulting +protocol. + +Our notion of deniability is taken from Di~Raimondo, Gennaro and Krawczyk +\cite{DiRaimondo:2006:DAK}, except that, as usual, we opt for a concrete +security approach. + +\subsubsection{Discussion} +Our definition for deniability is that, for any adversary interacting with +participants in the protocol, a simulator exists which can compute the same +things as the adversary. In particular, since an adversary could output a +transcript of the interactions between itself and the parties, it would +follow that a simulator could do this too. If the simulator is effective, +its output is indistinguishable from that of the real adversary, and hence no +`judge' (distinguisher) should be persuaded by evidence presented by someone +who claims to have witnessed or participated in an interaction. + +We work again the model described in~\ref{sec:um}. That is, our adversary +has complete control over the ordering and delivery of all messages. The +adversary is also able, at any time, to reveal the state of any session. +However, deniability is obviously impossible against an adversary who can +\emph{corrupt} other parties, since simulating such an adversary's actions +would necessarily require the simulator to compute private keys corresponding +to the known public keys, and this is (we believe) difficult, because an +efficient algorithm for doing this could easily attack our protocol, which we +already proved secure. Therefore, we forbid the adversary from corrupting +parties. + +In order to allow the adversary to participate in the protocol, rather than +merely observing it, we need to give it one or more private keys. We could +modify the initialization function \id{init} from figure~\ref{fig:wkx-formal} +to give the adversary a private key, but there's an easier way: we can just +give the adversary a number of private keys in its auxiliary input. + +\subsubsection{Definitions} +Let $\Pi$ be a key-exchange protocol, in the model described in +section~\ref{sec:um}. We use the simulation framework of +section~\ref{sec:sim}. We define the initialization function $I_\Pi$ to be +the initialization function of $\Pi$, as before, and the corresponding +world~$W_\Pi(\iota, \sigma, \tau, \mu)$ is a fairly straightforward mapping +of the adversary's possible actions to the simulation model: +\begin{itemize} +\item The invocation $\cookie{new-session}$ with $\mu = (i, j, s)$ creates a + new session on party~$P_i$, with partner~$P_j$ and session-id~$s$. The + reply $\rho = (\delta, m)$ is a \emph{decision} $\delta \in + \{\cookie{continue}, \cookie{abort}, \cookie{complete}\}$ and an output + message $m \in \Bin^* \cup \{\bot\}$. If $m \ne \bot$ then $m$ is a + message to be sent to the matching session (if any). +\item The invocation $\cookie{deliver}$ with $\mu = (i, j, s, m)$ delivers + message $m$ to the session $S = (P_i, P_j, s)$. The response $\rho$ is as + for $\cookie{new-session}$ invocations. +\item The invocation $\cookie{reveal-session-state}$ with $\mu = (i, j, s)$ + reveals to the adversary the state of the running session $S = (P_i, P_j, + s)$. The response $\rho$ is the session's state if $S$ is indeed a running + session, or $\bot$ otherwise. +\item The invocation $\cookie{reveal-session-key}$ with $\mu = (i, j, s)$ + reveals to the adversary the session-key of the completed session~$S = + (P_i, P_j, s)$. The response $\rho$ is the session key~$K$ if the session + is indeed complete, or $\bot$ otherwise. +\end{itemize} +There are no invocations corresponding to the adversary actions of corrupting +parties (since deniability against an corrupting adversary is impossible, as +discussed earlier), or session expiry or challenging (since they are useless +in this context). + +We measure the deniability of a protocol~$\Pi$, using a given simulator~$S$, +by the insecurity function $\InSec{sim}(W_\Pi, I_\Pi, S; t_D, t_A, +\mathcal{Q}_D, \mathcal{Q}_A, \mathcal{R}, \mathcal{U})$ of +definition~\ref{def:sim}. The interaction bounds $\mathcal{R} = (q_S, q_M)$ +we place on the adversary are on the number ($q_S$) of \cookie{new-session} +and ($q_M$) \cookie{deliver} invocations it makes. + +We shall (informally) say that a protocol~$\Pi$ is deniable if there is a +simulator~$S_\Pi$ for which the insecurity function is small for appropriate +resource bounds on the adversary and distinguisher. + +\subsubsection{The current protocol} +As it stands, $\Wkx$ isn't deniable, according to our definition, for +arbitrary auxiliary inputs. Let's see why. + +Suppose that Bob is an informant for the secret police, and wants to convince +a judge that Alice is involved in subversive activities in cyberspace. +Unfortunately, Bob's job is difficult, because of the strong zero-knowledge +nature of the Wrestlers identification protocol. However, Bob can work with +the judge to bring him the evidence necessary to convict Alice. Here's how. + +Alice's public key is $A$, and Bob's public key is $B$. The judge chooses +some session-id $s$, and $r \inr \Nupto{q}$. He computes $R = r P$ and $c = +r \xor H_I(B, s, R, r A)$, and gives Bob the triple $(s, R, c)$, keeping $r$ +secret. Bob can now persuade Alice to enter into a key-exchange with him, +with session-id $s$. He uses $(R, c)$ as his challenge message. When Alice +sends back her response $(R', \chi)$ (because Bob's challenge is correctly +formed), Bob aborts and shows $(R', \chi)$ to the judge. The judge knows $r$ +and can therefore decrypt $\chi$ and check the response. If it's wrong, then +Bob was cheating and gets demoted -- he can't get the right answer by himself +because that would require him to impersonate Alice. If it's right, Alice is +really a subversive element and `disappears' in the night. + +We shall show in theorem~\ref{thm:denial} below that this is basically the +only attack against the deniability of the protocol. However, we can do +better. + +\subsubsection{Fixing deniability} +We can fix the protocol to remove even the attack discussed above. The +change is simple: we feed \emph{both} parties' challenges to the hash +function~$H_I$ rather than just the sender's. We use a five-argument hash +function (random oracle) $H_I\colon G^2 \times \Bin^{\ell_S} \times G^2 \to +\Bin^{\ell_I}$. We introduce a new message pass at the beginning of the +protocol: each session simply sends its challenge point $R = r P$ in the +clear as a `pre-challenge'. The actual challenge is $R$ and $c = r \xor +H_I(X, R', s, R, c)$, where $R'$ is the challenge of the matching session. + +By breaking symmetry, we can reduce the communication complexity of this +variant to four messages. As before, we analyse the symmetrical version. +The extra flow might seem a high price to pay, but we shall see that it has +additional benefits beyond deniability. + +A summary of the new protocol is shown in figure~\ref{fig:wdkx}, and the +formal description is shown in figure~\ref{fig:wdkx-formal}. + +\begin{figure} + \begin{description} + \item[Setup] Group $G = \langle P \rangle$; $|G| = q$ is prime. + $H_I(\cdot, \cdot, \cdot, \cdot, \cdot)$ and $H_K(cdot)$ are secure + hashes. $\E = (\kappa, E, D)$ is an IND-CCA2 symmetric encryption + scheme. + \item[Parties] $U_i$ for $0 \le i < n$. + \item[Private keys] $x_i \inr \Nupto{q}$. + \item[Public keys] $X_i = x_i P$. + \end{description} + \[ \begin{graph} + !{0; <8cm, 0cm>: <0cm, 3cm>::} + *+[F]\dbox{$r_i \getsr I$; $R_i \gets r_i P$} ="i-1" + [d] + *+[F]\dbox{$c_i \gets r_i \xor H_I(R_j, X_i, s, R_i, r_i X_j)$} ="i0" + [d] + *+[F]\dbox{Check $R_j = \bigl(c_j \xor H_I(x_i R_j)\bigr) P$ \\ + $Z \gets r_i R_j$; $K \gets H_K(0, Z)$ \\ + $\chi_i \gets E_K(x_i R_j)$} ="i1" + [d] + *+[F]\dbox{Check $D_K(\chi_j) = r_i X_j$ \\ + Shared key is $H_K(1, Z)$} ="i2" + "i-1" [r] + *+[F]\dbox{$r_j \getsr I$; $R_j \gets r_j P$} ="j-1" + [d] + *+[F]\dbox{$c_j \gets r_j \xor H_I(R_i, X_j, s, R_j, r_j X_i)$} ="j0" + [d] + *+[F]\dbox{Check $R_i = \bigl(c_i \xor H_I(x_j R_i)\bigr) P$ \\ + $Z \gets r_j R_i$; $K \gets H_K(0, Z)$ \\ + $\chi_j \gets E_K(x_j R_i)$} ="j1" + [d] + *+[F]\dbox{Check $D_K(\chi_i) = r_j X_i$ \\ + Shared key is $H_K(1, Z)$} ="j2" + % + "i-1" : |(0)/3.25cm/*+{R_i} "j0" + "i0" : |(0)/3.25cm/*+{(R_i, c_i)} "j1" + "i1" : |(0)/3.25cm/*+{(R_i, \chi_i)} "j2" + "j-1" : |(0)/3.25cm/*+{R_j} "i0" + "j0" : |(0)/3.25cm/*+{(R_j, c_j)} "i1" + "j1" : |(0)/3.25cm/*+{(R_j, \chi_j)} "i2" + \end{graph} \] + + \caption{Summary of the Deniable Wrestlers Key Exchange protocol, $\Wdkx$} + \label{fig:wdkx} +\end{figure} + +\begin{figure} + \begin{program} + Function $\id{init}(n)$: \+ \\ + \FOR $i \in \Nupto{n}$ \DO \\ \ind + $x \getsr \Nupto{|G|}$; \\ + $\mathbf{i}[i] \gets x$; \\ + $\mathbf{p}[i] \gets x P$; \- \\ + \RETURN $(\mathbf{p}, \mathbf{i})$; + \- \\[\medskipamount] + Function $\id{new-session}^{H_I(\cdot, \cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\mathbf{p}, x, i, j, s)$: \+ \\ + $X \gets \mathbf{p}[i]$; + $X' \gets \mathbf{p}[j]$; + $C \gets \emptyset$; \\ + $r \getsr \Nupto{|G|}$; + $R \gets r P$; + $Y \gets r X'$; \\ + \SEND $(\cookie{pre-challange}, R)$; + \- \\[\medskipamount] + Function $\id{message}^{H_I(\cdot, \cdot, \cdot, \cdot, \cdot), H_K(\cdot)} + (\tau, \mu)$: \+ \\ + \IF $\tau = \cookie{pre-challenge}$ \THEN + $\id{msg-pre-challenge}(\mu)$; \\ + \ELSE \IF $\tau = \cookie{challenge}$ \THEN + $\id{msg-challenge}(\mu)$; \\ + \ELSE \IF $\tau = \cookie{response}$ \THEN $\id{msg-response}(\mu)$; + \next + Function $\id{msg-pre-challenge}(\mu)$: \+ \\ + $R' \gets \mu$; \\ + $h \gets H_I(R', X, s, R, c)$; \\ + $c \gets r \xor h$; \\ + \SEND $(\id{msg-challenge}, R, c)$; + \- \\[\medskipamount] + Function $\id{msg-challenge}(\mu)$: \+ \\ + $(R', c') \gets \mu$; \\ + $Y' \gets x R'$; \\ + $h' \gets H_I(R, X', s, R', Y')$; \\ + $r' \gets c' \xor h'$; \\ + \IF $R' \ne r' P$ \THEN \RETURN; \\ + $C \gets C \cup \{R\}$; \\ + $Z \gets r R'$; \\ + $(K_0, K_1) \gets H_K(Z)$; \\ + $\chi \gets E_{K_0}(Y')$; \\ + \SEND $(\cookie{response}, R, \chi)$; + \- \\[\medskipamount] + Function $\id{msg-response}(\mu)$: \+ \\ + $(R', \chi') \gets \mu$; \\ + \IF $R' \notin C$ \THEN \RETURN; \\ + $Z \gets r R'$; \\ + $(K_0, K_1) \gets H_K(Z)$; \\ + $Y' \gets D_{K_0}(\chi')$; \\ + \IF $Y' \ne Y$ \THEN \RETURN; \\ + \OUTPUT $K_1$; + \STOP; + \end{program} + + \caption{Deniable key-exchange: formalization of $\Wdkx$} + \label{fig:wdkx-formal} +\end{figure} + +The security of this variant is given by the following theorem, whose proof +is in appendix~\ref{sec:sk2-proof}. +\begin{theorem}[SK-security of $\Wdkx$] + \label{thm:sk2} + Let $G$ be a cyclic group. Let $\E = (\kappa, E, D)$ be a symmetric + encryption scheme. Then + \[ \InSec{sk}(\Wdkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) = + \InSec{sk}(\Wkx^{G, \E}; t, n, q_S, q_M, q_I, q_K) + \] +\end{theorem} + +\subsubsection{Deniability of the Wrestlers protocols} +In order to quantify the level of deniability our protocols provide, we shall +impose a limit on the auxiliary input to the adversary. In particular, we +shall use $\mathcal{U}$ of definition~\ref{def:sim} to count the number of +\emph{challenges} in the auxiliary input. That is, $\mathcal{U} = n_C$ is +the number of tuples $(i, j, s, R', R, c)$ for which there is an $r$ such +that $R = r P$ and $c = r \xor H_I(R', X_j, s, R, r X_i)$ (or without the +$R'$ for $\Wkx$). + +With this restriction in place, we can state the following theorem about the +deniability of our protocols. +\begin{theorem}[Deniability of $\Wkx$ and $\Wdkx$] + \label{thm:denial} + There exist simulators $S_\Wkx$ and $\Wdkx$ such that + \[ \InSec{sim}(W_{\Wkx^{G, \E}}, I_{\Wkx^{G, \E}}, S_{\Wkx^{G, \E}}; + t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A, (q_S, q_M), 0) \le + \frac{q_M}{2^{\ell_I}} + \] + and + \[ \InSec{sim}(W_{\Wdkx^{G, \E}}, I_{\Wdkx^{G, \E}}, S_{\Wdkx^{G, \E}}; + t_D, t_A, \mathcal{Q}_D, \mathcal{Q}_A, (q_S, q_M), n_C) \le + \frac{n_C q_S}{|G|} + + \frac{q_M}{2^{\ell_I}}. + \] + The running time of the simulators is $O(t_A) + O(\mathcal{Q}_A q_M)$. +\end{theorem} +\begin{proof} + The simulators $S_\Wkx$ and $S_\Wdkx$ are very similar. We describe both + here. Both are fake-world simulators, working as follows. + \begin{enumerate} + \item Initially, it constructs simulated parties $P_i$, for $0 \le i < n$, + giving each the public key $X_i$ from the common input. + \item Suppose the adversary requests creation of a new session $S = (P_i, + P_j, s)$. Then the simulator creates a new session, including a random + value $r_S \inr \Nupto{|G|}$, and computes $R_S = r_S P$, and $Y_S = r_S + X_j$. For $\Wdkx$, it sends the message $(\cookie{pre-challenge}, R_S)$; + for $\Wkx$, it additionally computes $h = H_I(X_i, s, R_S, Y_S)$ and + sends $(\cookie{challenge}, R_S, r_S \xor h)$. + \item Suppose, for $\Wdkx$, the adversary sends a message + $(\cookie{pre-challenge}, R')$ to a session~$S = (P_i, P_j, s)$. The + simulator computes $h = H_I(R', X_i, s, R_S, Y_S)$, and sends + $(\cookie{challenge}, R_S, r_S \xor h)$. + \item Suppose the adversary sends a message $(\cookie{challenge}, R', c')$ + to session $S = (P_i, P_j, s)$. The simulator doesn't know $x_i$. + \begin{enumerate} + \item If $R' = R_T$ for some other simulated session $T$, then the + simulator knows $r_T$ such that $R_T = r_T P$. Let $Y' = r_T X_i$. + The simulator computes $h = H_I(X_j, s, R', Y')$ (resp.\ $h = H_I(R_S, + X_j, s, R', Y')$) for $\Wkx$ (resp.\ $\Wdkx$) and checks that $r_T = c' + \xor h$. If not, the simulator discards the message. Otherwise, it + computes $(K_0, K_1) = H_K(r_S R')$, and sends the message + $(\cookie{response}, R, E_{K_0}(Y'))$. + \item \label{en:simextract} Otherwise the simulator runs the extractor + $T_\Wident$ on the adversary's history of queries $H_I(X_j, s, R', + \cdot)$ (resp.\ $H_I(R_S, X_j, s, R', \cdot)$) for $\Wkx$ (resp.\ + $\Wdkx$). The extractor returns $(r', Y')$. If $Y' = \bot$ then the + simulator ignores the message. Otherwise, the simulator computes + $(K_0, K_1) = H_K(r R')$ and sends back $(\cookie{response}, R, + E_{K_0}(Y'))$. + \end{enumerate} + \item Suppose the adversary sends a message $(\cookie{response}, R', \chi)$ + to session $S = (P_i, P_j, s)$. The simulator computes $(K_0, K_1) = + H_K(r_S R')$, and decrypts $Y' = D_{K_0}(\chi)$. If $Y' \ne Y_S$ then + the simulator discards the message. Otherwise, it makes the simulated + session complete, and outputs key $K_1$. + \item Finally, if the adversary reveals a session's state, the simulator + reveals $r_S$ as required; if the adversary reveals a session-key, the + simulator reveals the $K_1$ it output. + \end{enumerate} + The only point where the simulation fails to be perfect is in + \ref{en:simextract}. Let $R'$ and $c'$ be the values from an incoming + challenge message to session $S = (P_i, P_j, s)$. Let $r'$ be such that + $R' = r' P$ and let $Y' = r' X_i$. If a random-oracle query $H_I(X_j, s, + R', Y')$ (or $H_I(R_S, X_j, s, R', Y')$ for $\Wdkx$) has been issued, then + there are a number of possibilities. Let $h'$ be the result of this query. + \begin{itemize} + \item The adversary made this query. Then the extractor will find it and + return $Y'$ if $c' = h' \xor r'$, or $\bot$ otherwise. + \item Some simulated session $U = (P_{i'}, P_{j'}, s')$ made this query. + But simulated sessions only make $H_I$-queries when constructing + challenges, so $R' = R_U$ for some session~$U$. But the simulator does + something different in that case. + \item In $\Wdkx$, the quadruple $(s, R_S, R', c')$ came from the + adversary's auxiliary input. In this case the simulator must fail. But + $R_S = r_S P$, and $r_S$ was chosen uniformly at random. If there are at + most $n_C$ challenge sets in the auxiliary input then this happens with + probability at most $n_C/|G|$ for any given session. + \end{itemize} + We conclude that the simulator fails with probability + \[ \frac{q_M}{2^{\ell_I}} + \frac{q_S n_C}{|G|}. \] + (Note that we only consider $n_C = 0$ for $\Wkx$.) No adversary can + distinguish the simulator from a real interaction unless the simulator + fails, and the simulator is a fake-world simulator. We therefore apply + proposition~\ref{prop:fakesim}; the theorem follows. +\end{proof} + + +\subsection{Practical issues} +\label{sec:practice} + +\subsubsection{Denial of service from spoofers} +The adversary we considered in~\ref{sec:um} is very powerful. Proving +security against such a powerful adversary is good and useful. However, +there are other useful security properties we might like against weaker +adversaries. + +Eavesdropping on the Internet is actually nontrivial. One needs control of +one of the intermediate routers between two communicating parties. (There +are tricks one can play involving subversion of DNS servers, but this is also +nontrivial.) However, injecting packets with bogus source addresses is very +easy. + +Layering the protocol over TCP \cite{RFC793} ameliorates this problem because +an adversary needs to guess or eavesdrop in order to obtain the correct +sequence numbers for a spoofed packet; but the Wrestlers protocol is +sufficiently simple that we'd like to be able to run it over UDP +\cite{RFC768}, for which spoofing is trivial. + +Therefore, it's possible for anyone on the 'net to send Alice a spurious +challenge message $(R, c)$. She will then compute $Y = a R$, recover $r' = c +\xor H_I(\ldots, R, Y)$ check that $R = r' P$ and so on. That's at least two +scalar multiplications to respond to a spoofed packet, and even with very +efficient group operations, coping with this kind of simple denial-of-service +attack might be difficult. + +A straightforward solution is to use the Deniable variant of the protocol, +and require a challenge to quote its matching session's challenge $R'$ in its +challenge. That is, upon receiving a $(\cookie{pre-challenge}, R')$, the +session sends $(\cookie{challenge}, R', R, c)$. Alice then rejects any +\emph{incoming} challenge message which doesn't quote her current challenge +value. Now only eavesdroppers can force her to perform expensive +computations. + +Indeed, one need not quote the entire challenge $R'$: it suffices to send +some short hard-to-guess hash of it, maybe just the bottom 128 bits or so. + +This can't reduce security. Consider any adversary attacking this protocol +variant. We can construct an adversary which attacks the original protocol +just as efficiently. The new adversary attaches fake $R'$ values to +challenges output by other parties, and strips them off on delivery, +discarding messages with incorrect $R'$ values. + +There's another denial-of-service attack against the Wrestlers protocol. + +\subsubsection{Key confirmation} +Consider an application which uses the Wrestlers protocol to re-exchange keys +periodically. The application can be willing to \emph{receive} incoming +messages using the new key as soon as the key exchange completes +successfully; however, it should refrain from \emph{sending} messages under +the new key until it knows that its partner has also completed. The partner +may not have received the final response message, and therefore be unwilling +to accept a new key; it will therefore (presumably) reject incoming messages +under this new key. + +While key confirmation is unnecessary for \emph{security}, it has +\emph{practical} value, since it solves the above problem. If the +application sends a \cookie{switch} message when it `completes', it can +signal its partner that it is indeed ready to accept messages under the new +key. The \cookie{switch} message can be as simple as $(\cookie{switch}, +E_{K_0}(\cookie{switch}))$. + +\subsubsection{Unreliable transports} +The Internet UDP \cite{RFC768} is a simple, unreliable protocol for +transmitting datagrams. However, it's very efficient, and rather attractive +as a transport for datagram-based applications such as virtual private +networks (VPNs). + + + +\subsubsection{Key reuse} + + +%%%-------------------------------------------------------------------------- + +\section{Acknowledgements} + +The Wrestlers Protocol is named after the Wrestlers pub in Cambridge where +Clive Jones and I worked out the initial design. + +%%%-------------------------------------------------------------------------- + +\bibliography{mdw-crypto,cryptography2000,cryptography,rfc} + +%%%-------------------------------------------------------------------------- + +\appendix +\section{Proofs} + +\subsection{Proof of theorem~\ref{thm:sk}} +\label{sec:sk-proof} + +Before we embark on the proof proper, let us settle on some notation. Let +$P_i$ be a party. Then we write $x_i$ for $P_i$'s private key and $X_i = x_i +P$ is $P_i$'s public key. Let $S = (P_i, P_j, s)$ be a session. We write +$r_S$ for the random value chosen at the start of the session, and $R_S$, +$c_S$ etc.\ are the corresponding derived values in that session. + + +The proof uses a sequence of games. For each game~$\G{i}$, let $V_i$ be the +event that some pair of unexposed, matching sessions both complete but output +different keys, and let $W_i$ be the event that the adversary's final output +equals the game's hidden bit~$b^*$. To save on repetition, let us write +\[ \diff{i}{j} = \max(|\Pr[V_i] - \Pr[V_j]|, |\Pr[W_i] - \Pr[W_j]|). \] +Obviously, +\[ \diff{i}{j} \le \sum_{i\le k 5$, we define the event $F_i$ to be the event + corresponding to $F_5$ in $\G{i}$. Note that if $S_k$ \emph{is} sent a + message in $M_{T_k}$ then $S_k$ immediately completes. + + \begin{claim} + $\Pr[F_4] \le \Pr[F_5]/q_S$. + \end{claim} + This claim is proven exactly as we did for claim~1 of + lemma~\ref{lem:sk-g2-g3}. + + Let~$\G6$ be the same as $\G5$ except that we change the encrypted + responses of session~$S_k$ and its matching session~$T_k$. Let $K^* = + (K_0^*, K_1^*) = H_K(Z_S)$. Then, rather than sending $(\cookie{response}, + R_S, E_{K_0^*}(Y_T))$, session~$S$ sends $(\cookie{response}, R_S, + E_{K_0^*}(1^{\ell_G}))$. + \begin{claim} + $|\Pr[F_6] - \Pr[F_5]| \le \InSec{ind-cca}(\E; t', q_M, q_M).$ + \end{claim} + To prove this claim, we construct an adversary~$B$ which attacks the + IND-CCA security of our encryption scheme $\E$. The adversary~$B$ works as + follows. + \begin{enumerate} + \item It is given no input, but a pair of oracles $E(\cdot, \cdot)$ and + $D(\cdot)$; the former encrypts either the left or right input, according + to a hidden bit, and the latter decrypts ciphertexts other than those + returned by $E(\cdot, \cdot)$. Its goal is to guess the hidden bit. + \item It sets up a simulation of the game~$\G5$, by running the $\id{init}$ + function, and simulating all of the parties. In particular, it chooses a + random $k \in \Nupto{q_S}$. + \item It sets up accurate simulations of the random oracles $H_K(\cdot)$ + and $H_I(\cdot, \cdot, \cdot, \cdot)$. + \item It runs $A$ in its simulated game. It responds to all of $A$'s + instructions faithfully, except for the matching sessions $S_k$ and + $T_k$. Let $S = S_k = (P_i, P_j, s)$, and $T = T_k = (P_j, P_i, s)$. + \item Suppose $T$ is sent the message $C_S = (\cookie{challenge}, R_S, + c_S)$. Rather than computing $K^* = H_K(r_T R_S)$ and performing the + encryption properly, $B$ queries its left-or-right encryption oracle + $E(\cdot, \cdot)$ on $E(1^{\ell_G}, x_j R_S)$, and sends the resulting + ciphertext~$\chi$ back to~$S$ as part of a message $(\cookie{response}, + R_T, \chi)$. The set $M_T$ is precisely the set of messages constructed + in this fashion. (Recall that challenge messages other than $C_S$ aren't + actually delivered to $T$, since we simulate the responses using the + extractor, as of $\G2$.) + \item Suppose $S$ is sent a message $M = (\cookie{response}, R_T, \chi) \in + M_T$. We immediately stop the simulation, and $B$ returns $0$. + \item Suppose, instead, that $S$ is sent some message $M' = + (\cookie{response}, R, \chi) \notin M_T$. There are two cases to + consider. If $R = R_T$ then we must have $\chi$ distinct from the + ciphertexts returned by the $E(\cdot, \cdot)$ oracle, so we can invoke + the decryption oracle $D(\cdot)$ on $\chi$ to obtain a response $Y$. + Alternatively, if $R \ne R_T$, we can compute the key $K = (K_0, K_1) = + H_K(r_S R)$, and recover $Y = D_{K_0}(\chi)$. In either case, if $Y = + r_S X_j)$ then $S$ would complete at this point: $B$ stops the simulation + and returns $1$. + \item If $A$ exposes $S$ (by corrupting $P_i$ or~$P_j$, or revealing $S$ or + $T$) then we stop the simulation and $B$ returns $0$. + \item Finally, if the game stops, either because $A$ halts, or because of + one of the special rules introduced in earlier games, $B$ returns $0$. + \end{enumerate} + It is clear that $B$'s oracle queries are acceptable, since $|x_j R_S| = + \ell_G$ by definition, and $B$ never queries $D(\cdot)$ on a ciphertext + returned by its encryption oracle. By the rules of~$\G3$, we know that the + game stops immediately if $A$ ever queries $Z_S$, so the key $K^*$ is + independent of everything in $A$'s view except the ciphertexts $\chi$ + output by $S$ and $T$. Therefore, if the hidden bit of the IND-CCA game is + $1$, $B$ accurately simulates $\G5$, whereas if the bit is $0$ then $B$ + accurately simulates $\G6$. Finally, we issue no more that $q_M$ + encryption or decryption queries. Therefore, + \[ \Adv{ind-cca}{\E}(B) = \Pr[F_5] - \Pr[F_6] + \le \InSec{ind-cca}(\E; t', q_M, q_M). \] + We construct the adversary~$\bar{B}$ which is the same as $B$ above, except + that $\bar{B}$ returns $0$ whenever $B$ returns~$1$, and \emph{vice versa}. + Clearly + \[ \Adv{ind-cca}{\E}(\bar{B}) + = (1 - \Pr[F_5]) - (1 - \Pr[F_6]) + = \Pr[F_6] - \Pr[F_5] + \le \InSec{ind-cca}(\E; t', q_M, q_M). + \] + This proves the claim. + + Let $\G7$ be the same as $\G6$, except that at the start of the game we + choose a random $m \in \Nupto{n}$, and when the adversary creates the + session $S = S_k = (P_i, P_j, s)$, we abort the game unless $j = m$. + Clearly we have $\Pr[F_6] = n \Pr[F_7]$. + + Finally, we can explicitly bound $F_6$. In $\G6$, the adversary's view is + independent of the correct response $Y_S = r_S X_S = x_j R_S$ to $S$'s + challenge. Therefore, if $A$ manages to send any message $\mu \notin M_T$ + which causes $S$ to complete, then it has impersonated~$P_j$. + \begin{claim} + $\Pr[F_7] \le \InSec{mcdh}(G; t', q_M + q_I)$. + \end{claim} + The present lemma follows from this and the previous claims. + + To prove the claim formally, we construct an adversary~$B'$, which behaves + as follows. + \begin{enumerate} + \item It is given as input a public key $X^*$ and a single challenge $(R^*, + c^*)$, a random oracle $H^*_I(\cdot, \cdot)$, and an oracle $V(\cdot, + \cdot)$, which verifies responses $(R, Y)$. Its goal is to invoke + $V(\cdot, \cdot)$ with a correct response to the challenge. + \item It chooses a random $k \in \Nupto{q_S}$ and $m \in \Nupto{n}$. It + sets up a simulation of the game~$\G7$, by running the $\id{init}$ + function, and simulating all of the parties, except that it gives party + $P_m$ the public key $X^*$. This makes no difference, since $P_m$ + doesn't actually need to give any `honest' responses because of the + change we made in $\G6$. + \item It sets up accurate simulations of the random oracles $H_K(\cdot)$ + and $H_I(\cdot, \cdot, \cdot, \cdot)$, with one exception -- see below. + \item It runs $A$ in its simulated game. It responds to all of $A$'s + instructions faithfully, except for the session $S_k$. Let $S = S_k = + (P_i, P_j, s)$, and let $T = T_k = (P_j, P_i, s)$ be its matching + session. + \item When session~$S$ is created, $B'$ checks that $j = m$, and if not + stops the simulation and halts. Otherwise, $B'$ invokes its oracle~$C()$ + to obtain a pair $(R, c)$. Session~$S$ sends $C_S = (\cookie{challenge}, + R, c)$ as its challenge to~$T$. + \item When $A$ makes a query $H_I(X^*, s, R, Y)$, $B$ answers it by + querying its \emph{own} random oracle $H^*_I(R, Y)$. + \item When $S$ receives a message $(\cookie{response}, R, \chi)$, we + compute $(K_0, K_1) = r_S R$, and $Y = D_{K_0}(\chi)$. If $Y \ne \bot$ + then $B'$ calls $V(R, Y)$. + \item If $A$ reveals $S$ or corrupts $P_i$ or $P_j$ then $B'$ stops the + simulation immediately and halts. + \end{enumerate} + Clearly $B'$ succeeds whenever $F_7$ occurs; hence we can apply + theorem~\ref{thm:wident-sound}. The claim follows. +\end{proof} + + +\subsection{Proof of theorem~\ref{thm:sk2}} +\label{sec:sk2-proof} + +The proof is almost identical to the proof of theorem~\ref{thm:sk}, in +appendix~\ref{sec:sk-proof}. Unfortunately a black-box reduction doesn't +seem possible. + +We use the games and notation of section~\ref{sec:sk-proof}. + +The change to the check-value calculation doesn't affect key-generation at +all, so the transition to $\G1$ goes through as before. + +The transition from $\G1$ to $\G2$ -- answering challenges using the +extractor -- needs a little care. Let $S = (P_i, P_j, s)$ be a session, and +consider an incoming message $(\cookie{challenge}, R, c)$. +\begin{itemize} +\item If $T = (P_j, P_i, s)$ is the matching session to $S$, and $R = R_T$ is + the public challenge value of $T$, and $c = r_T \xor H_I(R_S, X_j, s, R_T, + r_T X_i)$ is the check-value output by $T$ when it received + $(\cookie{pre-challenge}, R_S)$ as input, then $S$ replies as it did in + $\G1$. +\item If the challenge message is any other message, then we use the + extractor. +\end{itemize} +As in lemma~\ref{lem:sk-g1-g2}, we examine which sessions could have queried +$H_I(R_S, X_j, s, R, x_i R)$, and for the same reasons conclude that only the +matching session would have done this, and only in response to the +pre-challenge $R_S$. It follows that $\diff{1}{2} \le q_M/2^{\ell_I}$ as +before. + +The remaining game steps go through unchanged. In particular, we conclude +that a ripe session will only complete if the adversary has transmitted +messages from its matching session correctly, and the session key is +independent of the adversary's view. The theorem follows. + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: diff --git a/wrshortsl.tex b/wrshortsl.tex new file mode 100644 index 0000000..ad79cb3 --- /dev/null +++ b/wrshortsl.tex @@ -0,0 +1,6 @@ +\let\short\relax +\input wrslides +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "wrslides" +%%% End: diff --git a/wrslide.tex b/wrslide.tex new file mode 100644 index 0000000..96bbe36 --- /dev/null +++ b/wrslide.tex @@ -0,0 +1,346 @@ +\xcalways\section{The Wrestlers Protocol}\x + +\xcalways\subsection{Identification using Diffie-Hellman}\x + +\begin{slide} + \resetseq + \head{Identification using Diffie-Hellman \seq: Properties} + \topic{properties} + + \begin{itemize} + \item Simple -- easy to remember, analyse and implement + \item Practical -- two scalar multiplications for each party + \item Secure -- under Computational Diffie-Hellman assumption + \item Zero-knowledge -- statistical ZK + \item Proofs in random oracle model -- but without `programming' + \end{itemize} +\end{slide} + +\begin{slide} + \head{Identification using Diffie-Hellman \seq: Basic setting} + \topic{setting} + + \begin{itemize} + \item Cyclic group $(G, +)$ + \item $|G| = q$ is prime + \item $P$ generates $G$ + \item Alice's private key is $a \inr \Nupto{q}$ + \item Alice's public key is $A = a P$ + \item Assume computational Diffie-Hellman problem hard in $G$ + \end{itemize} +\end{slide} + +\begin{slide} + \head{Identification using Diffie-Hellman \seq: Na\"\i ve attempt} + \topic{protocol design} + + \begin{protocol} + Alice & Bob \\ + (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) + \\[\medskipamount] + & $r \getsr \Nupto{q}$; \\ + & $R \gets r P$; \\ + \\ + \\ + \\ + \send{<-}{R} + $Y \gets a R$; \\ + \\ + \\ + \\ + \send{->}{Y} + & \textbf{Check} $Y = r A$ + \end{protocol} +\end{slide} + +\begin{slide} + \head{Identification using Diffie-Hellman \seq: Fix it with a hash} + \protocolskip0pt + + \begin{protocol} + Alice & Bob \\ + (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) + \\[\medskipamount] + & $r \getsr \Nupto{q}$; \\ + & $R \gets r P$; \\ + & $Y \gets r A$; \\ + & \diff $h \gets H(\cookie{check}, R, Y)$; \\ + & \\ + \send{<-}{(R, \hbox{\diff $h$})} + $Y \gets a R$; \\ + \\ + \\ + \diff \textbf{Check} $h = H(\cookie{check}, R, Y)$ \\ + \send{->}{Y} + & \textbf{Check} $Y$ + \end{protocol} + \dots but there are still small-subgroup attacks +\end{slide} + +\begin{slide} + \head{Identification using Diffie-Hellman \seq: Stinson-Wu [SW06]} + \protocolskip0pt + + \begin{protocol} + Alice & Bob \\ + (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) + \\[\medskipamount] + & $r \getsr \Nupto{q}$; \\ + & $R \gets r P$; \\ + & $Y \gets r A$; \\ + & $h \gets H(\cookie{check}, R, Y)$; \\ + & \\ + \send{<-}{(R, h)} + $Y \gets a R$; \\ + \\ + \diff \textbf{Check} $q R = 0$; \\ + \textbf{Check} $h = H(\cookie{check}, R, Y)$ \\ + \send{->}{Y} + & \textbf{Check} $Y$ + \end{protocol} + \dots and apply the Knowledge of Exponent assumption +\end{slide} + +\begin{slide} + \head{Identification using Diffie-Hellman \seq: The Wrestlers Protocol + $\Wident$} + + \begin{protocol} + Alice & Bob \\ + (Private key $a \inr \Nupto{q}$) & (Public key $A = a P$) + \\[\medskipamount] + & $r \getsr \Nupto{q}$; \\ + & $R \gets r P$; \\ + & $Y \gets r A$; \\ + & $h \gets H(\cookie{check}, R, Y)$; \\ + & \diff $c \gets h \xor r$; \\ + \send{<-}{(R, \hbox{\diff $c$})} + $Y \gets a R$; \\ + $h \gets H(\cookie{check}, R, Y)$; \\ + \diff $r \gets c \xor h$; \\ + \diff \textbf{Check} $R = r P$ \\ + \send{->}{Y} + & \textbf{Check} $Y$ + \end{protocol} +\end{slide} + +\begin{slide} + \head{Identification using Diffie-Hellman \seq: Identification-based + $\Wident$} + + \begin{protocol} + Alice & Bob \\ + (Private key $K_A = t I_A$) & + (Public key $I_A = H(\cookie{id}, \text{Alice})$) + \\[\medskipamount] + & $r \getsr \Nupto{q}$; \\ + & $R \gets r P$; \\ + & \diff $Y \gets \hat{e}(T, I_A)^r$; \\ + & $h \gets H(\cookie{check}, R, Y)$; \\ + & $c \gets h \xor r$; \\ + \send{<-}{(R, c)} + \diff $Y \gets \hat{e}(R, K_A)$; \\ + $h \gets H(\cookie{check}, R, Y)$; \\ + $r \gets c \xor h$; \\ + \textbf{Check} $R = r P$ \\ + \send{->}{Y} + & \textbf{Check} $Y$ + \end{protocol} + (Trusted authority's private key $t \inr \Nupto{q}$; public key $T = t P$) +\end{slide} + +\xcalways\subsection{Key exchange}\x + +\begin{slide} + \resetseq + \head{Mutual identification \seq: Bob identifies Alice} + \topic{mutual identification} + + \begin{protocol} + Alice & Bob \\ + (Private key $a$, public key $A = a P$) + \\[\medskipamount] + & $r_B \getsr \Nupto{q}$; \\ + & $R_B \gets r_B P$; \\ + \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} + \\ + $Y_B \gets a R_B$; \\ + \\ + \send{->}{Y_B} + \end{protocol} +\end{slide} + +\begin{slide} + \head{Mutual identification \seq: Alice identifies Bob too} + + \begin{protocol} + Alice & Bob \\ + (Private key $a$, public key $A = a P$) & + \other (Private key $b$, public key $B = b P$) + \\[\medskipamount] + \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ + \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ + \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} + \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} + $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ + \\ + \send{->}{Y_B} + \send{<-}{\other Y_A} + \end{protocol} +\end{slide} + +\begin{slide} + \head{Mutual identification \seq: Key exchange?} + + \begin{protocol} + Alice & Bob \\ + (Private key $a$, public key $A = a P$) & + \other (Private key $b$, public key $B = b P$) + \\[\medskipamount] + \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ + \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ + \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} + \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} + $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ + \\ + \send{->}{Y_B} + \send{<-}{\other Y_A} + \diff $Z \gets r_A R_B$; & \diff $Z \gets r_B R_A$; + \end{protocol} + \bigskip + Unfortunately it's not secure. +\end{slide} + +\begin{slide} + \resetseq + \head{Key exchange \seq: Properties} + \topic{properties} + + \begin{itemize} + \item Simple -- symmetrical; based on mutual identification + \item Practical -- three, four or five flows; four multiplications by each + party + \item Secure -- provides SK-security in model of [CK01] + \item Deniable -- simulator can produce convincing transcripts + \item Proofs in random oracle model -- again without `programming' + \end{itemize} +\end{slide} + +\begin{slide} + \head{Key exchange \seq: Setting} + \topic{setting} + + \begin{itemize} + \item Cyclic group $(G, +)$ + \item $|G| = q$ is prime + \item $P$ generates $G$ + \item Alice's private key is $a \inr \Nupto{q}$; her public key is $A = a + P$ + \item Bob's private key is $b \inr \Nupto{q}$; his public key is $B = b + P$ + \item Symmetric IND-CCA encryption scheme $\E = (\kappa, E, D)$ + \item Assume computational Diffie-Hellman problem hard in $G$ + \end{itemize} +\end{slide} + +\begin{slide} + \head{Key exchange \seq: Broken first attempt} + \topic{protocol design} + + \begin{protocol} + Alice & Bob \\ + (Private key $a$, public key $A = a P$) & + \other (Private key $b$, public key $B = b P$) + \\[\medskipamount] + \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ + \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ + \\ + \\ + \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} + \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} + $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ + $Z \gets r_A R_B$; & $Z \gets r_B R_A$; \\ + \send{->}{(R_A, Y_B)} + \send{<-}{\other (R_B, Y_A)} + Key is $Z$ & Key is $Z$ + \end{protocol} +\end{slide} + +\begin{slide} + \head{Key exchange \seq: Solution -- encrypt responses} + + \begin{protocol} + Alice & Bob \\ + (Private key $a$, public key $A = a P$) & + \other (Private key $b$, public key $B = b P$) + \\[\medskipamount] + \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ + \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ + \\ + \\ + \send{<-}{(R_B, r_B \xor H(\cookie{check}, R_B, Y_B))} + \send{->}{\other (R_A, r_A \xor H(\cookie{check}, R_A, Y_A))} + $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ + \diff $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; & + \diff $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\ + \send{->}{(R_A, \hbox{\diff $E_{K_0}(Y_B)$})} + \send{<-}{\other (R_B, \hbox{\diff $E_{K_0}(Y_A)$})} + Key is $K_1$ & Key is $K_1$ + \end{protocol} +\end{slide} + +\begin{slide} + \head{Key exchange \seq: Multiple sessions} + + \begin{protocol} + Alice & Bob \\ + (Private key $a$, public key $A = a P$) & + \other (Private key $b$, public key $B = b P$) + \\[\medskipamount] + \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ + \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ + \\ + \\ + \send{<-}{(R_B, r_B \xor H(\cookie{check}, + \hbox{\diff $B$}, \hbox{\diff $s$}, R_B, Y_B))} + \send{->}{\other (R_A, r_A \xor H(\cookie{check}, + \hbox{\diff $A$}, \hbox{\diff $s$}, R_A, Y_A))} + $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ + $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; & + $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\ + \send{->}{(R_A, E_{K_0}(Y_B))} + \send{<-}{\other (R_B, E_{K_0}(Y_A))} + Key is $K_1$ & Key is $K_1$ + \end{protocol} + (Session id is $s$) +\end{slide} + +\begin{slide} + \head{Key exchange \seq: Fully deniable variant} + + \begin{protocol} + Alice & Bob \\ + (Private key $a$, public key $A = a P$) & + \other (Private key $b$, public key $B = b P$) + \\[\medskipamount] + \other $r_A \getsr \Nupto{q}$; & $r_B \getsr \Nupto{q}$; \\ + \other $R_A \gets r_A P$ & $R_B \gets r_B P$; \\ + \send{->}{\diff R_A} + \send{<-}{\diff R_B} + \send{<-}{(R_B, r_B \xor H(\cookie{check}, B, s, \hbox{\diff $R_A$}, R_B, Y_B))} + \send{->}{\other (R_A, r_A \xor H(\cookie{check}, A, s, \hbox{\diff $R_B$}, R_A, Y_A))} + $Y_B \gets a R_B$; & \other $Y_A \gets b R_B$; \\ + $(K_0, K_1) \gets H(\cookie{key}, r_A R_B)$; & + $(K_0, K_1) \gets H(\cookie{key}, r_B R_A)$; \\ + \send{->}{(R_A, E_{K_0}(Y_B))} + \send{<-}{\other (R_B, E_{K_0}(Y_A))} + Key is $K_1$ & Key is $K_1$ + \end{protocol} +\end{slide} + +\endinput + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "wrslides" +%%% End: diff --git a/wrslides.cls b/wrslides.cls new file mode 100644 index 0000000..1d7913e --- /dev/null +++ b/wrslides.cls @@ -0,0 +1,75 @@ +\PassOptionsToClass{a4, article}{mdwslides} +\LoadClass{mdwslides} + +\newif\ifpdf +\if0\ifx\pdfoutput\@@undefined0\else\the\expandafter\pdfoutput\fi + \PassOptionsToPackage{dvips}{xy} + \pdffalse +\else + \AtBeginDocument{ + \ifarticle\else + \setslidelength{\pdfpagewidth}{\paperheight} + \setslidelength{\pdfpageheight}{\paperwidth} + \pdfhorigin=1 true in + \pdfvorigin=1 true in + \fi + } + \pdftrue +\fi + + +\RequirePackage{mdwlist} +\RequirePackage[T1]{fontenc} +\RequirePackage{colour} +\RequirePackage{mdwmath} +\RequirePackage{crypto} +\RequirePackage[all]{xy} +\RequirePackage{tabularx} +\RequirePackage{mathenv} +\RequirePackage{graphicx} +\RequirePackage[palatino, helvetica, courier, maths = cmr]{mdwfonts} +\RequirePackage{mdwthm} + +\def\Nupto#1{\{0, 1, \ldots, #1 - 1\}} +\def\Bin{\{0, 1\}} +\let\op\star +\let\le\leqslant +\let\ge\geqslant +\let\epsilon\varepsilon + +\def\poly{\mathop{\operator@font{poly}}} + +\def\description{% + \basedescript{% + \let\makelabel\textit% + \desclabelstyle\multilinelabel% + \desclabelwidth{1in}% + }% +} + +\let\protocolstyle\small +\newskip\protocolskip +\protocolskip\parskip +\def\protocol{% + \protocolstyle% + \vskip\protocolskip% + \begin{tabular*}{\linewidth}{@{\qquad}l@{\extracolsep{0ptplus1fil}}r@{\qquad}}} +\def\endprotocol{\end{tabular*}} + +\makeatother +\def\send#1#2{\noalign{% + \centerline{\xy\ar @{#1}|*+{\mathstrut#2}<.5\linewidth, 0pt>\endxy}}} +\makeatletter +\errorcontextlines=999 + +\newcommand{\E}{{\mathcal{E}}} + +\def\Wident{\Xid{W}{ident}} +\def\Wkw{\Xid{W}{kx}} + +\def\other{\colour{blue}} +\def\diff{\colour{red}} + +\title{The Wrestlers Protocol} + +\endinput diff --git a/wrslides.tex b/wrslides.tex new file mode 100644 index 0000000..a444f79 --- /dev/null +++ b/wrslides.tex @@ -0,0 +1,32 @@ +\documentclass{wrslides} +\ifx\short\xxundefined\else + \includeonly{wrslide} +\fi + +\begin{document} + +\begin{slide} + \emptyslide + \hrule height0pt + \vfill + \centerline{\Huge\sffamily\bfseries The Wrestlers Protocol} + \medskip + \centerline{\itshape A simple, practical, secure, deniable protocol for + key-exchange} + \vskip 1in + \tabskip=0ptplus1fil + \halign to \linewidth{\tabskip=0pt\hfil\ignorespaces#\unskip\cr + Mark Wooding\cr + \texttt{mdw@distorted.org.uk}\cr} + \bigskip +\end{slide} + +\include{background} +\include{wrslide} + +\end{document} + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: t +%%% End: -- 2.11.0