-Our next objective is to show that pretending to be Alice is hard without
-knowledge of her secret $\alpha$. We say that an adversary $A$
-\emph{impersonates} in the Wrestlers Authentication Protocol with probability
-$\epsilon$ if
-\[ \Pr[A^{\oracle{H}(\cdot)}(g^\alpha, g^\beta,
- \beta \xor h(g^{\alpha\beta}))
- = g^{\alpha\beta}]
- = \epsilon
-\]
-where the probability is taken over all choices of $\alpha, \beta \in \{ 1,
-2, \ldots, q - 1 \}$ and random oracles $\oracle{H}$.
-
-\begin{theorem}
- Assuming that the Diffie-Hellman problem is hard in $G$, no probabilistic
- polynomial-time adversary can impersonate in the Wrestlers Authentication
- Protocol with random oracle with better than negligible probability.
- \label{thm:wap-dhp}
-\end{theorem}
-\begin{proof}
- \newcommand{\Hlist}{\textit{$\oracle{H}$-list}}
- \newcommand{\Hqueries}{\textit{$\oracle{H}$-queries}}
- \newcommand{\Hsim}{\textit{$\oracle{H}$-sim}}
- \renewcommand{\H}{\oracle{H}}
- %
- We prove the theorem by contradiction. Given a polynomial-time adversary
- $A$ which impersonates Alice with non-negligible probability $\epsilon$, we
- construct an adversary which solves the Diffie-Hellman problem with
- probability no less than $\epsilon \poly{k}$, i.e.,
- \[ \Pr[A'(g^\alpha, g^\beta) = g^{\alpha\beta}] \ge \epsilon \poly{k}. \]
- Thus, if there is any polynomial-time $A$ which impersonates with better
- than negligible probability, then there is a polynomial-time $A'$ which
- solves Diffie-Hellman with essentially the same probability, which would
- violate our assumption of the hardness of Diffie-Hellman.
-
- The idea behind the proof is that the check value is only useful to $A$
- once it has discovered the correct response to the challenge, which it must
- have done by solving the Diffie-Hellman problem. Hence, our Diffie-Hellman
-
- \begin{figure}
- \begin{program}
- \quad \= \kill
- Adversary $A'(a, b)$: \+ \\
- $\Hlist \gets \emptyset$; \\
- $\Hqueries \gets \emptyset$; \\
- $r \getsr \{ 0, 1 \}^k$; \\
- $x \gets A^{\Hsim(\cdot)}(a, b, r)$; \\
- $c \getsr (\Hlist \cup \{ x \}) \cap G$; \\
- \textbf{return} $c$; \- \\[\medskipamount]
- %
- Simulated random oracle $\Hsim(q)$: \+ \\
- \textbf{if} $\exists r : (q, r) \in \Hlist$
- \textbf{then} \textbf{return} $r$; \\
- $r \gets \{ 0, 1 \}^k$; \\
- $\Hlist \gets \Hlist \cup \{ (q, r) \}$; \\
- $\Hqueries \gets \Hqueries \cup \{ q \}$; \\
- \textbf{return} $r$;
- \end{program}
- %
- \caption{The algorithm for the proof of theorem~\ref{thm:wap-dhp}}
- \label{fig:wap-dhp-rdc}
- \end{figure}
-
- The adversary $A'$ is shown in figure~\ref{fig:wap-dhp-rdc}. It generates
- a random check-value and runs the impersonator $A$.
-
- The simulated random oracle $\Hsim$ gathers together the results of all of
- the random oracle queries made by $A$. The final result returned by $A'$
- is randomly chosen from among all of the `plausible' random oracle queries
- and $A$'s output, i.e., those queries which are actually members of the
- group. The check value given to $A$ is most likely incorrect (with
- probability $1 - 2^{-k}$): the intuition is that $A$ can only notice if it
- actually computes the right answer and then checks explicitly.
-
- If $A$ does compute the correct answer $g^{\alpha\beta}$ and either returns
- it or queries $\Hsim$ on it, then $A'$ succeeds with probability $\epsilon
- / |(\Hlist \cup \{ x \}) \cap G| = \epsilon \poly{k}$, since $|\Hlist|$ is
- no greater than the number of random oracle queries made by $A$ (which must
- be polynomially bounded).\footnote{%
- This polynomial factor introduces a loss in the perceived security of the
- authentication protocol. It appears that this loss is only caused by the
- possibility of the adversary $A$ being deliberately awkward and checking
- the value of $c$ after having computed the answer. However, we can't see
- a way to improve the security bound on the scheme without imposing
- artificial requirements on $A$.} %
+\subsection{Bit strings}
+
+Most of our notation for bit strings is standard. The main thing to note is
+that everything is zero-indexed.
+
+\begin{itemize}
+\item We write $\Bin = \{0, 1\}$ for the set of binary digits. Then $\Bin^n$
+ is the set of $n$-bit strings, and $\Bin^*$ is the set of all bit strings.
+\item If $x$ is a bit string then $|x|$ is the length of $x$. If $x \in
+ \Bin^n$ then $|x| = n$.
+\item If $x, y \in \Bin^n$ are strings of bits of the same length then $x
+ \xor y \in \Bin^n$ is their bitwise XOR.
+\item If $x$ and $y$ are bit strings then $x \cat y$ is the result of
+ concatenating $y$ to $x$. If $z = x \cat y$ then we have $|z| = |x| +
+ |y|$.
+\item The empty string is denoted $\emptystring$. We have $|\emptystring| =
+ 0$, and $x = x \cat \emptystring = \emptystring \cat x$ for all strings $x
+ \in \Bin^*$.
+\item If $x$ is a bit string and $i$ is an integer satisfying $0 \le i < |x|$
+ then $x[i]$ is the $i$th bit of $x$. If $a$ and $b$ are integers
+ satisfying $0 \le a \le b \le |x|$ then $x[a \bitsto b]$ is the substring
+ of $x$ beginning with bit $a$ and ending just \emph{before} bit $b$. We
+ have $|x[i]| = 1$ and $|x[a \bitsto b]| = b - a$; if $y = x[a \bitsto b]$
+ then $y[i] = x[a + i]$.
+\item If $x$ is a bit string and $n$ is a natural number then $x^n$ is the
+ result of concatenating $x$ to itself $n$ times. We have $x^0 =
+ \emptystring$ and if $n > 0$ then $x^n = x^{n-1} \cat x = x \cat x^{n-1}$.
+\end{itemize}
+
+\subsection{Other notation}
+
+\begin{itemize}
+\item If $n$ is any natural number, then $\Nupto{n}$ is the set $\{\, i \in
+ \Z \mid 0 \le i < n \,\} = \{ 0, 1, \ldots, n \}$.
+\item The symbol $\bot$ (`bottom') is different from every bit string and
+ group element.
+\item We write $\Func{l}{L}$ as the set of all functions from $\Bin^l$ to
+ $\Bin^L$, and $\Perm{l}$ as the set of all permutations on $\Bin^l$.
+\end{itemize}
+
+\subsection{Algorithm descriptions}
+
+Most of the notation used in the algorithm descriptions should be obvious.
+We briefly note a few features which may be unfamiliar.
+\begin{itemize}
+\item The notation $a \gets x$ denotes the action of assigning the value $x$
+ to the variable $a$.
+\item The notation $a \getsr X$, where $X$ is a finite set, denotes the
+ action of assigning to $a$ a random value $x \in X$ according to the
+ uniform probability distribution on $X$; i.e., following $a \getsr X$,
+ $\Pr[a = x] = 1/|X|$ for any $x \in X$.
+\end{itemize}
+The notation is generally quite sloppy about types and scopes. In
+particular, there are implicit coercions between bit strings, integers and
+group elements. Any simple injective mapping will do for handling the
+conversions. We don't think these informalities cause much confusion, and
+they greatly simplify the presentation of the algorithms.
+
+\subsection{Random oracles}
+
+We shall analyse the Wrestlers Protocol in the random oracle model
+\cite{Bellare:1993:ROP}. That is, each participant including the adversary
+is given oracle access (only) to a uniformly-distributed random function
+$H\colon \Bin^* \to \Bin^\infty$ chosen at the beginning of the game: for any
+input string $x$, the oracle can produce, on demand, any prefix of an
+infinitely long random answer $y = H(x)$. Repeating a query yields a prefix
+of the same random result string; asking a new query yields a prefix of a new
+randomly-chosen string.
+
+We shan't need either to query the oracle on very long input strings nor
+shall we need outputs much longer than a representation of a group index.
+Indeed, since all the programs we shall be dealing with run in finite time,
+and can therefore make only a finite number of oracle queries, each with a
+finitely long result, we can safely think about the random oracle as a finite
+object.
+
+Finally, we shall treat the oracle as a function of multiple inputs and
+expect it to operate on some unambiguous encoding of all of the arguments in
+order.
+
+\subsection{Symmetric encryption}
+
+\begin{definition}[Symmetric encryption]
+ \label{def:sym-enc}
+ A \emph{symmetric encryption scheme} $\mathcal{E} = (E, D)$ is a pair of
+ algorithms:
+ \begin{itemize}
+ \item a randomized \emph{encryption algorithm} $E\colon \keys \mathcal{E}
+ \times \Bin^* \to \Bin^*$; and
+ \item a deterministic \emph{decryption algorithm} $E\colon \keys
+ \mathcal{E} \times \Bin^* \to \Bin^* \cup \{ \bot \}$
+ \end{itemize}
+ with the property that, for any $K \in \keys \mathcal{E}$, any plaintext
+ message $x$, and any ciphertext $y$ returned as a result of $E_K(x)$, we
+ have $D_K(y) = x$.
+\end{definition}
+
+\begin{definition}[Chosen plaintext security for symmetric encryption]
+ \label{def:sym-cpa}
+ Let $\mathcal{E} = (E, D)$ be a symmetric encryption scheme. Let $A$ be
+ any algorithm. Define
+ \begin{program}
+ Experiment $\Expt{lor-cpa-$b$}{\mathcal{E}}(A)$: \+ \\
+ $K \getsr \keys \mathcal{E}$; \\
+ $b' \getsr A^{E_K(\id{lr}(b, \cdot, \cdot))}$; \\
+ \RETURN $b'$;
+ \next
+ Function $\id{lr}(b, x_0, x_1)$: \+ \\
+ \RETURN $x_b$;
+ \end{program}
+ An adversary $A$ is forbidden from querying its encryption oracle
+ $E_K(\id{lr}(b, \cdot, \cdot))$ on a pair of strings with differing
+ lengths. We define the adversary's \emph{advantage} in this game by
+ \begin{equation}
+ \Adv{lor-cpa}{\mathcal{E}}(A) =
+ \Pr[\Expt{lor-cpa-$1$}{\mathcal{E}}(A) = 1] -
+ \Pr[\Expt{lor-cpa-$0$}{\mathcal{E}}(A) = 1]
+ \end{equation}
+ and the \emph{left-or-right insecurity of $\mathcal{E}$ under
+ chosen-plaintext attack} is given by
+ \begin{equation}
+ \InSec{lor-cpa}(\mathcal{E}; t, q_E, \mu_E) =
+ \max_A \Adv{lor-cpa}{\mathcal{E}}(A)
+ \end{equation}
+ where the maximum is taken over all adversaries $A$ running in time $t$ and
+ making at most $q_E$ encryption queries, totalling most $\mu_E$ bits of
+ plaintext.
+\end{definition}
+
+\subsection{The decision Diffie-Hellman problem}
+
+Let $G$ be some cyclic group. The standard \emph{Diffie-Hellman problem}
+\cite{Diffie:1976:NDC} is to compute $g^{\alpha\beta}$ given $g^\alpha$ and
+$g^\beta$. We need a slightly stronger assumption: that, given $g^\alpha$
+and $g^\beta$, it's hard to tell the difference between the correct
+Diffie-Hellman value $g^{\alpha\beta}$ and a randomly-chosen group element
+$g^\gamma$. This is the \emph{decision Diffie-Hellman problem}
+\cite{Boneh:1998:DDP}.
+
+\begin{definition}
+ \label{def:ddh}
+ Let $G$ be a cyclic group of order $q$, and let $g$ be a generator of $G$.
+ Let $A$ be any algorithm. Then $A$'s \emph{advantage in solving the
+ decision Diffie-Hellman problem in $G$} is
+ \begin{equation}
+ \begin{eqnalign}[rl]
+ \Adv{ddh}{G}(A) =
+ & \Pr[\alpha \getsr \Nupto{q}; \beta \getsr \Nupto{q} :
+ A(g^\alpha, g^\beta, g^{\alpha\beta}) = 1] - {} \\
+ & \Pr[\alpha \getsr \Nupto{q}; \beta \getsr \Nupto{q};
+ \gamma \getsr \Nupto{q} :
+ A(g^\alpha, g^\beta, g^\gamma) = 1].
+ \end{eqnalign}
+ \end{equation}
+ The \emph{insecurity function of the decision Diffie-Hellman problem in
+ $G$} is
+ \begin{equation}
+ \InSec{ddh}(G; t) = \max_A \Adv{ddh}{G}(A)
+ \end{equation}
+ where the maximum is taken over all algorithms $A$ which run in time $t$.
+\end{definition}
+
+%%%--------------------------------------------------------------------------
+
+\section{The protocol}
+\label{sec:protocol}
+
+The Wrestlers Protocol is parameterized. We need the following things:
+\begin{itemize}
+\item A cyclic group $G$ whose order~$q$ is prime. Let $g$ be a generator
+ of~$G$. We require that the (decision?\fixme) Diffie-Hellman problem be
+ hard in~$G$. The group operation is written multiplicatively.
+\item A symmetric encryption scheme $\mathcal{E} = (E, D)$. We require that
+ $\mathcal{E}$ be secure against adaptive chosen-plaintext attacks. Our
+ implementation uses Blowfish \cite{Schneier:1994:BEA} in CBC mode with
+ ciphertext stealing. See section~\ref{sec:cbc} for a description of
+ ciphertext stealing and an analysis of its security.
+\item A message authentication scheme $\mathcal{M} = (T, V)$. We require
+ that $\mathcal{M}$ be (strongly) existentially unforgeable under
+ chosen-message attacks. Our implementation uses RIPEMD-160
+ \cite{Dobbertin:1996:RSV} in the HMAC \cite{Bellare:1996:HC} construction.
+\item An instantiation for the random oracle. We use RIPEMD-160 again,
+ either on its own, if the output is long enough, or in the MGF-1
+ \cite{RFC2437} construction, if we need a larger output.\footnote{%
+ The use of the same hash function in the MAC as for instantiating the
+ random oracle is deliberate, with the aim of reducing the number of
+ primitives whose security we must assume. In an application of HMAC, the
+ message to be hashed is prefixed by a secret key padded out to the hash
+ function's block size. In a `random oracle' query, the message is
+ prefixed by a fixed identification string and not padded. Interference
+ between the two is then limited to the case where one of the HMAC keys
+ matches a random oracle prefix, which happens only with very tiny
+ probability.}%
+\end{itemize}
+
+An authenticated encryption scheme with associated data (AEAD)
+\cite{Rogaway:2002:AEAD, Rogaway:2001:OCB, Kohno:2003:CWC} could be used
+instead of a separate symmetric encryption scheme and MAC.
+
+\subsection{Symmetric encryption}
+
+The same symmetric encryption subprotocol is used both within the key
+exchange, to ensure secrecy and binding, and afterwards for message
+transfer. It provides a secure channel between two players, assuming that
+the key was chosen properly.
+
+A \id{keyset} contains the state required for communication between the two
+players. In particular it maintains:
+\begin{itemize}
+\item separate encryption and MAC keys in each direction (four keys in
+ total), chosen using the random oracle based on an input key assumed to be
+ unpredictable by the adversary and a pair of nonces chosen by the two
+ players; and
+\item incoming and outgoing sequence numbers, to detect and prevent replay
+ attacks.
+\end{itemize}
+
+The operations involved in the symmetric encryption protocol are shown in
+figure~\ref{fig:keyset}.
+
+The \id{keygen} procedure initializes a \id{keyset}, resetting the sequence
+numbers, and selecting keys for the encryption scheme and MAC using the
+random oracle. It uses the nonces $r_A$ and $r_B$ to ensure that with high
+probability the keys are different for the two directions: assuming that
+Alice chose her nonce $r_A$ at random, and that the keys and nonce are
+$\kappa$~bits long, the probability that the keys in the two directions are
+the same is at most $2^{\kappa - 2}$.
+
+The \id{encrypt} procedure constructs a ciphertext from a message $m$ and a
+\emph{message type} $\id{ty}$. It encrypts the message giving a ciphertext
+$y$, and computes a MAC tag $\tau$ for the triple $(\id{ty}, i, y)$, where
+$i$ is the next available outgoing sequence number. The ciphertext message
+to send is then $(i, y, \tau)$. The message type codes are used to
+separate ciphertexts used by the key-exchange protocol itself from those sent
+by the players later.
+
+The \id{decrypt} procedure recovers the plaintext from a ciphertext triple
+$(i, y, \tau)$, given its expected type code $\id{ty}$. It verifies that the
+tag $\tau$ is valid for the message $(\id{ty}, i, y)$, checks that the
+sequence number $i$ hasn't been seen before,\footnote{%
+ The sequence number checking shown in the figure is simple but obviously
+ secure. The actual implementation maintains a window of 32 previous
+ sequence numbers, to allow out-of-order reception of messages while still
+ preventing replay attacks. This doesn't affect our analysis.}%
+and then decrypts the ciphertext $y$.
+
+\begin{figure}
+ \begin{program}
+ Structure $\id{keyset}$: \+ \\
+ $\Xid{K}{enc-in}$; $\Xid{K}{enc-out}$; \\
+ $\Xid{K}{mac-in}$; $\Xid{K}{mac-out}$; \\
+ $\id{seq-in}$; $\id{seq-out}$; \- \\[\medskipamount]
+ Function $\id{gen-keys}(r_A, r_B, K)$: \+ \\
+ $k \gets \NEW \id{keyset}$; \\
+ $k.\Xid{K}{enc-in} \gets H(\cookie{encryption}, r_A, r_B, K)$; \\
+ $k.\Xid{K}{enc-out} \gets H(\cookie{encryption}, r_B, r_A, K)$; \\
+ $k.\Xid{K}{mac-in} \gets H(\cookie{integrity}, r_A, r_B, K)$; \\
+ $k.\Xid{K}{mac-out} \gets H(\cookie{integrity}, r_B, r_A, K)$; \\
+ $k.\id{seq-in} \gets 0$; \\
+ $k.\id{seq-out} \gets 0$; \\
+ \RETURN $k$;
+ \next
+ Function $\id{encrypt}(k, \id{ty}, m)$: \+ \\
+ $y \gets (E_{k.\Xid{K}{enc-out}}(m))$; \\
+ $i \gets k.\id{seq-out}$; \\
+ $\tau \gets T_{k.\Xid{K}{mac-out}}(\id{ty}, i, y)$; \\
+ $k.\id{seq-out} \gets i + 1$; \\
+ \RETURN $(i, y, \tau)$; \- \\[\medskipamount]
+ Function $\id{decrypt}(k, \id{ty}, c)$: \+ \\
+ $(i, y, \tau) \gets c$; \\
+ \IF $V_{k.\Xid{K}{mac-in}}((\id{ty}, i, y), \tau) = 0$ \THEN \\ \ind
+ \RETURN $\bot$; \- \\
+ \IF $i < k.\id{seq-in}$ \THEN \RETURN $\bot$; \\
+ $m \gets D_{k.\Xid{K}{enc-in}}(y)$; \\
+ $k.\id{seq-in} \gets i + 1$; \\
+ \RETURN $m$;
+ \end{program}
+
+ \caption{Symmetric-key encryption functions}
+ \label{fig:keyset}
+\end{figure}
+
+\subsection{The key-exchange}
+
+The key-exchange protocol is completely symmetrical. Either party may
+initiate, or both may attempt to converse at the same time. We shall
+describe the protocol from the point of view of Alice attempting to exchange
+a key with Bob.
+
+Alice's private key is a random index $\alpha \inr \Nupto{q}$. Her public
+key is $a = g^\alpha$. Bob's public key is $b \in G$. We'll subscript the
+variables Alice computes with an~$A$, and the values Bob has sent with a~$B$.
+Of course, if Bob is following the protocol correctly, he will have computed
+his $B$ values in a completely symmetrical way.
+
+There are six messages in the protocol, and we shall briefly discuss the
+purpose of each before embarking on the detailed descriptions. At the
+beginning of the protocol, Alice chooses a new random index $\rho_A$ and
+computes her \emph{challenge} $r_A = g^{\rho_A}$. Eventually, the shared
+secret key will be computed as $K = r_B^{\rho_A} = r_A^{\rho_B} =
+g^{\rho_A\rho_B}$, as for standard Diffie-Hellman key agreement.
+
+Throughout, we shall assume that messages are implicitly labelled with the
+sender's identity. If Alice is actually trying to talk to several other
+people she'll need to run multiple instances of the protocol, each with its
+own state, and she can use the sender label to decide which instance a
+message should be processed by. There's no need for the implicit labels to
+be attached securely.
+
+We'll summarize the messages and their part in the scheme of things before we
+start on the serious detail. For a summary of the names and symbols used in
+these descriptions, see table~\ref{tab:kx-names}. The actual message
+contents are summarized in table~\ref{tab:kx-messages}. A state-transition
+diagram of the protocol is shown in figure~\ref{fig:kx-states}. If reading
+pesudocode algorithms is your thing then you'll find message-processing
+procedures in figure~\ref{fig:kx-messages} with the necessary support procedures
+in figure~\ref{fig:kx-support}.
+
+\begin{table}
+ \begin{tabularx}{\textwidth}{Mr X}
+ G & A cyclic group known by all participants \\
+ q = |G| & The prime order of $G$ \\
+ g & A generator of $G$ \\
+ E_K(\cdot) & Encryption under key $K$, here used to denote
+ application of the $\id{encrypt}(K, \cdot)$
+ operation \\
+ \alpha \inr \Nupto{q} & Alice's private key \\
+ a = g^{\alpha} & Alice's public key \\
+ \rho_A \inr \Nupto{q} & Alice's secret Diffie-Hellman value \\
+ r_A = g^{\rho_A} & Alice's public \emph{challenge} \\
+ c_A = H(\cookie{cookie}, r_A)
+ & Alice's \emph{cookie} \\
+ v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A})
+ & Alice's challenge \emph{check value} \\
+ r_B^\alpha = a^{\rho_B}
+ & Alice's reply \\
+ K = r_B^{\rho_A} = r_B^{\rho_A} = g^{\rho_A\rho_B}
+ & Alice and Bob's shared secret key \\
+ w_A = H(\cookie{switch-request}, c_A, c_B)
+ & Alice's \emph{switch request} value \\
+ u_A = H(\cookie{switch-confirm}, c_A, c_B)
+ & Alice's \emph{switch confirm} value \\
+ \end{tabularx}
+
+ \caption{Names used during key-exchange}
+ \label{tab:kx-names}
+\end{table}
+
+\begin{table}
+ \begin{tabular}[C]{Ml}
+ \cookie{kx-pre-challenge}, r_A \\
+ \cookie{kx-cookie}, r_A, c_B \\
+ \cookie{kx-challenge}, r_A, c_B, v_A \\
+ \cookie{kx-reply}, c_A, c_B, v_A, E_K(r_B^\alpha)) \\
+ \cookie{kx-switch}, c_A, c_B, E_K(r_B^\alpha, w_A)) \\
+ \cookie{kx-switch-ok}, E_K(u_A))
+ \end{tabular}
+
+ \caption{Message contents, as sent by Alice}
+ \label{tab:kx-messages}
+\end{table}