+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}
+
+\begin{messages}
+\item[kx-pre-challenge] Contains a plain statement of Alice's challenge.
+ This is Alice's first message of a session.
+\item[kx-cookie] A bare acknowledgement of a received challenge: it restates
+ Alice's challenge, and contains a hash of Bob's challenge. This is an
+ engineering measure (rather than a cryptographic one) which prevents
+ trivial denial-of-service attacks from working.
+\item[kx-challenge] A full challenge, with a `check value' which proves the
+ challenge's honesty. Bob's correct reply to this challenge informs Alice
+ that she's received his challenge correctly.
+\item[kx-reply] A reply. This contains a `check value', like the
+ \cookie{kx-challenge} message above, and an encrypted reply which confirms
+ to Bob Alice's successful receipt of his challenge and lets Bob know he
+ received Alice's challenge correctly.
+\item[kx-switch] Acknowledges Alice's receipt of Bob's \cookie{kx-reply}
+ message, including Alice's own reply to Bob's challenge. Tells Bob that
+ she can start using the key they've agreed.
+\item[kx-switch-ok] Acknowlegement to Bob's \cookie{kx-switch} message.
+\end{messages}
+
+\begin{figure}
+ \small
+ \let\ns\normalsize
+ \let\c\cookie
+ \[ \begin{graph}
+ []!{0; <4.5cm, 0cm>: <0cm, 1.5cm>::}
+ *++[F:<4pt>]\txt{\ns Start \\ Choose $\rho_A$} ="start"
+ :[dd]
+ *++[F:<4pt>]\txt{
+ \ns State \c{challenge} \\
+ Send $(\c{pre-challenge}, r_A)$}
+ ="chal"
+ [] "chal" !{!L(0.5)} ="chal-cookie"
+ :@(d, d)[l]
+ *+\txt{Send $(\c{cookie}, r_A, c_B)$}
+ ="cookie"
+ |*+\txt{Receive \\ $(\c{pre-challenge}, r_B)$ \\ (no spare slot)}
+ :@(u, u)"chal-cookie"
+ "chal" :@/_0.8cm/ [ddddl]
+ *+\txt{Send \\ $(\c{challenge}, $\\$ r_A, c_B, v_A)$}
+ ="send-chal"
+ |<>(0.67) *+\txt\small{
+ Receive \\ $(\c{pre-challenge}, r_B)$ \\ (spare slot)}
+ "chal" :@/^0.8cm/ "send-chal" |<>(0.33)
+ *+\txt{Receive \\ $(\c{cookie}, r_B, c_A)$}
+ :[rr]
+ *+\txt{Send \\ $(\c{reply}, c_A, c_B, $\\$ v_A, E_K(r_B^\alpha))$}
+ ="send-reply"
+ |*+\txt{Receive \\ $(\c{challenge}, $\\$ r_B, c_A, v_B)$}
+ "chal" :"send-reply"
+ |*+\txt{Receive \\ $(\c{challenge}, $\\$ r_B, c_A, v_B)$}
+ "send-chal" :[ddd]
+ *++[F:<4pt>]\txt{
+ \ns State \c{commit} \\
+ Send \\ $(\c{switch}, c_A, c_B, $\\$ E_K(r_B^\alpha, w_A))$}
+ ="commit"
+ |*+\txt{Receive \\ $(\c{reply}, c_B, c_A, $\\$ v_B, E_K(b^{\rho_A}))$}
+ :[rr]
+ *+\txt{Send \\ $(\c{switch-ok}, E_K(u_A))$}
+ ="send-switch-ok"
+ |*+\txt{Receive \\ $(\c{switch}, c_B, c_A, $\\$ E_K(b^{\rho_A}, w_B))$}
+ "send-reply" :"commit"
+ |*+\txt{Receive \\ $(\c{reply}, c_B, c_A, $\\$ v_B, E_K(b^{\rho_A}))$}
+ "send-reply" :"send-switch-ok"
+ |*+\txt{Receive \\ $(\c{switch}, c_B, c_A, $\\$ E_K(b^{\rho_A}, w_B))$}
+ :[dddl]
+ *++[F:<4pt>]\txt{\ns Done}
+ ="done"
+ "commit" :"done"
+ |*+\txt{Receive \\ $(\c{switch-ok}, E_K(u_B))$}
+ "send-chal" [r] !{+<0cm, 0.75cm>}
+ *\txt\itshape{For each outstanding challenge}
+ ="for-each"
+ !{"send-chal"+DL-<8pt, 8pt> ="p0",
+ "for-each"+U+<8pt> ="p1",
+ "send-reply"+UR+<8pt, 8pt> ="p2",
+ "send-reply"+DR+<8pt, 8pt> ="p3",
+ "p0" !{"p1"-"p0"} !{"p2"-"p1"} !{"p3"-"p2"}
+ *\frm<8pt>{--}}
+ \end{graph} \]
+
+ \caption{State-transition diagram for key-exchange protocol}
+ \label{fig:kx-states}
+\end{figure}
+
+We now describe the protocol message by message, and Alice's actions when she
+receives each. Since the protocol is completely symmetrical, Bob should do
+the same, only swapping round $A$ and $B$ subscripts, the public keys $a$ and
+$b$, and using his private key $\beta$ instead of $\alpha$.
+
+\subsubsection{Starting the protocol}
+
+As described above, at the beginning of the protocol Alice chooses a random
+$\rho_A \inr \Nupto q$, and computes her \emph{challenge} $r_A = g^{\rho_A}$
+and her \emph{cookie} $c_A = H(\cookie{cookie}, r_A)$. She sends her
+announcement of her challenge as
+\begin{equation}
+ \label{eq:kx-pre-challenge}
+ \cookie{kx-pre-challenge}, r_A
+\end{equation}
+and enters the \cookie{challenge} state.
+
+\subsubsection{The \cookie{kx-pre-challenge} message}
+
+If Alice receieves a \cookie{kx-pre-challenge}, she ensures that she's in the
+\cookie{challenge} state: if not, she rejects the message.
+
+She must first calculate Bob's cookie $c_B = H(\cookie{cookie}, r_B)$. Then
+she has a choice: either she can send a full challenge, or she can send the
+cookie back.
+
+Suppose she decides to send a full challenge. She must compute a \emph{check
+value}
+\begin{equation}
+ \label{eq:v_A}
+ v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A})
+\end{equation}
+and sends
+\begin{equation}
+ \label{eq:kx-challenge}
+ \cookie{kx-challenge}, r_A, c_B, v_A
+\end{equation}
+to Bob. Then she remembers Bob's challenge for later use, and awaits his
+reply.
+
+If she decides to send only a cookie, she just transmits
+\begin{equation}
+ \label{eq:kx-cookie}
+ \cookie{kx-cookie}, r_A, c_B
+\end{equation}
+to Bob and forgets all about it.
+
+Why's this useful? Well, if Alice sends off a full \cookie{kx-challenge}
+message, she must remember Bob's $r_B$ so she can check his reply and that
+involves using up a table slot. That means that someone can send Alice
+messages purporting to come from Bob which will chew up Alice's memory, and
+they don't even need to be able to read Alice's messages to Bob to do that.
+If this protocol were used over the open Internet, script kiddies from all
+over the world might be flooding Alice with bogus \cookie{kx-pre-challenge}
+messages and she'd never get around to talking to Bob.
+
+By sending a cookie intead, she avoids committing a table slot until Bob (or
+someone) sends either a cookie or a full challenge, thus proving, at least,
+that he can read her messages. This is the best we can do at this stage in
+the protocol. Against an adversary as powerful as the one we present in
+section~\fixme\ref{sec:formal} this measure provides no benefit (but we have
+to analyse it anyway); but it raises the bar too sufficiently high to
+eliminate a large class of `nuisance' attacks in the real world.
+
+Our definition of the Wrestlers Protocol doesn't stipulate when Alice should
+send a full challenge or just a cookie: we leave this up to individual
+implementations, because it makes no difference to the security of the
+protocol against powerful adversaries. But we recommend that Alice proceed
+`optimistically' at first, sending full challenges until her challenge table
+looks like it's running out, and then generating cookies only if it actually
+looks like she's under attack. This is what our pseudocode in
+figure~\ref{fig:kx-messages} does.
+
+\subsubsection{The \cookie{kx-cookie} message}
+
+When Alice receives a \cookie{kx-cookie} message, she must ensure that she's
+in the \cookie{challenge} state: if not, she rejects the message. She checks
+the cookie in the message against the value of $c_A$ she computed earlier.
+If all is well, Alice sends a \cookie{kx-challenge} message, as in
+equation~\ref{eq:kx-challenge} above.
+
+This time, she doesn't have a choice about using up a table slot to remember
+Bob's $r_B$. If her table size is fixed, she must choose a slot to recycle.
+We suggest simply recycling slots at random: this means there's no clever
+pattern of \cookie{kx-cookie} messages an attacker might be able to send to
+clog up all of Alice's slots.
+
+\subsubsection{The \cookie{kx-challenge} message}
+
+
+
+\begin{figure}
+ \begin{program}
+ Procedure $\id{kx-initialize}$: \+ \\
+ $\rho_A \getsr [q]$; \\
+ $r_a \gets g^{\rho_A}$; \\
+ $\id{state} \gets \cookie{challenge}$; \\
+ $\Xid{n}{chal} \gets 0$; \\
+ $k \gets \bot$; \\
+ $\id{chal-commit} \gets \bot$; \\
+ $\id{send}(\cookie{kx-pre-challenge}, r_A)$; \- \\[\medskipamount]
+ Procedure $\id{kx-receive}(\id{type}, \id{data})$: \\ \ind
+ \IF $\id{type} = \cookie{kx-pre-challenge}$ \THEN \\ \ind
+ \id{msg-pre-challenge}(\id{data}); \- \\
+ \ELSE \IF $\id{type} = \cookie{kx-cookie}$ \THEN \\ \ind
+ \id{msg-cookie}(\id{data}); \- \\
+ \ELSE \IF $\id{type} = \cookie{kx-challenge}$ \THEN \\ \ind
+ \id{msg-challenge}(\id{data}); \- \\
+ \ELSE \IF $\id{type} = \cookie{kx-reply}$ \THEN \\ \ind
+ \id{msg-reply}(\id{data}); \- \\
+ \ELSE \IF $\id{type} = \cookie{kx-switch}$ \THEN \\ \ind
+ \id{msg-switch}(\id{data}); \- \\
+ \ELSE \IF $\id{type} = \cookie{kx-switch-ok}$ \THEN \\ \ind
+ \id{msg-switch-ok}(\id{data}); \-\- \\[\medskipamount]
+ Procedure $\id{msg-pre-challenge}(\id{data})$: \+ \\
+ \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\
+ $r \gets \id{data}$; \\
+ \IF $\Xid{n}{chal} \ge \Xid{n}{chal-thresh}$ \THEN \\ \ind
+ $\id{send}(\cookie{kx-cookie}, r_A, \id{cookie}(r_A)))$; \- \\
+ \ELSE \+ \\
+ $\id{new-chal}(r)$; \\
+ $\id{send}(\cookie{kx-challenge}, r_A,
+ \id{cookie}(r), \id{checkval}(r))$; \-\-\\[\medskipamount]
+ Procedure $\id{msg-cookie}(\id{data})$: \+ \\
+ \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\
+ $(r, c_A) \gets \id{data}$; \\
+ \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\
+ $\id{new-chal}(r)$; \\
+ $\id{send}(\cookie{kx-challenge}, r_A,
+ \id{cookie}(r), \id{checkval}(r))$; \- \\[\medskipamount]
+ Procedure $\id{msg-challenge}(\id{data})$: \+ \\
+ \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\
+ $(r, c_A, v) \gets \id{data}$; \\
+ \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\
+ $i \gets \id{check-reply}(\bot, r, v)$; \\
+ \IF $i = \bot$ \THEN \RETURN; \\
+ $k \gets \id{chal-tab}[i].k$; \\
+ $y \gets \id{encrypt}(k, \cookie{kx-reply}, r^\alpha)$; \\
+ $\id{send}(\cookie{kx-reply}, c_A, \id{cookie}(r),
+ \id{checkval}(r), y)$
+ \next
+ Procedure $\id{msg-reply}(\id{data})$: \+ \\
+ $(c, c_A, v, y) \gets \id{data}$; \\
+ \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\
+ $i \gets \id{find-chal}(c)$; \\
+ \IF $i = \bot$ \THEN \RETURN; \\
+ \IF $\id{check-reply}(i, \id{chal-tab}[i].r, v) = \bot$ \THEN \\ \ind
+ \RETURN; \- \\
+ $k \gets \id{chal-tab}[i].k$; \\
+ $x \gets \id{decrypt}(k, \cookie{kx-reply}, y)$; \\
+ \IF $x = \bot$ \THEN \RETURN; \\
+ \IF $x \ne b^{\rho_A}$ \THEN \RETURN; \\
+ $\id{state} \gets \cookie{commit}$; \\
+ $\id{chal-commit} \gets \id{chal-tab}[i]$; \\
+ $w \gets H(\cookie{switch-request}, c_A, c)$; \\
+ $x \gets \id{chal-tab}[i].r^\alpha$; \\
+ $y \gets \id{encrypt}(k, (x, \cookie{kx-switch}, w))$; \\
+ $\id{send}(\cookie{kx-switch}, c_A, c, y)$; \-\\[\medskipamount]
+ Procedure $\id{msg-switch}(\id{data})$: \+ \\
+ $(c, c_A, y) \gets \id{data}$; \\
+ \IF $c_A \ne \cookie(r_A)$ \THEN \RETURN; \\
+ $i \gets \id{find-chal}(c)$; \\
+ \IF $i = \bot$ \THEN \RETURN; \\
+ $k \gets \id{chal-tab}[i].k$; \\
+ $x \gets \id{decrypt}(k, \cookie{kx-switch}, y)$; \\
+ \IF $x = \bot$ \THEN \RETURN; \\
+ $(x, w) \gets x$; \\
+ \IF $\id{state} = \cookie{challenge}$ \THEN \\ \ind
+ \IF $x \ne b^{\rho_A}$ \THEN \RETURN; \\
+ $\id{chal-commit} \gets \id{chal-tab}[i]$; \- \\
+ \ELSE \IF $c \ne \id{chal-commit}.c$ \THEN \RETURN; \\
+ \IF $w \ne H(\cookie{switch-request}, c, c_A)$ \THEN \RETURN; \\
+ $w \gets H(\cookie{switch-confirm}, c_A, c)$; \\
+ $y \gets \id{encrypt}(y, \cookie{kx-switch-ok}, w)$; \\
+ $\id{send}(\cookie{switch-ok}, y)$; \\
+ $\id{done}(k)$; \- \\[\medskipamount]
+ Procedure $\id{msg-switch-ok}(\id{data})$ \+ \\
+ \IF $\id{state} \ne \cookie{commit}$ \THEN \RETURN; \\
+ $y \gets \id{data}$; \\
+ $k \gets \id{chal-commit}.k$; \\
+ $w \gets \id{decrypt}(k, \cookie{kx-switch-ok}, y)$; \\
+ \IF $w = \bot$ \THEN \RETURN; \\
+ $c \gets \id{chal-commit}.c$; \\
+ $c_A \gets \id{cookie}(r_A)$; \\
+ \IF $w \ne H(\cookie{switch-confirm}, c, c_A)$ \THEN \RETURN; \\
+ $\id{done}(k)$;
+ \end{program}
+
+ \caption{The key-exchange protocol: message handling}
+ \label{fig:kx-messages}
+\end{figure}
+
+\begin{figure}
+ \begin{program}
+ Structure $\id{chal-slot}$: \+ \\
+ $r$; $c$; $\id{replied}$; $k$; \- \\[\medskipamount]
+ Function $\id{find-chal}(c)$: \+ \\
+ \FOR $i = 0$ \TO $\Xid{n}{chal}$ \DO \\ \ind
+ \IF $\id{chal-tab}[i].c = c$ \THEN \RETURN $i$; \- \\
+ \RETURN $\bot$; \- \\[\medskipamount]
+ Function $\id{cookie}(r)$: \+ \\
+ \RETURN $H(\cookie{cookie}, r)$; \- \\[\medskipamount]
+ Function $\id{check-reply}(i, r, v)$: \+ \\
+ \IF $i \ne \bot \land \id{chal-tab}[i].\id{replied} = 1$ \THEN \\ \ind
+ \RETURN $i$; \- \\
+ $\rho \gets v \xor H(\cookie{expected-reply}, r, r_A, r^\alpha)$; \\
+ \IF $g^\rho \ne r$ \THEN \RETURN $\bot$; \\
+ \IF $i = \bot$ \THEN $i \gets \id{new-chal}(r)$; \\
+ $\id{chal-tab}[i].k \gets \id{gen-keys}(r_A, r, r^{\rho_A})$; \\
+ $\id{chal-tab}[i].\id{replied} \gets 1$; \\
+ \RETURN $i$;
+ \next
+ Function $\id{checkval}(r)$: \\ \ind
+ \RETURN $\rho_A \xor H(\cookie{expected-reply},
+ r_A,r, b^{\rho_A})$; \- \\[\medskipamount]
+ Function $\id{new-chal}(r)$: \+ \\
+ $c \gets \id{cookie}(r)$; \\
+ $i \gets \id{find-chal}(c)$; \\
+ \IF $i \ne \bot$ \THEN \RETURN $i$; \\
+ \IF $\Xid{n}{chal} < \Xid{n}{chal-max}$ \THEN \\ \ind
+ $i \gets \Xid{n}{chal}$; \\
+ $\id{chal-tab}[i] \gets \NEW \id{chal-slot}$; \\
+ $\Xid{n}{chal} \gets \Xid{n}{chal} + 1$; \- \\
+ \ELSE \\ \ind
+ $i \getsr [\Xid{n}{chal-max}]$; \- \\
+ $\id{chal-tab}[i].r \gets r$; \\
+ $\id{chal-tab}[i].c \gets c$; \\
+ $\id{chal-tab}[i].\id{replied} \gets 0$; \\
+ $\id{chal-tab}[i].k \gets \bot$; \\
+ \RETURN $i$;
+ \end{program}
+
+ \caption{The key-exchange protocol: support functions}
+ \label{fig:kx-support}
+\end{figure}