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