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