chiark / gitweb /
server/tests.at: Add a retry loop in `COMMS_EPING'.
[tripe] / doc / wrestlers.tex
CommitLineData
74eb47db 1%%% -*-latex-*-
2%%%
74eb47db 3%%% Description of the Wrestlers Protocol
4%%%
5%%% (c) 2001 Mark Wooding
6%%%
7
c128b544 8\newif\iffancystyle\fancystyletrue
d7d62ac0 9
10\iffancystyle
11 \documentclass
12 [a4paper, article, 10pt, numbering, noherefloats, notitlepage]
13 {strayman}
14 \usepackage[palatino, helvetica, courier, maths=cmr]{mdwfonts}
c128b544 15 \usepackage[mdwmargin]{mdwthm}
16 \PassOptionsToPackage{dvips}{xy}
d7d62ac0 17\else
c128b544 18 \documentclass{llncs}
d7d62ac0 19\fi
20
c128b544 21\usepackage{mdwtab, mathenv, mdwlist, mdwmath, crypto}
d7d62ac0 22\usepackage{amssymb, amstext}
c128b544 23\usepackage{tabularx}
24\usepackage{url}
25\usepackage[all]{xy}
74eb47db 26
90d03a85 27\errorcontextlines=999
d7d62ac0 28\showboxbreadth=999
29\showboxdepth=999
90d03a85 30\makeatletter
74eb47db 31
90d03a85 32\title{The Wrestlers Protocol: proof-of-receipt and secure key exchange}
33\author{Mark Wooding \and Clive Jones}
74eb47db 34
c128b544 35\bibliographystyle{mdwalpha}
1a981bdb 36
37\newcolumntype{G}{p{0pt}}
c128b544 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
1a981bdb 53
90d03a85 54\begin{document}
74eb47db 55
90d03a85 56\maketitle
57\begin{abstract}
c128b544 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.
90d03a85 73\end{abstract}
74\tableofcontents
75\newpage
74eb47db 76
90d03a85 77%%%--------------------------------------------------------------------------
74eb47db 78
90d03a85 79\section{Introduction}
c128b544 80\label{sec:intro}
90d03a85 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.
74eb47db 84
90d03a85 85%%%--------------------------------------------------------------------------
74eb47db 86
c128b544 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.
1a981bdb 91
c128b544 92\subsection{Bit strings}
93
94Most of our notation for bit strings is standard. The main thing to note is
95that 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
134Most of the notation used in the algorithm descriptions should be obvious.
135We 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}
144The notation is generally quite sloppy about types and scopes. In
145particular, there are implicit coercions between bit strings, integers and
146group elements. Any simple injective mapping will do for handling the
147conversions. We don't think these informalities cause much confusion, and
148they greatly simplify the presentation of the algorithms.
149
150\subsection{Random oracles}
151
152We shall analyse the Wrestlers Protocol in the random oracle model
153\cite{Bellare:1993:ROP}. That is, each participant including the adversary
154is 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
156input string $x$, the oracle can produce, on demand, any prefix of an
157infinitely long random answer $y = H(x)$. Repeating a query yields a prefix
158of the same random result string; asking a new query yields a prefix of a new
159randomly-chosen string.
160
161We shan't need either to query the oracle on very long input strings nor
162shall we need outputs much longer than a representation of a group index.
163Indeed, since all the programs we shall be dealing with run in finite time,
164and can therefore make only a finite number of oracle queries, each with a
165finitely long result, we can safely think about the random oracle as a finite
166object.
167
168Finally, we shall treat the oracle as a function of multiple inputs and
169expect it to operate on some unambiguous encoding of all of the arguments in
170order.
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$.
e04c2d50 187\end{definition}
c128b544 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
223Let $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$
226and $g^\beta$, it's hard to tell the difference between the correct
227Diffie-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} :
e04c2d50 240 A(g^\alpha, g^\beta, g^{\alpha\beta}) = 1] - {} \\
c128b544 241 & \Pr[\alpha \getsr \Nupto{q}; \beta \getsr \Nupto{q};
e04c2d50
MW
242 \gamma \getsr \Nupto{q} :
243 A(g^\alpha, g^\beta, g^\gamma) = 1].
c128b544 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
259The 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
287An authenticated encryption scheme with associated data (AEAD)
288\cite{Rogaway:2002:AEAD, Rogaway:2001:OCB, Kohno:2003:CWC} could be used
289instead of a separate symmetric encryption scheme and MAC.
290
291\subsection{Symmetric encryption}
292
293The same symmetric encryption subprotocol is used both within the key
294exchange, to ensure secrecy and binding, and afterwards for message
295transfer. It provides a secure channel between two players, assuming that
296the key was chosen properly.
297
298A \id{keyset} contains the state required for communication between the two
299players. 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
309The operations involved in the symmetric encryption protocol are shown in
310figure~\ref{fig:keyset}.
311
312The \id{keygen} procedure initializes a \id{keyset}, resetting the sequence
313numbers, and selecting keys for the encryption scheme and MAC using the
314random oracle. It uses the nonces $r_A$ and $r_B$ to ensure that with high
315probability the keys are different for the two directions: assuming that
316Alice 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
318the same is at most $2^{\kappa - 2}$.
319
320The \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
324to send is then $(i, y, \tau)$. The message type codes are used to
325separate ciphertexts used by the key-exchange protocol itself from those sent
326by the players later.
327
328The \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
330tag $\tau$ is valid for the message $(\id{ty}, i, y)$, checks that the
331sequence 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.}%
336and 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
e04c2d50 363 \RETURN $\bot$; \- \\
c128b544 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
376The key-exchange protocol is completely symmetrical. Either party may
377initiate, or both may attempt to converse at the same time. We shall
378describe the protocol from the point of view of Alice attempting to exchange
379a key with Bob.
380
381Alice's private key is a random index $\alpha \inr \Nupto{q}$. Her public
382key is $a = g^\alpha$. Bob's public key is $b \in G$. We'll subscript the
383variables Alice computes with an~$A$, and the values Bob has sent with a~$B$.
384Of course, if Bob is following the protocol correctly, he will have computed
385his $B$ values in a completely symmetrical way.
386
387There are six messages in the protocol, and we shall briefly discuss the
388purpose of each before embarking on the detailed descriptions. At the
389beginning of the protocol, Alice chooses a new random index $\rho_A$ and
390computes her \emph{challenge} $r_A = g^{\rho_A}$. Eventually, the shared
391secret key will be computed as $K = r_B^{\rho_A} = r_A^{\rho_B} =
392g^{\rho_A\rho_B}$, as for standard Diffie-Hellman key agreement.
393
394Throughout, we shall assume that messages are implicitly labelled with the
395sender's identity. If Alice is actually trying to talk to several other
396people she'll need to run multiple instances of the protocol, each with its
397own state, and she can use the sender label to decide which instance a
398message should be processed by. There's no need for the implicit labels to
399be attached securely.
400
401We'll summarize the messages and their part in the scheme of things before we
402start on the serious detail. For a summary of the names and symbols used in
403these descriptions, see table~\ref{tab:kx-names}. The actual message
404contents are summarized in table~\ref{tab:kx-messages}. A state-transition
405diagram of the protocol is shown in figure~\ref{fig:kx-states}. If reading
406pesudocode algorithms is your thing then you'll find message-processing
407procedures in figure~\ref{fig:kx-messages} with the necessary support procedures
408in figure~\ref{fig:kx-support}.
409
410\begin{table}
411 \begin{tabularx}{\textwidth}{Mr X}
e04c2d50
MW
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 \\
c128b544 418 \alpha \inr \Nupto{q} & Alice's private key \\
e04c2d50 419 a = g^{\alpha} & Alice's public key \\
c128b544 420 \rho_A \inr \Nupto{q} & Alice's secret Diffie-Hellman value \\
e04c2d50 421 r_A = g^{\rho_A} & Alice's public \emph{challenge} \\
c128b544 422 c_A = H(\cookie{cookie}, r_A)
e04c2d50 423 & Alice's \emph{cookie} \\
c128b544 424 v_A = \rho_A \xor H(\cookie{expected-reply}, r_A, r_B, b^{\rho_A})
e04c2d50 425 & Alice's challenge \emph{check value} \\
c128b544 426 r_B^\alpha = a^{\rho_B}
e04c2d50 427 & Alice's reply \\
c128b544 428 K = r_B^{\rho_A} = r_B^{\rho_A} = g^{\rho_A\rho_B}
e04c2d50 429 & Alice and Bob's shared secret key \\
c128b544 430 w_A = H(\cookie{switch-request}, c_A, c_B)
e04c2d50 431 & Alice's \emph{switch request} value \\
c128b544 432 u_A = H(\cookie{switch-confirm}, c_A, c_B)
e04c2d50 433 & Alice's \emph{switch confirm} value \\
c128b544 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}
e04c2d50 453
c128b544 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
539We now describe the protocol message by message, and Alice's actions when she
540receives each. Since the protocol is completely symmetrical, Bob should do
541the 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
546As 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}$
548and her \emph{cookie} $c_A = H(\cookie{cookie}, r_A)$. She sends her
549announcement of her challenge as
550\begin{equation}
551 \label{eq:kx-pre-challenge}
552 \cookie{kx-pre-challenge}, r_A
553\end{equation}
554and enters the \cookie{challenge} state.
555
556\subsubsection{The \cookie{kx-pre-challenge} message}
557
558If 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
561She must first calculate Bob's cookie $c_B = H(\cookie{cookie}, r_B)$. Then
562she has a choice: either she can send a full challenge, or she can send the
563cookie back.
564
565Suppose she decides to send a full challenge. She must compute a \emph{check
566value}
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}
571and sends
572\begin{equation}
573 \label{eq:kx-challenge}
574 \cookie{kx-challenge}, r_A, c_B, v_A
575\end{equation}
576to Bob. Then she remembers Bob's challenge for later use, and awaits his
577reply.
578
579If 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}
584to Bob and forgets all about it.
585
586Why's this useful? Well, if Alice sends off a full \cookie{kx-challenge}
587message, she must remember Bob's $r_B$ so she can check his reply and that
588involves using up a table slot. That means that someone can send Alice
589messages purporting to come from Bob which will chew up Alice's memory, and
590they don't even need to be able to read Alice's messages to Bob to do that.
591If this protocol were used over the open Internet, script kiddies from all
592over the world might be flooding Alice with bogus \cookie{kx-pre-challenge}
593messages and she'd never get around to talking to Bob.
594
595By sending a cookie intead, she avoids committing a table slot until Bob (or
596someone) sends either a cookie or a full challenge, thus proving, at least,
597that he can read her messages. This is the best we can do at this stage in
598the protocol. Against an adversary as powerful as the one we present in
599section~\fixme\ref{sec:formal} this measure provides no benefit (but we have
600to analyse it anyway); but it raises the bar too sufficiently high to
601eliminate a large class of `nuisance' attacks in the real world.
602
603Our definition of the Wrestlers Protocol doesn't stipulate when Alice should
604send a full challenge or just a cookie: we leave this up to individual
605implementations, because it makes no difference to the security of the
606protocol against powerful adversaries. But we recommend that Alice proceed
607`optimistically' at first, sending full challenges until her challenge table
608looks like it's running out, and then generating cookies only if it actually
609looks like she's under attack. This is what our pseudocode in
610figure~\ref{fig:kx-messages} does.
1a981bdb 611
c128b544 612\subsubsection{The \cookie{kx-cookie} message}
1a981bdb 613
c128b544 614When Alice receives a \cookie{kx-cookie} message, she must ensure that she's
615in the \cookie{challenge} state: if not, she rejects the message. She checks
616the cookie in the message against the value of $c_A$ she computed earlier.
617If all is well, Alice sends a \cookie{kx-challenge} message, as in
618equation~\ref{eq:kx-challenge} above.
1a981bdb 619
c128b544 620This time, she doesn't have a choice about using up a table slot to remember
621Bob's $r_B$. If her table size is fixed, she must choose a slot to recycle.
622We suggest simply recycling slots at random: this means there's no clever
623pattern of \cookie{kx-cookie} messages an attacker might be able to send to
624clog up all of Alice's slots.
1a981bdb 625
c128b544 626\subsubsection{The \cookie{kx-challenge} message}
1a981bdb 627
c128b544 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
e04c2d50 642 \id{msg-pre-challenge}(\id{data}); \- \\
c128b544 643 \ELSE \IF $\id{type} = \cookie{kx-cookie}$ \THEN \\ \ind
e04c2d50 644 \id{msg-cookie}(\id{data}); \- \\
c128b544 645 \ELSE \IF $\id{type} = \cookie{kx-challenge}$ \THEN \\ \ind
e04c2d50 646 \id{msg-challenge}(\id{data}); \- \\
c128b544 647 \ELSE \IF $\id{type} = \cookie{kx-reply}$ \THEN \\ \ind
e04c2d50 648 \id{msg-reply}(\id{data}); \- \\
c128b544 649 \ELSE \IF $\id{type} = \cookie{kx-switch}$ \THEN \\ \ind
e04c2d50 650 \id{msg-switch}(\id{data}); \- \\
c128b544 651 \ELSE \IF $\id{type} = \cookie{kx-switch-ok}$ \THEN \\ \ind
e04c2d50 652 \id{msg-switch-ok}(\id{data}); \-\- \\[\medskipamount]
c128b544 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
e04c2d50 657 $\id{send}(\cookie{kx-cookie}, r_A, \id{cookie}(r_A)))$; \- \\
c128b544 658 \ELSE \+ \\
e04c2d50
MW
659 $\id{new-chal}(r)$; \\
660 $\id{send}(\cookie{kx-challenge}, r_A,
661 \id{cookie}(r), \id{checkval}(r))$; \-\-\\[\medskipamount]
c128b544 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,
e04c2d50 668 \id{cookie}(r), \id{checkval}(r))$; \- \\[\medskipamount]
c128b544 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),
e04c2d50 678 \id{checkval}(r), y)$
c128b544 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
e04c2d50 686 \RETURN; \- \\
c128b544 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
e04c2d50
MW
707 \IF $x \ne b^{\rho_A}$ \THEN \RETURN; \\
708 $\id{chal-commit} \gets \id{chal-tab}[i]$; \- \\
c128b544 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
e04c2d50 737 \IF $\id{chal-tab}[i].c = c$ \THEN \RETURN $i$; \- \\
c128b544 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
e04c2d50 743 \RETURN $i$; \- \\
c128b544 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},
e04c2d50 753 r_A,r, b^{\rho_A})$; \- \\[\medskipamount]
c128b544 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
e04c2d50
MW
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$; \- \\
c128b544 762 \ELSE \\ \ind
e04c2d50 763 $i \getsr [\Xid{n}{chal-max}]$; \- \\
c128b544 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}
1a981bdb 774
d7d62ac0 775%%%--------------------------------------------------------------------------
1a981bdb 776
c128b544 777\section{CBC mode encryption}
778\label{sec:cbc}
779
780Our implementation of the Wrestlers Protocol uses Blowfish
781\cite{Schneier:1994:BEA} in CBC mode. However, rather than pad plaintext
782messages to a block boundary, with the ciphertext expansion that entails, we
783use a technique called \emph{ciphertext stealing}
784\cite[section 9.3]{Schneier:1996:ACP}.
785
786\subsection{Standard CBC mode}
787
788Suppose $E$ is an $\ell$-bit pseudorandom permutation. Normal CBC mode works
789as follows. Given a message $X$, we divide it into blocks $x_0, x_1, \ldots,
790x_{n-1}$. Choose a random \emph{initialization vector} $I \inr \Bin^\ell$.
791Before passing each $x_i$ through $E$, we XOR it with the previous
792ciphertext, 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}
797The ciphertext is then the concatenation of $I$ and the $y_i$. Decryption is
798simple:
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}
803See 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}
e04c2d50 836
c128b544 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
e04c2d50
MW
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$; \- \\
c128b544 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
e04c2d50
MW
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$; \- \\
c128b544 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
886The proof of this theorem is given in section~\ref{sec:cbc-proof}
887
888\subsection{Ciphertext stealing}
889
890Ciphertext stealing allows us to encrypt any message in $\Bin^*$ and make the
891ciphertext exactly $\ell$ bits longer than the plaintext. See
892figure~\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",
e04c2d50
MW
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{>}}
c128b544 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",
e04c2d50
MW
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{>}}
c128b544 954 \end{graph} \]
955
956 \caption{Encryption using CBC mode with ciphertext stealing}
957 \label{fig:cbc-steal}
e04c2d50 958\end{figure}
c128b544 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
e04c2d50
MW
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$; \- \\
c128b544 979 \IF $t \ne 0$ \THEN \\ \ind
e04c2d50
MW
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]$; \- \\
c128b544 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
e04c2d50
MW
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]$; \- \\
c128b544 995 $x \gets \emptystring$; \\
996 \FOR $1 = 0$ \TO $|y|/\ell$ \DO \\ \ind
e04c2d50
MW
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$; \- \\
c128b544 1001 \IF $t \ne 0$ \THEN \\ \ind
e04c2d50 1002 $x \gets x \cat z[0 \bitsto t] \xor y[b \bitsto b + t]$; \- \\
c128b544 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
e04c2d50
MW
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]$; \- \\
c128b544 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}
1a981bdb 1048
c128b544 1049\subsection{Proof of theorem~\ref{thm:cbc}}
1050\label{sec:cbc-proof}
1a981bdb 1051
c128b544 1052Consider an adversary $A$ attacking CBC encryption using an ideal random
1053permutation $P(\cdot)$. Pick some point in the attack game when we're just
1054about to encrypt the $n$th plaintext block. For each $i \in \Nupto{n}$,
1055let $x_i$ be the $i$th block of plaintext we've processed; let $y_i$ be the
1056corresponding ciphertext; and let $z_i = P^{-1}(y_i)$, i.e., $z_i = x_i \xor
1057I$ for the first block of a message, and $z_i = x_i \xor y_{i-1}$ for the
1058subsequent blocks.
1a981bdb 1059
c128b544 1060Say that `something went wrong' if any $z_i = z_j$ for $i \ne j$. This is
1061indeed a disaster, because it means that $y_i = y_j$ , so he can detect it,
1062and $x_i \xor y_{i-1} = x_j \xor y_{j-1}$, so he can compute an XOR
1063difference between two plaintext blocks from the ciphertext and thus
1064(possibly) reveal whether he's getting his left or right plaintexts
1065encrypted. The alternative, `everything is fine', is much better. If all
1066the $z_i$ are distinct, then because $y_i = P(z_i)$, the $y_i$ are all
1067generated by $P(\cdot)$ on inputs it's never seen before, so they're all
1068random subject to the requirement that they be distinct. If everything is
1069fine, then, the adversary has no better way of deciding whether he has a left
1070oracle or a right oracle than tossing a coin, and his advantage is therefore
1071zero. Thus, we must bound the probability that something went wrong.
874aed51 1072
c128b544 1073Assume that, at our point in the game so far, everything is fine. But we're
1074just 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}
1084Either 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
1086wrong at this point, i.e., that $z^* = z_i$ for some $0 \le i < n$. Let's
1087call 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 +
10891$ 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}
e04c2d50 1094 \Pr[x^* = x] \sum_{0\le i<n} \Pr[y^* = z_i \xor x] \\
c128b544 1095 & \le \sum_{0\le i<n} \frac{1}{2^\ell - n}
e04c2d50 1096 \sum_{x \in \Bin^\ell} \Pr[x^* = x] \\
c128b544 1097 & = \frac{n}{2^\ell - n}
1098\end{eqnarray}
874aed51 1099
c128b544 1100Having bounded the probability that something went wrong for any particular
1101block, we can proceed to bound the probability of something going wrong in
1102the course of the entire game. Let's suppose that $q = \mu_E/\ell \le
11032^{\ell/2}$; for if not, $q (q - 1) > 2^\ell$ and the theorem is trivially
1104true, since no adversary can achieve advantage greater than one.
74eb47db 1105
c128b544 1106Let's give the name $W_i$ to the probability that something went wrong after
1107encrypting $i$ blocks. We therefore want to bound $W_q$ from above.
1108Armed 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}
1115Working 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
1117W_q$.
74eb47db 1118
c128b544 1119By using an adversary attacking CBC encryption as a statistical test in an
1120attempt to distinguish $P_K(\cdot)$ from a pseudorandom permutation, we see
1121that
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}
1128where $t_P$ expresses the overhead of doing the XORs and other care and
1129feeding 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}
1134as required.
1135\qed
74eb47db 1136
1137%%%----- That's all, folks --------------------------------------------------
1138
c128b544 1139\bibliography{mdw-crypto,cryptography,cryptography2000,rfc}
74eb47db 1140\end{document}
1141
e04c2d50 1142%%% Local Variables:
74eb47db 1143%%% mode: latex
1144%%% TeX-master: "wrestlers"
d7d62ac0 1145%%% End: