chiark / gitweb /
Release 1.5.0.
[tripe] / doc / wrestlers.tex
1 %%% -*-latex-*-
2 %%%
3 %%% Description of the Wrestlers Protocol
4 %%%
5 %%% (c) 2001 Mark Wooding
6 %%%
7
8 \newif\iffancystyle\fancystyletrue
9
10 \iffancystyle
11   \documentclass
12     [a4paper, article, 10pt, numbering, noherefloats, notitlepage]
13     {strayman}
14   \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
15   \usepackage[mdwmargin]{mdwthm}
16   \PassOptionsToPackage{dvips}{xy}
17 \else
18   \documentclass{llncs}
19 \fi
20
21 \usepackage{mdwtab, mathenv, mdwlist, mdwmath, crypto}
22 \usepackage{amssymb, amstext}
23 \usepackage{tabularx}
24 \usepackage{url}
25 \usepackage[all]{xy}
26
27 \errorcontextlines=999
28 \showboxbreadth=999
29 \showboxdepth=999
30 \makeatletter
31
32 \title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
33 \author{Mark Wooding \and Clive Jones}
34
35 \bibliographystyle{mdwalpha}
36
37 \newcolumntype{G}{p{0pt}}
38 \def\Nupto#1{\N_{<{#1}}}
39 \let\Bin\Sigma
40 \let\epsilon\varepsilon
41 \let\emptystring\lambda
42 \def\bitsto{\mathbin{..}}
43 \turnradius{4pt}
44 \def\fixme{\marginpar{FIXME}}
45 \def\messages{%
46   \basedescript{%
47     \desclabelwidth{2.5cm}%
48     \desclabelstyle\pushlabel%
49     \let\makelabel\cookie%
50   }%
51 }
52 \let\endmessages\endbasedescript
53
54 \begin{document}
55
56 \maketitle
57 \begin{abstract}
58   The Wrestlers Protocol\footnote{%
59     `The Wrestlers' is a pub in Cambridge which serves good beer and
60     excellent Thai food.  It's where the authors made their first attempts at
61     a secure key-exchange protocol which doesn't use signatures.} %
62   is a key-exchange protocol with the interesting property that it leaves no
63   evidence which could be used to convince a third party that any of the
64   participants are involved.  We describe the protocol and prove its security
65   in the random oracle model.
66
67   Almost incidentally, we provide a new security proof for the CBC encryption
68   mode.  Our proof is much simpler than that of \cite{Bellare:2000:CST}, and
69   gives a slightly better security bound.
70
71   % I've not yet decided whose key-exchange model to use, but this ought to
72   % be mentioned.
73 \end{abstract}
74 \tableofcontents
75 \newpage
76
77 %%%--------------------------------------------------------------------------
78
79 \section{Introduction}
80 \label{sec:intro}
81 % Some waffle here about the desirability of a key-exchange protocol that
82 % doesn't leave signatures lying around, followed by an extended report of
83 % the various results.
84
85 %%%--------------------------------------------------------------------------
86
87 \section{Preliminaries}
88 \label{sec:prelim}
89 % Here we provide definitions of the various kinds of things we use and make,
90 % and describe some of the notation we use.
91
92 \subsection{Bit strings}
93
94 Most of our notation for bit strings is standard.  The main thing to note is
95 that everything is zero-indexed.
96
97 \begin{itemize}
98 \item We write $\Bin = \{0, 1\}$ for the set of binary digits.  Then $\Bin^n$
99   is the set of $n$-bit strings, and $\Bin^*$ is the set of all bit strings.
100 \item If $x$ is a bit string then $|x|$ is the length of $x$.  If $x \in
101   \Bin^n$ then $|x| = n$.
102 \item If $x, y \in \Bin^n$ are strings of bits of the same length then $x
103   \xor y \in \Bin^n$ is their bitwise XOR.
104 \item If $x$ and $y$ are bit strings then $x \cat y$ is the result of
105   concatenating $y$ to $x$.  If $z = x \cat y$ then we have $|z| = |x| +
106   |y|$.
107 \item The empty string is denoted $\emptystring$.  We have $|\emptystring| =
108   0$, and $x = x \cat \emptystring = \emptystring \cat x$ for all strings $x
109   \in \Bin^*$.
110 \item If $x$ is a bit string and $i$ is an integer satisfying $0 \le i < |x|$
111   then $x[i]$ is the $i$th bit of $x$.  If $a$ and $b$ are integers
112   satisfying $0 \le a \le b \le |x|$ then $x[a \bitsto b]$ is the substring
113   of $x$ beginning with bit $a$ and ending just \emph{before} bit $b$.  We
114   have $|x[i]| = 1$ and $|x[a \bitsto b]| = b - a$; if $y = x[a \bitsto b]$
115   then $y[i] = x[a + i]$.
116 \item If $x$ is a bit string and $n$ is a natural number then $x^n$ is the
117   result of concatenating $x$ to itself $n$ times.  We have $x^0 =
118   \emptystring$ and if $n > 0$ then $x^n = x^{n-1} \cat x = x \cat x^{n-1}$.
119 \end{itemize}
120
121 \subsection{Other notation}
122
123 \begin{itemize}
124 \item If $n$ is any natural number, then $\Nupto{n}$ is the set $\{\, i \in
125   \Z \mid 0 \le i < n \,\} = \{ 0, 1, \ldots, n \}$.
126 \item The symbol $\bot$ (`bottom') is different from every bit string and
127   group element.
128 \item We write $\Func{l}{L}$ as the set of all functions from $\Bin^l$ to
129   $\Bin^L$, and $\Perm{l}$ as the set of all permutations on $\Bin^l$.
130 \end{itemize}
131
132 \subsection{Algorithm descriptions}
133
134 Most of the notation used in the algorithm descriptions should be obvious.
135 We briefly note a few features which may be unfamiliar.
136 \begin{itemize}
137 \item The notation $a \gets x$ denotes the action of assigning the value $x$
138   to the variable $a$.
139 \item The notation $a \getsr X$, where $X$ is a finite set, denotes the
140   action of assigning to $a$ a random value $x \in X$ according to the
141   uniform probability distribution on $X$; i.e., following $a \getsr X$,
142   $\Pr[a = x] = 1/|X|$ for any $x \in X$.
143 \end{itemize}
144 The notation is generally quite sloppy about types and scopes.  In
145 particular, there are implicit coercions between bit strings, integers and
146 group elements.  Any simple injective mapping will do for handling the
147 conversions.  We don't think these informalities cause much confusion, and
148 they greatly simplify the presentation of the algorithms.
149
150 \subsection{Random oracles}
151
152 We shall analyse the Wrestlers Protocol in the random oracle model
153 \cite{Bellare:1993:ROP}.  That is, each participant including the adversary
154 is given oracle access (only) to a uniformly-distributed random function
155 $H\colon \Bin^* \to \Bin^\infty$ chosen at the beginning of the game: for any
156 input string $x$, the oracle can produce, on demand, any prefix of an
157 infinitely long random answer $y = H(x)$.  Repeating a query yields a prefix
158 of the same random result string; asking a new query yields a prefix of a new
159 randomly-chosen string.
160
161 We shan't need either to query the oracle on very long input strings nor
162 shall we need outputs much longer than a representation of a group index.
163 Indeed, since all the programs we shall be dealing with run in finite time,
164 and can therefore make only a finite number of oracle queries, each with a
165 finitely long result, we can safely think about the random oracle as a finite
166 object.
167
168 Finally, we shall treat the oracle as a function of multiple inputs and
169 expect it to operate on some unambiguous encoding of all of the arguments in
170 order.
171
172 \subsection{Symmetric encryption}
173
174 \begin{definition}[Symmetric encryption]
175   \label{def:sym-enc}
176   A \emph{symmetric encryption scheme} $\mathcal{E} = (E, D)$ is a pair of
177   algorithms:
178   \begin{itemize}
179   \item a randomized \emph{encryption algorithm} $E\colon \keys \mathcal{E}
180     \times \Bin^* \to \Bin^*$; and
181   \item a deterministic \emph{decryption algorithm} $E\colon \keys
182     \mathcal{E} \times \Bin^* \to \Bin^* \cup \{ \bot \}$
183   \end{itemize}
184   with the property that, for any $K \in \keys \mathcal{E}$, any plaintext
185   message $x$, and any ciphertext $y$ returned as a result of $E_K(x)$, we
186   have $D_K(y) = x$.
187 \end{definition}
188
189 \begin{definition}[Chosen plaintext security for symmetric encryption]
190   \label{def:sym-cpa}
191   Let $\mathcal{E} = (E, D)$ be a symmetric encryption scheme.  Let $A$ be
192   any algorithm.  Define
193   \begin{program}
194     Experiment $\Expt{lor-cpa-$b$}{\mathcal{E}}(A)$: \+ \\
195       $K \getsr \keys \mathcal{E}$; \\
196       $b' \getsr A^{E_K(\id{lr}(b, \cdot, \cdot))}$; \\
197       \RETURN $b'$;
198     \next
199     Function $\id{lr}(b, x_0, x_1)$: \+ \\
200       \RETURN $x_b$;
201   \end{program}
202   An adversary $A$ is forbidden from querying its encryption oracle
203   $E_K(\id{lr}(b, \cdot, \cdot))$ on a pair of strings with differing
204   lengths.  We define the adversary's \emph{advantage} in this game by
205   \begin{equation}
206     \Adv{lor-cpa}{\mathcal{E}}(A) =
207       \Pr[\Expt{lor-cpa-$1$}{\mathcal{E}}(A) = 1] -
208       \Pr[\Expt{lor-cpa-$0$}{\mathcal{E}}(A) = 1]
209   \end{equation}
210   and the \emph{left-or-right insecurity of $\mathcal{E}$ under
211   chosen-plaintext attack} is given by
212   \begin{equation}
213     \InSec{lor-cpa}(\mathcal{E}; t, q_E, \mu_E) =
214       \max_A \Adv{lor-cpa}{\mathcal{E}}(A)
215   \end{equation}
216   where the maximum is taken over all adversaries $A$ running in time $t$ and
217   making at most $q_E$ encryption queries, totalling most $\mu_E$ bits of
218   plaintext.
219 \end{definition}
220
221 \subsection{The decision Diffie-Hellman problem}
222
223 Let $G$ be some cyclic group.  The standard \emph{Diffie-Hellman problem}
224 \cite{Diffie:1976:NDC} is to compute $g^{\alpha\beta}$ given $g^\alpha$ and
225 $g^\beta$.  We need a slightly stronger assumption: that, given $g^\alpha$
226 and $g^\beta$, it's hard to tell the difference between the correct
227 Diffie-Hellman value $g^{\alpha\beta}$ and a randomly-chosen group element
228 $g^\gamma$.  This is the \emph{decision Diffie-Hellman problem}
229 \cite{Boneh:1998:DDP}.
230
231 \begin{definition}
232   \label{def:ddh}
233   Let $G$ be a cyclic group of order $q$, and let $g$ be a generator of $G$.
234   Let $A$ be any algorithm.  Then $A$'s \emph{advantage in solving the
235   decision Diffie-Hellman problem in $G$} is
236   \begin{equation}
237     \begin{eqnalign}[rl]
238       \Adv{ddh}{G}(A) =
239       & \Pr[\alpha \getsr \Nupto{q}; \beta \getsr \Nupto{q} :
240             A(g^\alpha, g^\beta, g^{\alpha\beta}) = 1] - {} \\
241       & \Pr[\alpha \getsr \Nupto{q}; \beta \getsr \Nupto{q};
242             \gamma \getsr \Nupto{q} :
243             A(g^\alpha, g^\beta, g^\gamma) = 1].
244     \end{eqnalign}
245   \end{equation}
246   The \emph{insecurity function of the decision Diffie-Hellman problem in
247   $G$} is
248   \begin{equation}
249     \InSec{ddh}(G; t) = \max_A \Adv{ddh}{G}(A)
250   \end{equation}
251   where the maximum is taken over all algorithms $A$ which run in time $t$.
252 \end{definition}
253
254 %%%--------------------------------------------------------------------------
255
256 \section{The protocol}
257 \label{sec:protocol}
258
259 The Wrestlers Protocol is parameterized.  We need the following things:
260 \begin{itemize}
261 \item A cyclic group $G$ whose order~$q$ is prime.  Let $g$ be a generator
262   of~$G$.  We require that the (decision?\fixme) Diffie-Hellman problem be
263   hard in~$G$.  The group operation is written multiplicatively.
264 \item A symmetric encryption scheme $\mathcal{E} = (E, D)$.  We require that
265   $\mathcal{E}$ be secure against adaptive chosen-plaintext attacks.  Our
266   implementation uses Blowfish \cite{Schneier:1994:BEA} in CBC mode with
267   ciphertext stealing.  See section~\ref{sec:cbc} for a description of
268   ciphertext stealing and an analysis of its security.
269 \item A message authentication scheme $\mathcal{M} = (T, V)$.  We require
270   that $\mathcal{M}$ be (strongly) existentially unforgeable under
271   chosen-message attacks.  Our implementation uses RIPEMD-160
272   \cite{Dobbertin:1996:RSV} in the HMAC \cite{Bellare:1996:HC} construction.
273 \item An instantiation for the random oracle.  We use RIPEMD-160 again,
274   either on its own, if the output is long enough, or in the MGF-1
275   \cite{RFC2437} construction, if we need a larger output.\footnote{%
276     The use of the same hash function in the MAC as for instantiating the
277     random oracle is deliberate, with the aim of reducing the number of
278     primitives whose security we must assume.  In an application of HMAC, the
279     message to be hashed is prefixed by a secret key padded out to the hash
280     function's block size.  In a `random oracle' query, the message is
281     prefixed by a fixed identification string and not padded.  Interference
282     between the two is then limited to the case where one of the HMAC keys
283     matches a random oracle prefix, which happens only with very tiny
284     probability.}%
285 \end{itemize}
286
287 An authenticated encryption scheme with associated data (AEAD)
288 \cite{Rogaway:2002:AEAD, Rogaway:2001:OCB, Kohno:2003:CWC} could be used
289 instead of a separate symmetric encryption scheme and MAC.
290
291 \subsection{Symmetric encryption}
292
293 The same symmetric encryption subprotocol is used both within the key
294 exchange, to ensure secrecy and binding, and afterwards for message
295 transfer.  It provides a secure channel between two players, assuming that
296 the key was chosen properly.
297
298 A \id{keyset} contains the state required for communication between the two
299 players.  In particular it maintains:
300 \begin{itemize}
301 \item separate encryption and MAC keys in each direction (four keys in
302   total), chosen using the random oracle based on an input key assumed to be
303   unpredictable by the adversary and a pair of nonces chosen by the two
304   players; and
305 \item incoming and outgoing sequence numbers, to detect and prevent replay
306   attacks.
307 \end{itemize}
308
309 The operations involved in the symmetric encryption protocol are shown in
310 figure~\ref{fig:keyset}.
311
312 The \id{keygen} procedure initializes a \id{keyset}, resetting the sequence
313 numbers, and selecting keys for the encryption scheme and MAC using the
314 random oracle.  It uses the nonces $r_A$ and $r_B$ to ensure that with high
315 probability the keys are different for the two directions: assuming that
316 Alice chose her nonce $r_A$ at random, and that the keys and nonce are
317 $\kappa$~bits long, the probability that the keys in the two directions are
318 the same is at most $2^{\kappa - 2}$.
319
320 The \id{encrypt} procedure constructs a ciphertext from a message $m$ and a
321 \emph{message type} $\id{ty}$.  It encrypts the message giving a ciphertext
322 $y$, and computes a MAC tag $\tau$ for the triple $(\id{ty}, i, y)$, where
323 $i$ is the next available outgoing sequence number.  The ciphertext message
324 to send is then $(i, y, \tau)$.  The message type codes are used to
325 separate ciphertexts used by the key-exchange protocol itself from those sent
326 by the players later.
327
328 The \id{decrypt} procedure recovers the plaintext from a ciphertext triple
329 $(i, y, \tau)$, given its expected type code $\id{ty}$.  It verifies that the
330 tag $\tau$ is valid for the message $(\id{ty}, i, y)$, checks that the
331 sequence number $i$ hasn't been seen before,\footnote{%
332   The sequence number checking shown in the figure is simple but obviously
333   secure.  The actual implementation maintains a window of 32 previous
334   sequence numbers, to allow out-of-order reception of messages while still
335   preventing replay attacks.  This doesn't affect our analysis.}%
336 and then decrypts the ciphertext $y$.
337
338 \begin{figure}
339   \begin{program}
340     Structure $\id{keyset}$: \+ \\
341       $\Xid{K}{enc-in}$; $\Xid{K}{enc-out}$; \\
342       $\Xid{K}{mac-in}$; $\Xid{K}{mac-out}$; \\
343       $\id{seq-in}$; $\id{seq-out}$; \- \\[\medskipamount]
344     Function $\id{gen-keys}(r_A, r_B, K)$: \+ \\
345       $k \gets \NEW \id{keyset}$; \\
346       $k.\Xid{K}{enc-in} \gets H(\cookie{encryption}, r_A, r_B, K)$; \\
347       $k.\Xid{K}{enc-out} \gets H(\cookie{encryption}, r_B, r_A, K)$; \\
348       $k.\Xid{K}{mac-in} \gets H(\cookie{integrity}, r_A, r_B, K)$; \\
349       $k.\Xid{K}{mac-out} \gets H(\cookie{integrity}, r_B, r_A, K)$; \\
350       $k.\id{seq-in} \gets 0$; \\
351       $k.\id{seq-out} \gets 0$; \\
352       \RETURN $k$;
353     \next
354     Function $\id{encrypt}(k, \id{ty}, m)$: \+ \\
355       $y \gets (E_{k.\Xid{K}{enc-out}}(m))$; \\
356       $i \gets k.\id{seq-out}$; \\
357       $\tau \gets T_{k.\Xid{K}{mac-out}}(\id{ty}, i, y)$; \\
358       $k.\id{seq-out} \gets i + 1$; \\
359       \RETURN $(i, y, \tau)$; \- \\[\medskipamount]
360     Function $\id{decrypt}(k, \id{ty}, c)$: \+ \\
361       $(i, y, \tau) \gets c$; \\
362       \IF $V_{k.\Xid{K}{mac-in}}((\id{ty}, i, y), \tau) = 0$ \THEN \\ \ind
363         \RETURN $\bot$; \- \\
364       \IF $i < k.\id{seq-in}$ \THEN \RETURN $\bot$; \\
365       $m \gets D_{k.\Xid{K}{enc-in}}(y)$; \\
366       $k.\id{seq-in} \gets i + 1$; \\
367       \RETURN $m$;
368   \end{program}
369
370   \caption{Symmetric-key encryption functions}
371   \label{fig:keyset}
372 \end{figure}
373
374 \subsection{The key-exchange}
375
376 The key-exchange protocol is completely symmetrical.  Either party may
377 initiate, or both may attempt to converse at the same time.  We shall
378 describe the protocol from the point of view of Alice attempting to exchange
379 a key with Bob.
380
381 Alice's private key is a random index $\alpha \inr \Nupto{q}$.  Her public
382 key is $a = g^\alpha$.  Bob's public key is $b \in G$.  We'll subscript the
383 variables Alice computes with an~$A$, and the values Bob has sent with a~$B$.
384 Of course, if Bob is following the protocol correctly, he will have computed
385 his $B$ values in a completely symmetrical way.
386
387 There are six messages in the protocol, and we shall briefly discuss the
388 purpose of each before embarking on the detailed descriptions.  At the
389 beginning of the protocol, Alice chooses a new random index $\rho_A$ and
390 computes her \emph{challenge} $r_A = g^{\rho_A}$.  Eventually, the shared
391 secret key will be computed as $K = r_B^{\rho_A} = r_A^{\rho_B} =
392 g^{\rho_A\rho_B}$, as for standard Diffie-Hellman key agreement.
393
394 Throughout, we shall assume that messages are implicitly labelled with the
395 sender's identity.  If Alice is actually trying to talk to several other
396 people she'll need to run multiple instances of the protocol, each with its
397 own state, and she can use the sender label to decide which instance a
398 message should be processed by.  There's no need for the implicit labels to
399 be attached securely.
400
401 We'll summarize the messages and their part in the scheme of things before we
402 start on the serious detail.  For a summary of the names and symbols used in
403 these descriptions, see table~\ref{tab:kx-names}.  The actual message
404 contents are summarized in table~\ref{tab:kx-messages}.  A state-transition
405 diagram of the protocol is shown in figure~\ref{fig:kx-states}.  If reading
406 pesudocode algorithms is your thing then you'll find message-processing
407 procedures in figure~\ref{fig:kx-messages} with the necessary support procedures
408 in figure~\ref{fig:kx-support}.
409
410 \begin{table}
411   \begin{tabularx}{\textwidth}{Mr X}
412     G                     & A cyclic group known by all participants \\
413     q = |G|               & The prime order of $G$ \\
414     g                     & A generator of $G$ \\
415     E_K(\cdot)            & Encryption under key $K$, here used to denote
416                             application of the $\id{encrypt}(K, \cdot)$
417                             operation \\
418     \alpha \inr \Nupto{q} & Alice's private key \\
419     a = g^{\alpha}        & Alice's public key \\
420     \rho_A \inr \Nupto{q} & Alice's secret Diffie-Hellman value \\
421     r_A = g^{\rho_A}      & Alice's public \emph{challenge} \\
422     c_A = H(\cookie{cookie}, r_A)
423                           & Alice's \emph{cookie} \\
424     v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A})
425                           & Alice's challenge \emph{check value} \\
426     r_B^\alpha = a^{\rho_B}
427                           & Alice's reply \\
428     K = r_B^{\rho_A} = r_B^{\rho_A} = g^{\rho_A\rho_B}
429                           & Alice and Bob's shared secret key \\
430     w_A = H(\cookie{switch-request}, c_A, c_B)
431                           & Alice's \emph{switch request} value \\
432     u_A = H(\cookie{switch-confirm}, c_A, c_B)
433                           & Alice's \emph{switch confirm} value \\
434   \end{tabularx}
435
436   \caption{Names used during key-exchange}
437   \label{tab:kx-names}
438 \end{table}
439
440 \begin{table}
441   \begin{tabular}[C]{Ml}
442     \cookie{kx-pre-challenge}, r_A \\
443     \cookie{kx-cookie}, r_A, c_B \\
444     \cookie{kx-challenge}, r_A, c_B, v_A \\
445     \cookie{kx-reply}, c_A, c_B, v_A, E_K(r_B^\alpha)) \\
446     \cookie{kx-switch}, c_A, c_B, E_K(r_B^\alpha, w_A)) \\
447     \cookie{kx-switch-ok}, E_K(u_A))
448   \end{tabular}
449
450   \caption{Message contents, as sent by Alice}
451   \label{tab:kx-messages}
452 \end{table}
453
454 \begin{messages}
455 \item[kx-pre-challenge] Contains a plain statement of Alice's challenge.
456   This is Alice's first message of a session.
457 \item[kx-cookie] A bare acknowledgement of a received challenge: it restates
458   Alice's challenge, and contains a hash of Bob's challenge.  This is an
459   engineering measure (rather than a cryptographic one) which prevents
460   trivial denial-of-service attacks from working.
461 \item[kx-challenge] A full challenge, with a `check value' which proves the
462   challenge's honesty.  Bob's correct reply to this challenge informs Alice
463   that she's received his challenge correctly.
464 \item[kx-reply] A reply.  This contains a `check value', like the
465   \cookie{kx-challenge} message above, and an encrypted reply which confirms
466   to Bob Alice's successful receipt of his challenge and lets Bob know he
467   received Alice's challenge correctly.
468 \item[kx-switch] Acknowledges Alice's receipt of Bob's \cookie{kx-reply}
469   message, including Alice's own reply to Bob's challenge.  Tells Bob that
470   she can start using the key they've agreed.
471 \item[kx-switch-ok] Acknowlegement to Bob's \cookie{kx-switch} message.
472 \end{messages}
473
474 \begin{figure}
475   \small
476   \let\ns\normalsize
477   \let\c\cookie
478   \[ \begin{graph}
479      []!{0; <4.5cm, 0cm>: <0cm, 1.5cm>::}
480      *++[F:<4pt>]\txt{\ns Start \\ Choose $\rho_A$} ="start"
481      :[dd]
482      *++[F:<4pt>]\txt{
483        \ns State \c{challenge} \\
484        Send $(\c{pre-challenge}, r_A)$}
485      ="chal"
486      [] "chal" !{!L(0.5)} ="chal-cookie"
487      :@(d, d)[l]
488      *+\txt{Send $(\c{cookie}, r_A, c_B)$}
489      ="cookie"
490      |*+\txt{Receive \\ $(\c{pre-challenge}, r_B)$ \\ (no spare slot)}
491      :@(u, u)"chal-cookie"
492      "chal" :@/_0.8cm/ [ddddl]
493      *+\txt{Send \\ $(\c{challenge}, $\\$ r_A, c_B, v_A)$}
494      ="send-chal"
495      |<>(0.67) *+\txt\small{
496        Receive \\ $(\c{pre-challenge}, r_B)$ \\ (spare slot)}
497      "chal" :@/^0.8cm/ "send-chal" |<>(0.33)
498      *+\txt{Receive \\ $(\c{cookie}, r_B, c_A)$}
499      :[rr]
500      *+\txt{Send \\ $(\c{reply}, c_A, c_B, $\\$ v_A, E_K(r_B^\alpha))$}
501      ="send-reply"
502      |*+\txt{Receive \\ $(\c{challenge}, $\\$ r_B, c_A, v_B)$}
503      "chal" :"send-reply"
504      |*+\txt{Receive \\ $(\c{challenge}, $\\$ r_B, c_A, v_B)$}
505      "send-chal" :[ddd]
506      *++[F:<4pt>]\txt{
507        \ns State \c{commit} \\
508        Send \\ $(\c{switch}, c_A, c_B, $\\$ E_K(r_B^\alpha, w_A))$}
509      ="commit"
510      |*+\txt{Receive \\ $(\c{reply}, c_B, c_A, $\\$ v_B, E_K(b^{\rho_A}))$}
511      :[rr]
512      *+\txt{Send \\ $(\c{switch-ok}, E_K(u_A))$}
513      ="send-switch-ok"
514      |*+\txt{Receive \\ $(\c{switch}, c_B, c_A, $\\$ E_K(b^{\rho_A}, w_B))$}
515      "send-reply" :"commit"
516      |*+\txt{Receive \\ $(\c{reply}, c_B, c_A, $\\$ v_B, E_K(b^{\rho_A}))$}
517      "send-reply" :"send-switch-ok"
518      |*+\txt{Receive \\ $(\c{switch}, c_B, c_A, $\\$ E_K(b^{\rho_A}, w_B))$}
519      :[dddl]
520      *++[F:<4pt>]\txt{\ns Done}
521      ="done"
522      "commit" :"done"
523      |*+\txt{Receive \\ $(\c{switch-ok}, E_K(u_B))$}
524      "send-chal" [r] !{+<0cm, 0.75cm>}
525      *\txt\itshape{For each outstanding challenge}
526      ="for-each"
527      !{"send-chal"+DL-<8pt, 8pt> ="p0",
528        "for-each"+U+<8pt> ="p1",
529        "send-reply"+UR+<8pt, 8pt> ="p2",
530        "send-reply"+DR+<8pt, 8pt> ="p3",
531        "p0" !{"p1"-"p0"} !{"p2"-"p1"} !{"p3"-"p2"}
532       *\frm<8pt>{--}}
533   \end{graph} \]
534
535   \caption{State-transition diagram for key-exchange protocol}
536   \label{fig:kx-states}
537 \end{figure}
538
539 We now describe the protocol message by message, and Alice's actions when she
540 receives each.  Since the protocol is completely symmetrical, Bob should do
541 the same, only swapping round $A$ and $B$ subscripts, the public keys $a$ and
542 $b$, and using his private key $\beta$ instead of $\alpha$.
543
544 \subsubsection{Starting the protocol}
545
546 As described above, at the beginning of the protocol Alice chooses a random
547 $\rho_A \inr \Nupto q$, and computes her \emph{challenge} $r_A = g^{\rho_A}$
548 and her \emph{cookie} $c_A = H(\cookie{cookie}, r_A)$.  She sends her
549 announcement of her challenge as
550 \begin{equation}
551   \label{eq:kx-pre-challenge}
552   \cookie{kx-pre-challenge}, r_A
553 \end{equation}
554 and enters the \cookie{challenge} state.
555
556 \subsubsection{The \cookie{kx-pre-challenge} message}
557
558 If Alice receieves a \cookie{kx-pre-challenge}, she ensures that she's in the
559 \cookie{challenge} state: if not, she rejects the message.
560
561 She must first calculate Bob's cookie $c_B = H(\cookie{cookie}, r_B)$.  Then
562 she has a choice: either she can send a full challenge, or she can send the
563 cookie back.
564
565 Suppose she decides to send a full challenge.  She must compute a \emph{check
566 value}
567 \begin{equation}
568   \label{eq:v_A}
569   v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A})
570 \end{equation}
571 and sends
572 \begin{equation}
573   \label{eq:kx-challenge}
574   \cookie{kx-challenge}, r_A, c_B, v_A
575 \end{equation}
576 to Bob.  Then she remembers Bob's challenge for later use, and awaits his
577 reply.
578
579 If she decides to send only a cookie, she just transmits
580 \begin{equation}
581   \label{eq:kx-cookie}
582   \cookie{kx-cookie}, r_A, c_B
583 \end{equation}
584 to Bob and forgets all about it.
585
586 Why's this useful?  Well, if Alice sends off a full \cookie{kx-challenge}
587 message, she must remember Bob's $r_B$ so she can check his reply and that
588 involves using up a table slot.  That means that someone can send Alice
589 messages purporting to come from Bob which will chew up Alice's memory, and
590 they don't even need to be able to read Alice's messages to Bob to do that.
591 If this protocol were used over the open Internet, script kiddies from all
592 over the world might be flooding Alice with bogus \cookie{kx-pre-challenge}
593 messages and she'd never get around to talking to Bob.
594
595 By sending a cookie intead, she avoids committing a table slot until Bob (or
596 someone) sends either a cookie or a full challenge, thus proving, at least,
597 that he can read her messages.  This is the best we can do at this stage in
598 the protocol.  Against an adversary as powerful as the one we present in
599 section~\fixme\ref{sec:formal} this measure provides no benefit (but we have
600 to analyse it anyway); but it raises the bar too sufficiently high to
601 eliminate a large class of `nuisance' attacks in the real world.
602
603 Our definition of the Wrestlers Protocol doesn't stipulate when Alice should
604 send a full challenge or just a cookie: we leave this up to individual
605 implementations, because it makes no difference to the security of the
606 protocol against powerful adversaries.  But we recommend that Alice proceed
607 `optimistically' at first, sending full challenges until her challenge table
608 looks like it's running out, and then generating cookies only if it actually
609 looks like she's under attack.  This is what our pseudocode in
610 figure~\ref{fig:kx-messages} does.
611
612 \subsubsection{The \cookie{kx-cookie} message}
613
614 When Alice receives a \cookie{kx-cookie} message, she must ensure that she's
615 in the \cookie{challenge} state: if not, she rejects the message.  She checks
616 the cookie in the message against the value of $c_A$ she computed earlier.
617 If all is well, Alice sends a \cookie{kx-challenge} message, as in
618 equation~\ref{eq:kx-challenge} above.
619
620 This time, she doesn't have a choice about using up a table slot to remember
621 Bob's $r_B$.  If her table size is fixed, she must choose a slot to recycle.
622 We suggest simply recycling slots at random: this means there's no clever
623 pattern of \cookie{kx-cookie} messages an attacker might be able to send to
624 clog up all of Alice's slots.
625
626 \subsubsection{The \cookie{kx-challenge} message}
627
628
629
630 \begin{figure}
631   \begin{program}
632     Procedure $\id{kx-initialize}$: \+ \\
633       $\rho_A \getsr [q]$; \\
634       $r_a \gets g^{\rho_A}$; \\
635       $\id{state} \gets \cookie{challenge}$; \\
636       $\Xid{n}{chal} \gets 0$; \\
637       $k \gets \bot$; \\
638       $\id{chal-commit} \gets \bot$; \\
639       $\id{send}(\cookie{kx-pre-challenge}, r_A)$; \- \\[\medskipamount]
640     Procedure $\id{kx-receive}(\id{type}, \id{data})$: \\ \ind
641       \IF $\id{type} = \cookie{kx-pre-challenge}$ \THEN \\ \ind
642         \id{msg-pre-challenge}(\id{data}); \- \\
643       \ELSE \IF $\id{type} = \cookie{kx-cookie}$ \THEN \\ \ind
644         \id{msg-cookie}(\id{data}); \- \\
645       \ELSE \IF $\id{type} = \cookie{kx-challenge}$ \THEN \\ \ind
646         \id{msg-challenge}(\id{data}); \- \\
647       \ELSE \IF $\id{type} = \cookie{kx-reply}$ \THEN \\ \ind
648         \id{msg-reply}(\id{data}); \- \\
649       \ELSE \IF $\id{type} = \cookie{kx-switch}$ \THEN \\ \ind
650         \id{msg-switch}(\id{data}); \- \\
651       \ELSE \IF $\id{type} = \cookie{kx-switch-ok}$ \THEN \\ \ind
652         \id{msg-switch-ok}(\id{data}); \-\- \\[\medskipamount]
653     Procedure $\id{msg-pre-challenge}(\id{data})$: \+ \\
654       \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\
655       $r \gets \id{data}$; \\
656       \IF $\Xid{n}{chal} \ge \Xid{n}{chal-thresh}$ \THEN \\ \ind
657         $\id{send}(\cookie{kx-cookie}, r_A, \id{cookie}(r_A)))$; \- \\
658       \ELSE \+ \\
659         $\id{new-chal}(r)$; \\
660         $\id{send}(\cookie{kx-challenge}, r_A,
661                    \id{cookie}(r), \id{checkval}(r))$; \-\-\\[\medskipamount]
662     Procedure $\id{msg-cookie}(\id{data})$: \+ \\
663       \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\
664       $(r, c_A) \gets \id{data}$; \\
665       \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\
666       $\id{new-chal}(r)$; \\
667       $\id{send}(\cookie{kx-challenge}, r_A,
668                  \id{cookie}(r), \id{checkval}(r))$; \- \\[\medskipamount]
669     Procedure $\id{msg-challenge}(\id{data})$: \+ \\
670       \IF $\id{state} \ne \cookie{challenge}$ \THEN \RETURN; \\
671       $(r, c_A, v) \gets \id{data}$; \\
672       \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\
673       $i \gets \id{check-reply}(\bot, r, v)$; \\
674       \IF $i = \bot$ \THEN \RETURN; \\
675       $k \gets \id{chal-tab}[i].k$; \\
676       $y \gets \id{encrypt}(k, \cookie{kx-reply}, r^\alpha)$; \\
677       $\id{send}(\cookie{kx-reply}, c_A, \id{cookie}(r),
678                  \id{checkval}(r), y)$
679     \next
680     Procedure $\id{msg-reply}(\id{data})$: \+ \\
681       $(c, c_A, v, y) \gets \id{data}$; \\
682       \IF $c_A \ne \id{cookie}(r_A)$ \THEN \RETURN; \\
683       $i \gets \id{find-chal}(c)$; \\
684       \IF $i = \bot$ \THEN \RETURN; \\
685       \IF $\id{check-reply}(i, \id{chal-tab}[i].r, v) = \bot$ \THEN \\ \ind
686         \RETURN; \- \\
687       $k \gets \id{chal-tab}[i].k$; \\
688       $x \gets \id{decrypt}(k, \cookie{kx-reply}, y)$; \\
689       \IF $x = \bot$ \THEN \RETURN; \\
690       \IF $x \ne b^{\rho_A}$ \THEN \RETURN; \\
691       $\id{state} \gets \cookie{commit}$; \\
692       $\id{chal-commit} \gets \id{chal-tab}[i]$; \\
693       $w \gets H(\cookie{switch-request}, c_A, c)$; \\
694       $x \gets \id{chal-tab}[i].r^\alpha$; \\
695       $y \gets \id{encrypt}(k, (x, \cookie{kx-switch}, w))$; \\
696       $\id{send}(\cookie{kx-switch}, c_A, c, y)$; \-\\[\medskipamount]
697     Procedure $\id{msg-switch}(\id{data})$: \+ \\
698       $(c, c_A, y) \gets \id{data}$; \\
699       \IF $c_A \ne \cookie(r_A)$ \THEN \RETURN; \\
700       $i \gets \id{find-chal}(c)$; \\
701       \IF $i = \bot$ \THEN \RETURN; \\
702       $k \gets \id{chal-tab}[i].k$; \\
703       $x \gets \id{decrypt}(k, \cookie{kx-switch}, y)$; \\
704       \IF $x = \bot$ \THEN \RETURN; \\
705       $(x, w) \gets x$; \\
706       \IF $\id{state} = \cookie{challenge}$ \THEN \\ \ind
707         \IF $x \ne b^{\rho_A}$ \THEN \RETURN; \\
708         $\id{chal-commit} \gets \id{chal-tab}[i]$; \- \\
709       \ELSE \IF $c \ne \id{chal-commit}.c$ \THEN \RETURN; \\
710       \IF $w \ne H(\cookie{switch-request}, c, c_A)$ \THEN \RETURN; \\
711       $w \gets H(\cookie{switch-confirm}, c_A, c)$; \\
712       $y \gets \id{encrypt}(y, \cookie{kx-switch-ok}, w)$; \\
713       $\id{send}(\cookie{switch-ok}, y)$; \\
714       $\id{done}(k)$; \- \\[\medskipamount]
715     Procedure $\id{msg-switch-ok}(\id{data})$ \+ \\
716       \IF $\id{state} \ne \cookie{commit}$ \THEN \RETURN; \\
717       $y \gets \id{data}$; \\
718       $k \gets \id{chal-commit}.k$; \\
719       $w \gets \id{decrypt}(k, \cookie{kx-switch-ok}, y)$; \\
720       \IF $w = \bot$ \THEN \RETURN; \\
721       $c \gets \id{chal-commit}.c$; \\
722       $c_A \gets \id{cookie}(r_A)$; \\
723       \IF $w \ne H(\cookie{switch-confirm}, c, c_A)$ \THEN \RETURN; \\
724       $\id{done}(k)$;
725   \end{program}
726
727   \caption{The key-exchange protocol: message handling}
728   \label{fig:kx-messages}
729 \end{figure}
730
731 \begin{figure}
732   \begin{program}
733     Structure $\id{chal-slot}$: \+ \\
734       $r$; $c$; $\id{replied}$; $k$; \- \\[\medskipamount]
735     Function $\id{find-chal}(c)$: \+ \\
736       \FOR $i = 0$ \TO $\Xid{n}{chal}$ \DO \\ \ind
737         \IF $\id{chal-tab}[i].c = c$ \THEN \RETURN $i$; \- \\
738       \RETURN $\bot$; \- \\[\medskipamount]
739     Function $\id{cookie}(r)$: \+ \\
740       \RETURN $H(\cookie{cookie}, r)$; \- \\[\medskipamount]
741     Function $\id{check-reply}(i, r, v)$: \+ \\
742       \IF $i \ne \bot \land \id{chal-tab}[i].\id{replied} = 1$ \THEN \\ \ind
743         \RETURN $i$; \- \\
744       $\rho \gets v \xor H(\cookie{expected-reply}, r, r_A, r^\alpha)$; \\
745       \IF $g^\rho \ne r$ \THEN \RETURN $\bot$; \\
746       \IF $i = \bot$ \THEN $i \gets \id{new-chal}(r)$; \\
747       $\id{chal-tab}[i].k \gets \id{gen-keys}(r_A, r, r^{\rho_A})$; \\
748       $\id{chal-tab}[i].\id{replied} \gets 1$; \\
749       \RETURN $i$;
750     \next
751     Function $\id{checkval}(r)$: \\ \ind
752       \RETURN $\rho_A \xor H(\cookie{expected-reply},
753                              r_A,r, b^{\rho_A})$; \- \\[\medskipamount]
754     Function $\id{new-chal}(r)$: \+ \\
755       $c \gets \id{cookie}(r)$; \\
756       $i \gets \id{find-chal}(c)$; \\
757       \IF $i \ne \bot$ \THEN \RETURN $i$; \\
758       \IF $\Xid{n}{chal} < \Xid{n}{chal-max}$ \THEN \\ \ind
759         $i \gets \Xid{n}{chal}$; \\
760         $\id{chal-tab}[i] \gets \NEW \id{chal-slot}$; \\
761         $\Xid{n}{chal} \gets \Xid{n}{chal} + 1$; \- \\
762       \ELSE \\ \ind
763         $i \getsr [\Xid{n}{chal-max}]$; \- \\
764       $\id{chal-tab}[i].r \gets r$; \\
765       $\id{chal-tab}[i].c \gets c$; \\
766       $\id{chal-tab}[i].\id{replied} \gets 0$; \\
767       $\id{chal-tab}[i].k \gets \bot$; \\
768       \RETURN $i$;
769   \end{program}
770
771   \caption{The key-exchange protocol: support functions}
772   \label{fig:kx-support}
773 \end{figure}
774
775 %%%--------------------------------------------------------------------------
776
777 \section{CBC mode encryption}
778 \label{sec:cbc}
779
780 Our implementation of the Wrestlers Protocol uses Blowfish
781 \cite{Schneier:1994:BEA} in CBC mode.  However, rather than pad plaintext
782 messages to a block boundary, with the ciphertext expansion that entails, we
783 use a technique called \emph{ciphertext stealing}
784 \cite[section 9.3]{Schneier:1996:ACP}.
785
786 \subsection{Standard CBC mode}
787
788 Suppose $E$ is an $\ell$-bit pseudorandom permutation.  Normal CBC mode works
789 as follows.  Given a message $X$, we divide it into blocks $x_0, x_1, \ldots,
790 x_{n-1}$.  Choose a random \emph{initialization vector} $I \inr \Bin^\ell$.
791 Before passing each $x_i$ through $E$, we XOR it with the previous
792 ciphertext, with $I$ standing in for the first block:
793 \begin{equation}
794   y_0 = E_K(x_0 \xor I) \qquad
795   y_i = E_K(x_i \xor y_{i-1} \ \text{(for $1 \le i < n$)}.
796 \end{equation}
797 The ciphertext is then the concatenation of $I$ and the $y_i$.  Decryption is
798 simple:
799 \begin{equation}
800   x_0 = E^{-1}_K(y_0) \xor I \qquad
801   x_i = E^{-1}_K(y_i) \xor y_{i-1} \ \text{(for $1 \le i < n$)}
802 \end{equation}
803 See figure~\ref{fig:cbc} for a diagram of CBC encryption.
804
805 \begin{figure}
806   \[ \begin{graph}
807     []!{0; <0.85cm, 0cm>: <0cm, 0.5cm>::}
808     *+=(1, 0)+[F]{\mathstrut x_0}="x"
809       :[dd] *{\xor}="xor"
810       [ll] *+=(1, 0)+[F]{I} :"xor"
811       :[dd] *+[F]{E}="e" :[ddd] *+=(1, 0)+[F]{\mathstrut y_0}="i"
812       "e" [l] {K} :"e"
813     [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_1}="x"
814       :[dd] *{\xor}="xor"
815       "e" [d] :`r [ru] `u "xor" "xor"
816       :[dd] *+[F]{E}="e" :[ddd]
817       *+=(1, 0)+[F]{\mathstrut y_1}="i"
818       "e" [l] {K} :"e"
819     [rrruuuu] *+=(1, 0)+[F--]{\mathstrut x_i}="x"
820       :@{-->}[dd] *{\xor}="xor"
821       "e" [d] :@{-->}`r [ru] `u "xor" "xor"
822       :@{-->}[dd] *+[F]{E}="e" :@{-->}[ddd]
823       *+=(1, 0)+[F--]{\mathstrut y_i}="i"
824       "e" [l] {K} :@{-->}"e"
825     [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_{n-1}}="x"
826       :[dd] *{\xor}="xor"
827       "e" [d] :@{-->}`r [ru] `u "xor" "xor"
828       :[dd] *+[F]{E}="e" :[ddd]
829       *+=(1, 0)+[F]{\mathstrut y_{n-1}}="i"
830       "e" [l] {K} :"e"
831   \end{graph} \]
832
833   \caption{Encryption using CBC mode}
834   \label{fig:cbc}
835 \end{figure}
836
837 \begin{definition}[CBC mode]
838   \label{def:cbc}
839   Let $P\colon \keys P \times \Bin^\ell to \Bin^\ell$ be a pseudorandom
840   permutation.  We define the symmetric encryption scheme
841   $\Xid{\mathcal{E}}{CBC}^P = (\Xid{E}{CBC}^P, \Xid{D}{CBC}^P)$ for messages
842   in $\Bin^{\ell\Z}$ by setting $\keys \Xid{\mathcal{E}}{CBC} = \keys P$ and
843   defining the encryption and decryption algorithms as follows:
844   \begin{program}
845     Algorithm $\Xid{E}{CBC}^P_K(x)$: \+ \\
846       $I \getsr \Bin^\ell$; \\
847       $y \gets I$; \\
848       \FOR $i = 0$ \TO $|x|/\ell$ \DO \\ \ind
849         $x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\
850         $y_i \gets P_K(x_i \xor I)$; \\
851         $I \gets y_i$; \\
852         $y \gets y \cat y_i$; \- \\
853       \RETURN $y$;
854     \next
855     Algorithm $\Xid{D}{CBC}^P_K(y)$: \+ \\
856       $I \gets y[0 \bitsto \ell]$; \\
857       $x \gets \emptystring$; \\
858       \FOR $1 = 0$ \TO $|y|/\ell$ \DO \\ \ind
859         $y_i \gets y[\ell i  \bitsto  \ell (i + 1)]$; \\
860         $x_i \gets P^{-1}_K(y_i) \xor I$; \\
861         $I \gets y_i$; \\
862         $x \gets x \cat x_i$; \- \\
863       \RETURN $x$;
864   \end{program}
865 \end{definition}
866
867 \begin{theorem}[Security of standard CBC mode]
868   \label{thm:cbc}
869   Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
870   permutation.  Then,
871   \begin{equation}
872     \InSec{lor-cpa}(\Xid{\mathcal{E}}{CBC}; t, q_E + \mu_E) \le
873       2 \cdot \InSec{prp}(P; t + q t_P, q) +
874       \frac{q (q - 1)}{2^\ell - 2^{\ell/2}}
875   \end{equation}
876   where $q = \mu_E/\ell$ and $t_P$ is some small constant.
877 \end{theorem}
878
879 \begin{note}
880   Our security bound is slightly better than that of \cite[theorem
881   17]{Bellare:2000:CST}.  Their theorem statement contains a term $3 \cdot q
882   (q - 1) 2^{-\ell-1}$.  Our result lowers the factor from 3 to just over 2.
883   Our proof is also much shorter and considerably more comprehensible.
884 \end{note}
885
886 The proof of this theorem is given in section~\ref{sec:cbc-proof}
887
888 \subsection{Ciphertext stealing}
889
890 Ciphertext stealing allows us to encrypt any message in $\Bin^*$ and make the
891 ciphertext exactly $\ell$ bits longer than the plaintext.  See
892 figure~\ref{fig:cbc-steal} for a diagram.
893
894 \begin{figure}
895   \[ \begin{graph}
896     []!{0; <0.85cm, 0cm>: <0cm, 0.5cm>::}
897     *+=(1, 0)+[F]{\mathstrut x_0}="x"
898       :[dd] *{\xor}="xor"
899       [ll] *+=(1, 0)+[F]{I} :"xor"
900       :[dd] *+[F]{E}="e" :[ddddd] *+=(1, 0)+[F]{\mathstrut y_0}="i"
901       "e" [l] {K} :"e"
902     [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_1}="x"
903       :[dd] *{\xor}="xor"
904       "e" [d] :`r [ru] `u "xor" "xor"
905       :[dd] *+[F]{E}="e" :[ddddd]
906       *+=(1, 0)+[F]{\mathstrut y_1}="i"
907       "e" [l] {K} :"e"
908     [rrruuuu] *+=(1, 0)+[F--]{\mathstrut x_i}="x"
909       :@{-->}[dd] *{\xor}="xor"
910       "e" [d] :@{-->}`r [ru] `u "xor" "xor"
911       :@{-->}[dd] *+[F]{E}="e" :@{-->}[ddddd]
912       *+=(1, 0)+[F--]{\mathstrut y_i}="i"
913       "e" [l] {K} :@{-->}"e"
914     [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_{n-2}}="x"
915       :[dd] *{\xor}="xor"
916       "e" [d] :@{-->}`r [ru] `u "xor" "xor"
917       :[dd] *+[F]{E}="e"
918       "e" [l] {K} :"e"
919     [rrruuuu] *+=(1, 0)+[F]{\mathstrut x_{n-1} \cat 0^{\ell-t}}="x"
920       :[dd] *{\xor}="xor"
921       "e" [d] :`r [ru] `u "xor" "xor"
922       "e" [dddddrrr] *+=(1, 0)+[F]{\mathstrut y_{n-1}[0 \bitsto t]}="i"
923       "e" [dd] ="x"
924       "i" [uu] ="y"
925       []!{"x"; "e" **{}, "x"+/4pt/ ="p",
926           "x"; "y" **{}, "x"+/4pt/ ="q",
927           "y"; "x" **{}, "y"+/4pt/ ="r",
928           "y"; "i" **{}, "y"+/4pt/ ="s",
929           "e";
930           "p" **\dir{-};
931           "q" **\crv{"x"};
932           "r" **\dir{-};
933           "s" **\crv{"y"};
934           "i" **\dir{-}?>*\dir{>}}
935       "xor" :[dd] *+[F]{E}="e"
936       "e" [l] {K} :"e"
937       "e" [dddddlll] *+=(1, 0)+[F]{\mathstrut y_{n-2}}="i"
938       "e" [dd] ="x"
939       "i" [uu] ="y"
940       []!{"x"; "e" **{}, "x"+/4pt/ ="p",
941           "x"; "y" **{}, "x"+/4pt/ ="q",
942           "y"; "x" **{}, "y"+/4pt/ ="r",
943           "y"; "i" **{}, "y"+/4pt/ ="s",
944           "x"; "y" **{} ?="c" ?(0.5)/-4pt/ ="cx" ?(0.5)/4pt/ ="cy",
945           "e";
946           "p" **\dir{-};
947           "q" **\crv{"x"};
948           "cx" **\dir{-};
949           "c" *[@]\cir<4pt>{d^u};
950           "cy";
951           "r" **\dir{-};
952           "s" **\crv{"y"};
953           "i" **\dir{-}?>*\dir{>}}
954   \end{graph} \]
955
956   \caption{Encryption using CBC mode with ciphertext stealing}
957   \label{fig:cbc-steal}
958 \end{figure}
959
960 \begin{definition}[CBC stealing]
961   \label{def:cbc-steal}
962   Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
963   permutation.  We define the symmetric encryption scheme
964   $\Xid{\mathcal{E}}{CBC-steal}^P = (\Xid{G}{CBC}^P, \Xid{E}{CBC-steal}^P,
965   \Xid{D}{CBC-steal}^P)$ for messages in $\Bin^{\ell\Z}$ by setting $\keys
966   \Xid{\mathcal{E}}{CBC-steal} = \keys P$ and defining the encryption and
967   decryption algorithms as follows:
968   \begin{program}
969     Algorithm $\Xid{E}{CBC-steal}^P_K(x)$: \+ \\
970       $I \getsr \Bin^\ell$; \\
971       $y \gets I$; \\
972       $t = |x| \bmod \ell$; \\
973       \IF $t \ne 0$ \THEN $x \gets x \cat 0^{\ell-t}$; \\
974       \FOR $i = 0$ \TO $|x|/\ell$ \DO \\ \ind
975         $x_i \gets x[\ell i \bitsto \ell (i + 1)]$; \\
976         $y_i \gets P_K(x_i \xor I)$; \\
977         $I \gets y_i$; \\
978         $y \gets y \cat y_i$; \- \\
979       \IF $t \ne 0$ \THEN \\ \ind
980         $b \gets |y| - 2\ell$; \\
981         $y \gets $\=$y[0 \bitsto b] \cat
982                      y[b + \ell \bitsto |y|] \cat {}$ \\
983                   \>$y[b \bitsto b + t]$; \- \\
984       \RETURN $y$;
985     \next
986     Algorithm $\Xid{D}{CBC-steal}^P_K(y)$: \+ \\
987       $I \gets y[0 \bitsto \ell]$; \\
988       $t = |y| \bmod \ell$; \\
989       \IF $t \ne 0$ \THEN \\ \ind
990         $b \gets |y| - t - \ell$; \\
991         $z \gets P^{-1}_K(y[b \bitsto b + \ell])$; \\
992         $y \gets $\=$y[0 \bitsto b] \cat
993                      y[b + \ell \bitsto |y|] \cat {}$ \\
994                   \>$z[t \bitsto \ell]$; \- \\
995       $x \gets \emptystring$; \\
996       \FOR $1 = 0$ \TO $|y|/\ell$ \DO \\ \ind
997         $y_i \gets y[\ell i \bitsto \ell (i + 1)]$; \\
998         $x_i \gets P^{-1}_K(y_i) \xor I$; \\
999         $I \gets y_i$; \\
1000         $x \gets x \cat x_i$; \- \\
1001       \IF $t \ne 0$ \THEN \\ \ind
1002         $x \gets x \cat z[0 \bitsto t] \xor y[b \bitsto b + t]$; \- \\
1003       \RETURN $x$;
1004   \end{program}
1005 \end{definition}
1006
1007 \begin{theorem}[Security of CBC with ciphertext stealing]
1008   \label{thm:cbc-steal}
1009   Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
1010   permutation.  Then
1011   \begin{equation}
1012     \InSec{lor-cpa}(\Xid{\mathcal{E}}{CBC-steal}; t, q_E, \mu_E) \le
1013       2 \cdot \InSec{prp}(P; t + q t_P, q) +
1014       \frac{q (q - 1)}{2^\ell - 2^{\ell/2}}
1015   \end{equation}
1016   where $q = \mu_E/\ell$ and $t_P$ is some small constant.
1017 \end{theorem}
1018
1019 \begin{proof}
1020   This is an easy reducibility argument.  Let $A$ be an adversary attacking
1021   $\Xid{\mathcal{E}}{CBC-steal}^P$.  We construct an adversary which attacks
1022   $\Xid{\mathcal{E}}{CBC}^P$:
1023   \begin{program}
1024     Adversary $A'^{E(\cdot)}$: \+ \\
1025       $b \gets A^{\Xid{E}{steal}(\cdot)}$; \\
1026       \RETURN $b$;
1027     \- \\[\medskipamount]
1028     Oracle $\Xid{E}{steal}(x_0, x_1)$: \+ \\
1029       \IF $|x_0| \ne |x_1|$ \THEN \ABORT; \\
1030       \RETURN $\id{steal}(|x_0|, E(\id{pad}(x_0), \id{pad}(x_1)))$;
1031     \next
1032     Function $\id{pad}(x)$: \+ \\
1033       $t \gets |x| \bmod \ell$; \\
1034       \RETURN $x \cat 0^{\ell-t}$;
1035     \- \\[\medskipamount]
1036     Function $\id{steal}(l, y)$: \+ \\
1037       $t \gets l \bmod \ell$; \\
1038       \IF $t \ne 0$ \THEN \\ \ind
1039         $b \gets |y| - 2\ell$; \\
1040         $y \gets $\=$y[0 \bitsto b] \cat
1041                      y[b + \ell \bitsto |y|] \cat y[b \bitsto b + t]$; \- \\
1042       \RETURN $y$;
1043   \end{program}
1044   Comparing this to definition~\ref{def:cbc-steal} shows that $A'$ simlates
1045   the LOR-CPA game for $\Xid{\mathcal{E}}{CBC-steal}$ perfectly.  The theorem
1046   follows.
1047 \end{proof}
1048
1049 \subsection{Proof of theorem~\ref{thm:cbc}}
1050 \label{sec:cbc-proof}
1051
1052 Consider an adversary $A$ attacking CBC encryption using an ideal random
1053 permutation $P(\cdot)$.  Pick some point in the attack game when we're just
1054 about to encrypt the $n$th plaintext block.  For each $i \in \Nupto{n}$,
1055 let $x_i$ be the $i$th block of plaintext we've processed; let $y_i$ be the
1056 corresponding ciphertext; and let $z_i = P^{-1}(y_i)$, i.e., $z_i = x_i \xor
1057 I$ for the first block of a message, and $z_i = x_i \xor y_{i-1}$ for the
1058 subsequent blocks.
1059
1060 Say that `something went wrong' if any $z_i = z_j$ for $i \ne j$.  This is
1061 indeed a disaster, because it means that $y_i = y_j$ , so he can detect it,
1062 and $x_i \xor y_{i-1} = x_j \xor y_{j-1}$, so he can compute an XOR
1063 difference between two plaintext blocks from the ciphertext and thus
1064 (possibly) reveal whether he's getting his left or right plaintexts
1065 encrypted.  The alternative, `everything is fine', is much better.  If all
1066 the $z_i$ are distinct, then because $y_i = P(z_i)$, the $y_i$ are all
1067 generated by $P(\cdot)$ on inputs it's never seen before, so they're all
1068 random subject to the requirement that they be distinct.  If everything is
1069 fine, then, the adversary has no better way of deciding whether he has a left
1070 oracle or a right oracle than tossing a coin, and his advantage is therefore
1071 zero.  Thus, we must bound the probability that something went wrong.
1072
1073 Assume that, at our point in the game so far, everything is fine.  But we're
1074 just about to encrypt $x^* = x_n$.  There are two cases:
1075 \begin{itemize}
1076 \item If $x_n$ is the first block in a new message, we've just invented a new
1077   random IV $I \in \Bin^\ell$ which is unknown to $A$, and $z_n = x_n \xor
1078   I$.  Let $y^* = I$.
1079 \item If $x_n$ is \emph{not} the first block, then $z_n = x_n \xor y_{n-1}$,
1080   but the adversary doesn't yet know $y_{n-1}$, except that because $P$ is a
1081   permutation and all the $z_i$ are distinct, $y_{n-1} \ne y_i$ for any $0
1082   \le i < n - 1$.  Let $y^* = y_{n-1}$.
1083 \end{itemize}
1084 Either way, the adversary's choice of $x^*$ is independent of $y^*$.  Let
1085 $z^* = x^* \xor y^*$.  We want to know the probability that something goes
1086 wrong at this point, i.e., that $z^* = z_i$ for some $0 \le i < n$.  Let's
1087 call this event $C_n$.  Note first that, in the first case, there are
1088 $2^\ell$ possible values for $y^*$ and in the second there are $2^\ell - n +
1089 1$ possibilities for $y^*$.  Then
1090 \begin{eqnarray}[rl]
1091   \Pr[C_n]
1092   & = \sum_{x \in \Bin^\ell} \Pr[C_n \mid x^* = x] \Pr[x^* = x] \\
1093   & = \sum_{x \in \Bin^\ell}
1094           \Pr[x^* = x] \sum_{0\le i<n} \Pr[y^* = z_i \xor x] \\
1095   & \le \sum_{0\le i<n} \frac{1}{2^\ell - n}
1096         \sum_{x \in \Bin^\ell} \Pr[x^* = x] \\
1097   & = \frac{n}{2^\ell - n}
1098 \end{eqnarray}
1099
1100 Having bounded the probability that something went wrong for any particular
1101 block, we can proceed to bound the probability of something going wrong in
1102 the course of the entire game.  Let's suppose that $q = \mu_E/\ell \le
1103 2^{\ell/2}$; for if not, $q (q - 1) > 2^\ell$ and the theorem is trivially
1104 true, since no adversary can achieve advantage greater than one.
1105
1106 Let's give the name $W_i$ to the probability that something went wrong after
1107 encrypting $i$ blocks.  We therefore want to bound $W_q$ from above.
1108 Armed with the knowledge that $q \le 2^{\ell/2}$, we have
1109 \begin{eqnarray}[rl]
1110   W_q &\le \sum_{0\le i<q} \Pr[C_i]
1111        \le \sum_{0\le i<q} \frac{i}{2^\ell - i} \\
1112       &\le \frac{1}{2^\ell - 2^{\ell/2}} \sum_{0\le i<q} i \\
1113       &= \frac{q (q - 1)}{2 \cdot (2^\ell - 2^{\ell/2})}
1114 \end{eqnarray}
1115 Working through the definition of LOR-CPA security, we can see that $A$'s
1116 (and hence any adversary's) advantage against the ideal system is at most $2
1117 W_q$.
1118
1119 By using an adversary attacking CBC encryption as a statistical test in an
1120 attempt to distinguish $P_K(\cdot)$ from a pseudorandom permutation, we see
1121 that
1122 \begin{equation}
1123   \InSec{prp}(P; t + q t_P, q) \ge
1124     \frac{1}{2} \cdot
1125       \InSec{lor-cpa}(\Xid{\mathcal{E}}{CBC}; t, q_E, \mu_E) -
1126     \frac{q (q - 1)}{2 \cdot (2^\ell - 2^{\ell/2})}
1127 \end{equation}
1128 where $t_P$ expresses the overhead of doing the XORs and other care and
1129 feeding of the CBC adversary; whence
1130 \begin{equation}
1131   \InSec{lor-cpa}(\Xid{\mathcal{E}}{CBC}; t, q_E, \mu_E) \le
1132   2 \cdot \InSec{prp}(P; t, q) + \frac{q (q - 1)}{2^\ell - 2^{\ell/2}}
1133 \end{equation}
1134 as required.
1135 \qed
1136
1137 %%%----- That's all, folks --------------------------------------------------
1138
1139 \bibliography{mdw-crypto,cryptography,cryptography2000,rfc}
1140 \end{document}
1141
1142 %%% Local Variables:
1143 %%% mode: latex
1144 %%% TeX-master: "wrestlers"
1145 %%% End: