3 %%% Description of the Wrestlers Protocol
5 %%% (c) 2001 Mark Wooding
8 \newif\iffancystyle\fancystyletrue
12 [a4paper, article,
10pt, numbering, noherefloats, notitlepage
]
14 \usepackage[palatino, helvetica, courier, maths=cmr
]{mdwfonts
}
15 \usepackage[mdwmargin
]{mdwthm
}
16 \PassOptionsToPackage{dvips}{xy
}
21 \usepackage{mdwtab, mathenv, mdwlist, mdwmath, crypto
}
22 \usepackage{amssymb, amstext
}
27 \errorcontextlines=
999
32 \title{The Wrestlers Protocol: proof-of-receipt and secure key exchange
}
33 \author{Mark Wooding
\and Clive Jones
}
35 \bibliographystyle{mdwalpha
}
37 \newcolumntype{G
}{p
{0pt
}}
38 \def\Nupto#1{\N_{<
{#1}}}
40 \let\epsilon\varepsilon
41 \let\emptystring\lambda
42 \def\bitsto{\mathbin{..
}}
44 \def\fixme{\marginpar{FIXME
}}
47 \desclabelwidth{2.5cm
}%
48 \desclabelstyle\pushlabel%
49 \let\makelabel\cookie%
52 \let\endmessages\endbasedescript
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.
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.
71 % I've not yet decided whose key-exchange model to use, but this ought to
77 %%%--------------------------------------------------------------------------
79 \section{Introduction
}
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.
85 %%%--------------------------------------------------------------------------
87 \section{Preliminaries
}
89 % Here we provide definitions of the various kinds of things we use and make,
90 % and describe some of the notation we use.
92 \subsection{Bit strings
}
94 Most of our notation for bit strings is standard. The main thing to note is
95 that everything is zero-indexed.
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| +
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
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}$.
121 \subsection{Other notation
}
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
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$.
132 \subsection{Algorithm descriptions
}
134 Most of the notation used in the algorithm descriptions should be obvious.
135 We briefly note a few features which may be unfamiliar.
137 \item The notation $a
\gets x$ denotes the action of assigning the value $x$
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$.
144 The notation is generally quite sloppy about types and scopes. In
145 particular, there are implicit coercions between bit strings, integers and
146 group elements. Any simple injective mapping will do for handling the
147 conversions. We don't think these informalities cause much confusion, and
148 they greatly simplify the presentation of the algorithms.
150 \subsection{Random oracles
}
152 We shall analyse the Wrestlers Protocol in the random oracle model
153 \cite{Bellare:
1993:ROP
}. That is, each participant including the adversary
154 is given oracle access (only) to a uniformly-distributed random function
155 $H
\colon \Bin^*
\to \Bin^
\infty$ chosen at the beginning of the game: for any
156 input string $x$, the oracle can produce, on demand, any prefix of an
157 infinitely long random answer $y = H(x)$. Repeating a query yields a prefix
158 of the same random result string; asking a new query yields a prefix of a new
159 randomly-chosen string.
161 We shan't need either to query the oracle on very long input strings nor
162 shall we need outputs much longer than a representation of a group index.
163 Indeed, since all the programs we shall be dealing with run in finite time,
164 and can therefore make only a finite number of oracle queries, each with a
165 finitely long result, we can safely think about the random oracle as a finite
168 Finally, we shall treat the oracle as a function of multiple inputs and
169 expect it to operate on some unambiguous encoding of all of the arguments in
172 \subsection{Symmetric encryption
}
174 \begin{definition
}[Symmetric encryption
]
176 A
\emph{symmetric encryption scheme
} $
\mathcal{E
} = (E, D)$ is a pair of
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 \
}$
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
189 \begin{definition
}[Chosen plaintext security for symmetric encryption
]
191 Let $
\mathcal{E
} = (E, D)$ be a symmetric encryption scheme. Let $A$ be
192 any algorithm. Define
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))
}$; \\
199 Function $
\id{lr
}(b, x_0, x_1)$: \+ \\
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
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]
210 and the
\emph{left-or-right insecurity of $
\mathcal{E
}$ under
211 chosen-plaintext attack
} is given by
213 \InSec{lor-cpa
}(
\mathcal{E
}; t, q_E,
\mu_E) =
214 \max_A \Adv{lor-cpa
}{\mathcal{E
}}(A)
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
221 \subsection{The decision Diffie-Hellman problem
}
223 Let $G$ be some cyclic group. The standard
\emph{Diffie-Hellman problem
}
224 \cite{Diffie:
1976:NDC
} is to compute $g^
{\alpha\beta}$ given $g^
\alpha$ and
225 $g^
\beta$. We need a slightly stronger assumption: that, given $g^
\alpha$
226 and $g^
\beta$, it's hard to tell the difference between the correct
227 Diffie-Hellman value $g^
{\alpha\beta}$ and a randomly-chosen group element
228 $g^
\gamma$. This is the
\emph{decision Diffie-Hellman problem
}
229 \cite{Boneh:
1998:DDP
}.
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
239 &
\Pr[\alpha \getsr \Nupto{q
};
\beta \getsr \Nupto{q
} :
240 A(g^
\alpha, g^
\beta, g^
{\alpha\beta}) =
1] -
{} \\
241 &
\Pr[\alpha \getsr \Nupto{q
};
\beta \getsr \Nupto{q
};
242 \gamma \getsr \Nupto{q
} :
243 A(g^
\alpha, g^
\beta, g^
\gamma) =
1].
246 The
\emph{insecurity function of the decision Diffie-Hellman problem in
249 \InSec{ddh
}(G; t) =
\max_A \Adv{ddh
}{G
}(A)
251 where the maximum is taken over all algorithms $A$ which run in time $t$.
254 %%%--------------------------------------------------------------------------
256 \section{The protocol
}
259 The Wrestlers Protocol is parameterized. We need the following things:
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
287 An authenticated encryption scheme with associated data (AEAD)
288 \cite{Rogaway:
2002:AEAD, Rogaway:
2001:OCB, Kohno:
2003:CWC
} could be used
289 instead of a separate symmetric encryption scheme and MAC.
291 \subsection{Symmetric encryption
}
293 The same symmetric encryption subprotocol is used both within the key
294 exchange, to ensure secrecy and binding, and afterwards for message
295 transfer. It provides a secure channel between two players, assuming that
296 the key was chosen properly.
298 A
\id{keyset
} contains the state required for communication between the two
299 players. In particular it maintains:
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
305 \item incoming and outgoing sequence numbers, to detect and prevent replay
309 The operations involved in the symmetric encryption protocol are shown in
310 figure~
\ref{fig:keyset
}.
312 The
\id{keygen
} procedure initializes a
\id{keyset
}, resetting the sequence
313 numbers, and selecting keys for the encryption scheme and MAC using the
314 random oracle. It uses the nonces $r_A$ and $r_B$ to ensure that with high
315 probability the keys are different for the two directions: assuming that
316 Alice chose her nonce $r_A$ at random, and that the keys and nonce are
317 $
\kappa$~bits long, the probability that the keys in the two directions are
318 the same is at most $
2^
{\kappa -
2}$.
320 The
\id{encrypt
} procedure constructs a ciphertext from a message $m$ and a
321 \emph{message type
} $
\id{ty
}$. It encrypts the message giving a ciphertext
322 $y$, and computes a MAC tag $
\tau$ for the triple $(
\id{ty
}, i, y)$, where
323 $i$ is the next available outgoing sequence number. The ciphertext message
324 to send is then $(i, y,
\tau)$. The message type codes are used to
325 separate ciphertexts used by the key-exchange protocol itself from those sent
326 by the players later.
328 The
\id{decrypt
} procedure recovers the plaintext from a ciphertext triple
329 $(i, y,
\tau)$, given its expected type code $
\id{ty
}$. It verifies that the
330 tag $
\tau$ is valid for the message $(
\id{ty
}, i, y)$, checks that the
331 sequence number $i$ hasn't been seen before,
\footnote{%
332 The sequence number checking shown in the figure is simple but obviously
333 secure. The actual implementation maintains a window of
32 previous
334 sequence numbers, to allow out-of-order reception of messages while still
335 preventing replay attacks. This doesn't affect our analysis.
}%
336 and then decrypts the ciphertext $y$.
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$; \\
354 Function $
\id{encrypt
}(k,
\id{ty
}, m)$: \+ \\
355 $y
\gets (E_
{k.
\Xid{K
}{enc-out
}}(m))$; \\
356 $i
\gets k.
\id{seq-out
}$; \\
357 $
\tau \gets T_
{k.
\Xid{K
}{mac-out
}}(
\id{ty
}, i, y)$; \\
358 $k.
\id{seq-out
} \gets i +
1$; \\
359 \RETURN $(i, y,
\tau)$; \- \\
[\medskipamount]
360 Function $
\id{decrypt
}(k,
\id{ty
}, c)$: \+ \\
361 $(i, y,
\tau)
\gets c$; \\
362 \IF $V_
{k.
\Xid{K
}{mac-in
}}((
\id{ty
}, i, y),
\tau) =
0$
\THEN \\
\ind
363 \RETURN $
\bot$; \- \\
364 \IF $i < k.
\id{seq-in
}$
\THEN \RETURN $
\bot$; \\
365 $m
\gets D_
{k.
\Xid{K
}{enc-in
}}(y)$; \\
366 $k.
\id{seq-in
} \gets i +
1$; \\
370 \caption{Symmetric-key encryption functions
}
374 \subsection{The key-exchange
}
376 The key-exchange protocol is completely symmetrical. Either party may
377 initiate, or both may attempt to converse at the same time. We shall
378 describe the protocol from the point of view of Alice attempting to exchange
381 Alice's private key is a random index $
\alpha \inr \Nupto{q
}$. Her public
382 key is $a = g^
\alpha$. Bob's public key is $b
\in G$. We'll subscript the
383 variables Alice computes with an~$A$, and the values Bob has sent with a~$B$.
384 Of course, if Bob is following the protocol correctly, he will have computed
385 his $B$ values in a completely symmetrical way.
387 There are six messages in the protocol, and we shall briefly discuss the
388 purpose of each before embarking on the detailed descriptions. At the
389 beginning of the protocol, Alice chooses a new random index $
\rho_A$ and
390 computes her
\emph{challenge
} $r_A = g^
{\rho_A}$. Eventually, the shared
391 secret key will be computed as $K = r_B^
{\rho_A} = r_A^
{\rho_B} =
392 g^
{\rho_A\rho_B}$, as for standard Diffie-Hellman key agreement.
394 Throughout, we shall assume that messages are implicitly labelled with the
395 sender's identity. If Alice is actually trying to talk to several other
396 people she'll need to run multiple instances of the protocol, each with its
397 own state, and she can use the sender label to decide which instance a
398 message should be processed by. There's no need for the implicit labels to
399 be attached securely.
401 We'll summarize the messages and their part in the scheme of things before we
402 start on the serious detail. For a summary of the names and symbols used in
403 these descriptions, see table~
\ref{tab:kx-names
}. The actual message
404 contents are summarized in table~
\ref{tab:kx-messages
}. A state-transition
405 diagram of the protocol is shown in figure~
\ref{fig:kx-states
}. If reading
406 pesudocode algorithms is your thing then you'll find message-processing
407 procedures in figure~
\ref{fig:kx-messages
} with the necessary support procedures
408 in figure~
\ref{fig:kx-support
}.
411 \begin{tabularx
}{\textwidth}{Mr X
}
412 G & A cyclic group known by all participants \\
413 q = |G| & The prime order of $G$ \\
414 g & A generator of $G$ \\
415 E_K(
\cdot) & Encryption under key $K$, here used to denote
416 application of the $
\id{encrypt
}(K,
\cdot)$
418 \alpha \inr \Nupto{q
} & Alice's private key \\
419 a = g^
{\alpha} & Alice's public key \\
420 \rho_A \inr \Nupto{q
} & Alice's secret Diffie-Hellman value \\
421 r_A = g^
{\rho_A} & Alice's public
\emph{challenge
} \\
422 c_A = H(
\cookie{cookie
}, r_A)
423 & Alice's
\emph{cookie
} \\
424 v_A =
\rho_A \xor H(
\cookie{expected-reply
}, r_A, r_B, b^
{\rho_A})
425 & Alice's challenge
\emph{check value
} \\
426 r_B^
\alpha = a^
{\rho_B}
428 K = r_B^
{\rho_A} = r_B^
{\rho_A} = g^
{\rho_A\rho_B}
429 & Alice and Bob's shared secret key \\
430 w_A = H(
\cookie{switch-request
}, c_A, c_B)
431 & Alice's
\emph{switch request
} value \\
432 u_A = H(
\cookie{switch-confirm
}, c_A, c_B)
433 & Alice's
\emph{switch confirm
} value \\
436 \caption{Names used during key-exchange
}
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))
450 \caption{Message contents, as sent by Alice
}
451 \label{tab:kx-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.
479 []!
{0; <
4.5cm,
0cm>: <
0cm,
1.5cm>::
}
480 *++
[F:<
4pt>
]\txt{\ns Start \\ Choose $
\rho_A$
} ="start"
483 \ns State
\c{challenge
} \\
484 Send $(
\c{pre-challenge
}, r_A)$
}
486 [] "chal" !
{!L(
0.5)
} ="chal-cookie"
488 *+
\txt{Send $(
\c{cookie
}, r_A, c_B)$
}
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)$
}
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)$
}
500 *+
\txt{Send \\ $(
\c{reply
}, c_A, c_B, $\\$ v_A, E_K(r_B^
\alpha))$
}
502 |*+
\txt{Receive \\ $(
\c{challenge
}, $\\$ r_B, c_A, v_B)$
}
504 |*+
\txt{Receive \\ $(
\c{challenge
}, $\\$ r_B, c_A, v_B)$
}
507 \ns State
\c{commit
} \\
508 Send \\ $(
\c{switch
}, c_A, c_B, $\\$ E_K(r_B^
\alpha, w_A))$
}
510 |*+
\txt{Receive \\ $(
\c{reply
}, c_B, c_A, $\\$ v_B, E_K(b^
{\rho_A}))$
}
512 *+
\txt{Send \\ $(
\c{switch-ok
}, E_K(u_A))$
}
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))$
}
520 *++
[F:<
4pt>
]\txt{\ns 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
}
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"
}
535 \caption{State-transition diagram for key-exchange protocol
}
536 \label{fig:kx-states
}
539 We now describe the protocol message by message, and Alice's actions when she
540 receives each. Since the protocol is completely symmetrical, Bob should do
541 the same, only swapping round $A$ and $B$ subscripts, the public keys $a$ and
542 $b$, and using his private key $
\beta$ instead of $
\alpha$.
544 \subsubsection{Starting the protocol
}
546 As described above, at the beginning of the protocol Alice chooses a random
547 $
\rho_A \inr \Nupto q$, and computes her
\emph{challenge
} $r_A = g^
{\rho_A}$
548 and her
\emph{cookie
} $c_A = H(
\cookie{cookie
}, r_A)$. She sends her
549 announcement of her challenge as
551 \label{eq:kx-pre-challenge
}
552 \cookie{kx-pre-challenge
}, r_A
554 and enters the
\cookie{challenge
} state.
556 \subsubsection{The
\cookie{kx-pre-challenge
} message
}
558 If Alice receieves a
\cookie{kx-pre-challenge
}, she ensures that she's in the
559 \cookie{challenge
} state: if not, she rejects the message.
561 She must first calculate Bob's cookie $c_B = H(
\cookie{cookie
}, r_B)$. Then
562 she has a choice: either she can send a full challenge, or she can send the
565 Suppose she decides to send a full challenge. She must compute a
\emph{check
569 v_A =
\rho_A \xor H(
\cookie{expected-reply
}, r_A, r_B, b^
{\rho_A})
573 \label{eq:kx-challenge
}
574 \cookie{kx-challenge
}, r_A, c_B, v_A
576 to Bob. Then she remembers Bob's challenge for later use, and awaits his
579 If she decides to send only a cookie, she just transmits
582 \cookie{kx-cookie
}, r_A, c_B
584 to Bob and forgets all about it.
586 Why's this useful? Well, if Alice sends off a full
\cookie{kx-challenge
}
587 message, she must remember Bob's $r_B$ so she can check his reply and that
588 involves using up a table slot. That means that someone can send Alice
589 messages purporting to come from Bob which will chew up Alice's memory, and
590 they don't even need to be able to read Alice's messages to Bob to do that.
591 If this protocol were used over the open Internet, script kiddies from all
592 over the world might be flooding Alice with bogus
\cookie{kx-pre-challenge
}
593 messages and she'd never get around to talking to Bob.
595 By sending a cookie intead, she avoids committing a table slot until Bob (or
596 someone) sends either a cookie or a full challenge, thus proving, at least,
597 that he can read her messages. This is the best we can do at this stage in
598 the protocol. Against an adversary as powerful as the one we present in
599 section~
\fixme\ref{sec:formal
} this measure provides no benefit (but we have
600 to analyse it anyway); but it raises the bar too sufficiently high to
601 eliminate a large class of `nuisance' attacks in the real world.
603 Our definition of the Wrestlers Protocol doesn't stipulate when Alice should
604 send a full challenge or just a cookie: we leave this up to individual
605 implementations, because it makes no difference to the security of the
606 protocol against powerful adversaries. But we recommend that Alice proceed
607 `optimistically' at first, sending full challenges until her challenge table
608 looks like it's running out, and then generating cookies only if it actually
609 looks like she's under attack. This is what our pseudocode in
610 figure~
\ref{fig:kx-messages
} does.
612 \subsubsection{The
\cookie{kx-cookie
} message
}
614 When Alice receives a
\cookie{kx-cookie
} message, she must ensure that she's
615 in the
\cookie{challenge
} state: if not, she rejects the message. She checks
616 the cookie in the message against the value of $c_A$ she computed earlier.
617 If all is well, Alice sends a
\cookie{kx-challenge
} message, as in
618 equation~
\ref{eq:kx-challenge
} above.
620 This time, she doesn't have a choice about using up a table slot to remember
621 Bob's $r_B$. If her table size is fixed, she must choose a slot to recycle.
622 We suggest simply recycling slots at random: this means there's no clever
623 pattern of
\cookie{kx-cookie
} messages an attacker might be able to send to
624 clog up all of Alice's slots.
626 \subsubsection{The
\cookie{kx-challenge
} message
}
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$; \\
638 $
\id{chal-commit
} \gets \bot$; \\
639 $
\id{send
}(
\cookie{kx-pre-challenge
}, r_A)$; \- \\
[\medskipamount]
640 Procedure $
\id{kx-receive
}(
\id{type
},
\id{data
})$: \\
\ind
641 \IF $
\id{type
} =
\cookie{kx-pre-challenge
}$
\THEN \\
\ind
642 \id{msg-pre-challenge
}(
\id{data
}); \- \\
643 \ELSE \IF $
\id{type
} =
\cookie{kx-cookie
}$
\THEN \\
\ind
644 \id{msg-cookie
}(
\id{data
}); \- \\
645 \ELSE \IF $
\id{type
} =
\cookie{kx-challenge
}$
\THEN \\
\ind
646 \id{msg-challenge
}(
\id{data
}); \- \\
647 \ELSE \IF $
\id{type
} =
\cookie{kx-reply
}$
\THEN \\
\ind
648 \id{msg-reply
}(
\id{data
}); \- \\
649 \ELSE \IF $
\id{type
} =
\cookie{kx-switch
}$
\THEN \\
\ind
650 \id{msg-switch
}(
\id{data
}); \- \\
651 \ELSE \IF $
\id{type
} =
\cookie{kx-switch-ok
}$
\THEN \\
\ind
652 \id{msg-switch-ok
}(
\id{data
}); \-\- \\
[\medskipamount]
653 Procedure $
\id{msg-pre-challenge
}(
\id{data
})$: \+ \\
654 \IF $
\id{state
} \ne \cookie{challenge
}$
\THEN \RETURN; \\
655 $r
\gets \id{data
}$; \\
656 \IF $
\Xid{n
}{chal
} \ge \Xid{n
}{chal-thresh
}$
\THEN \\
\ind
657 $
\id{send
}(
\cookie{kx-cookie
}, r_A,
\id{cookie
}(r_A)))$; \- \\
659 $
\id{new-chal
}(r)$; \\
660 $
\id{send
}(
\cookie{kx-challenge
}, r_A,
661 \id{cookie
}(r),
\id{checkval
}(r))$; \-\-\\
[\medskipamount]
662 Procedure $
\id{msg-cookie
}(
\id{data
})$: \+ \\
663 \IF $
\id{state
} \ne \cookie{challenge
}$
\THEN \RETURN; \\
664 $(r, c_A)
\gets \id{data
}$; \\
665 \IF $c_A
\ne \id{cookie
}(r_A)$
\THEN \RETURN; \\
666 $
\id{new-chal
}(r)$; \\
667 $
\id{send
}(
\cookie{kx-challenge
}, r_A,
668 \id{cookie
}(r),
\id{checkval
}(r))$; \- \\
[\medskipamount]
669 Procedure $
\id{msg-challenge
}(
\id{data
})$: \+ \\
670 \IF $
\id{state
} \ne \cookie{challenge
}$
\THEN \RETURN; \\
671 $(r, c_A, v)
\gets \id{data
}$; \\
672 \IF $c_A
\ne \id{cookie
}(r_A)$
\THEN \RETURN; \\
673 $i
\gets \id{check-reply
}(
\bot, r, v)$; \\
674 \IF $i =
\bot$
\THEN \RETURN; \\
675 $k
\gets \id{chal-tab
}[i
].k$; \\
676 $y
\gets \id{encrypt
}(k,
\cookie{kx-reply
}, r^
\alpha)$; \\
677 $
\id{send
}(
\cookie{kx-reply
}, c_A,
\id{cookie
}(r),
678 \id{checkval
}(r), y)$
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
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; \\
706 \IF $
\id{state
} =
\cookie{challenge
}$
\THEN \\
\ind
707 \IF $x
\ne b^
{\rho_A}$
\THEN \RETURN; \\
708 $
\id{chal-commit
} \gets \id{chal-tab
}[i
]$; \- \\
709 \ELSE \IF $c
\ne \id{chal-commit
}.c$
\THEN \RETURN; \\
710 \IF $w
\ne H(
\cookie{switch-request
}, c, c_A)$
\THEN \RETURN; \\
711 $w
\gets H(
\cookie{switch-confirm
}, c_A, c)$; \\
712 $y
\gets \id{encrypt
}(y,
\cookie{kx-switch-ok
}, w)$; \\
713 $
\id{send
}(
\cookie{switch-ok
}, y)$; \\
714 $
\id{done
}(k)$; \- \\
[\medskipamount]
715 Procedure $
\id{msg-switch-ok
}(
\id{data
})$ \+ \\
716 \IF $
\id{state
} \ne \cookie{commit
}$
\THEN \RETURN; \\
717 $y
\gets \id{data
}$; \\
718 $k
\gets \id{chal-commit
}.k$; \\
719 $w
\gets \id{decrypt
}(k,
\cookie{kx-switch-ok
}, y)$; \\
720 \IF $w =
\bot$
\THEN \RETURN; \\
721 $c
\gets \id{chal-commit
}.c$; \\
722 $c_A
\gets \id{cookie
}(r_A)$; \\
723 \IF $w
\ne H(
\cookie{switch-confirm
}, c, c_A)$
\THEN \RETURN; \\
727 \caption{The key-exchange protocol: message handling
}
728 \label{fig:kx-messages
}
733 Structure $
\id{chal-slot
}$: \+ \\
734 $r$; $c$; $
\id{replied
}$; $k$; \- \\
[\medskipamount]
735 Function $
\id{find-chal
}(c)$: \+ \\
736 \FOR $i =
0$
\TO $
\Xid{n
}{chal
}$
\DO \\
\ind
737 \IF $
\id{chal-tab
}[i
].c = c$
\THEN \RETURN $i$; \- \\
738 \RETURN $
\bot$; \- \\
[\medskipamount]
739 Function $
\id{cookie
}(r)$: \+ \\
740 \RETURN $H(
\cookie{cookie
}, r)$; \- \\
[\medskipamount]
741 Function $
\id{check-reply
}(i, r, v)$: \+ \\
742 \IF $i
\ne \bot \land \id{chal-tab
}[i
].
\id{replied
} =
1$
\THEN \\
\ind
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$; \\
751 Function $
\id{checkval
}(r)$: \\
\ind
752 \RETURN $
\rho_A \xor H(
\cookie{expected-reply
},
753 r_A,r, b^
{\rho_A})$; \- \\
[\medskipamount]
754 Function $
\id{new-chal
}(r)$: \+ \\
755 $c
\gets \id{cookie
}(r)$; \\
756 $i
\gets \id{find-chal
}(c)$; \\
757 \IF $i
\ne \bot$
\THEN \RETURN $i$; \\
758 \IF $
\Xid{n
}{chal
} <
\Xid{n
}{chal-max
}$
\THEN \\
\ind
759 $i
\gets \Xid{n
}{chal
}$; \\
760 $
\id{chal-tab
}[i
] \gets \NEW \id{chal-slot
}$; \\
761 $
\Xid{n
}{chal
} \gets \Xid{n
}{chal
} +
1$; \- \\
763 $i
\getsr [\Xid{n
}{chal-max
}]$; \- \\
764 $
\id{chal-tab
}[i
].r
\gets r$; \\
765 $
\id{chal-tab
}[i
].c
\gets c$; \\
766 $
\id{chal-tab
}[i
].
\id{replied
} \gets 0$; \\
767 $
\id{chal-tab
}[i
].k
\gets \bot$; \\
771 \caption{The key-exchange protocol: support functions
}
772 \label{fig:kx-support
}
775 %%%--------------------------------------------------------------------------
777 \section{CBC mode encryption
}
780 Our implementation of the Wrestlers Protocol uses Blowfish
781 \cite{Schneier:
1994:BEA
} in CBC mode. However, rather than pad plaintext
782 messages to a block boundary, with the ciphertext expansion that entails, we
783 use a technique called
\emph{ciphertext stealing
}
784 \cite[section
9.3]{Schneier:
1996:ACP
}.
786 \subsection{Standard CBC mode
}
788 Suppose $E$ is an $
\ell$-bit pseudorandom permutation. Normal CBC mode works
789 as follows. Given a message $X$, we divide it into blocks $x_0, x_1,
\ldots,
790 x_
{n-
1}$. Choose a random
\emph{initialization vector
} $I
\inr \Bin^
\ell$.
791 Before passing each $x_i$ through $E$, we XOR it with the previous
792 ciphertext, with $I$ standing in for the first block:
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$)
}.
797 The ciphertext is then the concatenation of $I$ and the $y_i$. Decryption is
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$)
}
803 See figure~
\ref{fig:cbc
} for a diagram of CBC encryption.
807 []!
{0; <
0.85cm,
0cm>: <
0cm,
0.5cm>::
}
808 *+=(
1,
0)+
[F
]{\mathstrut x_0
}="x"
810 [ll
] *+=(
1,
0)+
[F
]{I
} :"xor"
811 :
[dd
] *+
[F
]{E
}="e" :
[ddd
] *+=(
1,
0)+
[F
]{\mathstrut y_0
}="i"
813 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_1
}="x"
815 "e"
[d
] :`r
[ru
] `u "xor" "xor"
816 :
[dd
] *+
[F
]{E
}="e" :
[ddd
]
817 *+=(
1,
0)+
[F
]{\mathstrut y_1
}="i"
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"
827 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
828 :
[dd
] *+
[F
]{E
}="e" :
[ddd
]
829 *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
1}}="i"
833 \caption{Encryption using CBC mode
}
837 \begin{definition
}[CBC mode
]
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:
845 Algorithm $
\Xid{E
}{CBC
}^P_K(x)$: \+ \\
846 $I
\getsr \Bin^
\ell$; \\
848 \FOR $i =
0$
\TO $|x|/
\ell$
\DO \\
\ind
849 $x_i
\gets x
[\ell i
\bitsto \ell (i +
1)
]$; \\
850 $y_i
\gets P_K(x_i
\xor I)$; \\
852 $y
\gets y
\cat y_i$; \- \\
855 Algorithm $
\Xid{D
}{CBC
}^P_K(y)$: \+ \\
856 $I
\gets y
[0 \bitsto \ell]$; \\
857 $x
\gets \emptystring$; \\
858 \FOR $
1 =
0$
\TO $|y|/
\ell$
\DO \\
\ind
859 $y_i
\gets y
[\ell i
\bitsto \ell (i +
1)
]$; \\
860 $x_i
\gets P^
{-
1}_K(y_i)
\xor I$; \\
862 $x
\gets x
\cat x_i$; \- \\
867 \begin{theorem
}[Security of standard CBC mode
]
869 Let $P
\colon \keys P
\times \Bin^
\ell \to \Bin^
\ell$ be a pseudorandom
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}}
876 where $q =
\mu_E/
\ell$ and $t_P$ is some small constant.
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.
886 The proof of this theorem is given in section~
\ref{sec:cbc-proof
}
888 \subsection{Ciphertext stealing
}
890 Ciphertext stealing allows us to encrypt any message in $
\Bin^*$ and make the
891 ciphertext exactly $
\ell$ bits longer than the plaintext. See
892 figure~
\ref{fig:cbc-steal
} for a diagram.
896 []!
{0; <
0.85cm,
0cm>: <
0cm,
0.5cm>::
}
897 *+=(
1,
0)+
[F
]{\mathstrut x_0
}="x"
899 [ll
] *+=(
1,
0)+
[F
]{I
} :"xor"
900 :
[dd
] *+
[F
]{E
}="e" :
[ddddd
] *+=(
1,
0)+
[F
]{\mathstrut y_0
}="i"
902 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_1
}="x"
904 "e"
[d
] :`r
[ru
] `u "xor" "xor"
905 :
[dd
] *+
[F
]{E
}="e" :
[ddddd
]
906 *+=(
1,
0)+
[F
]{\mathstrut y_1
}="i"
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"
916 "e"
[d
] :@
{-->
}`r
[ru
] `u "xor" "xor"
919 [rrruuuu
] *+=(
1,
0)+
[F
]{\mathstrut x_
{n-
1} \cat 0^
{\ell-t
}}="x"
921 "e"
[d
] :`r
[ru
] `u "xor" "xor"
922 "e"
[dddddrrr
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
1}[0 \bitsto t
]}="i"
925 []!
{"x"; "e" **
{}, "x"+/
4pt/ ="p",
926 "x"; "y" **
{}, "x"+/
4pt/ ="q",
927 "y"; "x" **
{}, "y"+/
4pt/ ="r",
928 "y"; "i" **
{}, "y"+/
4pt/ ="s",
934 "i" **
\dir{-
}?>*
\dir{>
}}
935 "xor" :
[dd
] *+
[F
]{E
}="e"
937 "e"
[dddddlll
] *+=(
1,
0)+
[F
]{\mathstrut y_
{n-
2}}="i"
940 []!
{"x"; "e" **
{}, "x"+/
4pt/ ="p",
941 "x"; "y" **
{}, "x"+/
4pt/ ="q",
942 "y"; "x" **
{}, "y"+/
4pt/ ="r",
943 "y"; "i" **
{}, "y"+/
4pt/ ="s",
944 "x"; "y" **
{} ?="c" ?(
0.5)/-
4pt/ ="cx" ?(
0.5)/
4pt/ ="cy",
949 "c" *
[@
]\cir<
4pt>
{d^u
};
953 "i" **
\dir{-
}?>*
\dir{>
}}
956 \caption{Encryption using CBC mode with ciphertext stealing
}
957 \label{fig:cbc-steal
}
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:
969 Algorithm $
\Xid{E
}{CBC-steal
}^P_K(x)$: \+ \\
970 $I
\getsr \Bin^
\ell$; \\
972 $t = |x|
\bmod \ell$; \\
973 \IF $t
\ne 0$
\THEN $x
\gets x
\cat 0^
{\ell-t
}$; \\
974 \FOR $i =
0$
\TO $|x|/
\ell$
\DO \\
\ind
975 $x_i
\gets x
[\ell i
\bitsto \ell (i +
1)
]$; \\
976 $y_i
\gets P_K(x_i
\xor I)$; \\
978 $y
\gets y
\cat y_i$; \- \\
979 \IF $t
\ne 0$
\THEN \\
\ind
980 $b
\gets |y| -
2\ell$; \\
981 $y
\gets $\=$y
[0 \bitsto b
] \cat
982 y
[b +
\ell \bitsto |y|
] \cat {}$ \\
983 \>$y
[b
\bitsto b + t
]$; \- \\
986 Algorithm $
\Xid{D
}{CBC-steal
}^P_K(y)$: \+ \\
987 $I
\gets y
[0 \bitsto \ell]$; \\
988 $t = |y|
\bmod \ell$; \\
989 \IF $t
\ne 0$
\THEN \\
\ind
990 $b
\gets |y| - t -
\ell$; \\
991 $z
\gets P^
{-
1}_K(y
[b
\bitsto b +
\ell])$; \\
992 $y
\gets $\=$y
[0 \bitsto b
] \cat
993 y
[b +
\ell \bitsto |y|
] \cat {}$ \\
994 \>$z
[t
\bitsto \ell]$; \- \\
995 $x
\gets \emptystring$; \\
996 \FOR $
1 =
0$
\TO $|y|/
\ell$
\DO \\
\ind
997 $y_i
\gets y
[\ell i
\bitsto \ell (i +
1)
]$; \\
998 $x_i
\gets P^
{-
1}_K(y_i)
\xor I$; \\
1000 $x
\gets x
\cat x_i$; \- \\
1001 \IF $t
\ne 0$
\THEN \\
\ind
1002 $x
\gets x
\cat z
[0 \bitsto t
] \xor y
[b
\bitsto b + t
]$; \- \\
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
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}}
1016 where $q =
\mu_E/
\ell$ and $t_P$ is some small constant.
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$:
1024 Adversary $A'^
{E(
\cdot)
}$: \+ \\
1025 $b
\gets A^
{\Xid{E
}{steal
}(
\cdot)
}$; \\
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)))$;
1032 Function $
\id{pad
}(x)$: \+ \\
1033 $t
\gets |x|
\bmod \ell$; \\
1034 \RETURN $x
\cat 0^
{\ell-t
}$;
1035 \- \\
[\medskipamount]
1036 Function $
\id{steal
}(l, y)$: \+ \\
1037 $t
\gets l
\bmod \ell$; \\
1038 \IF $t
\ne 0$
\THEN \\
\ind
1039 $b
\gets |y| -
2\ell$; \\
1040 $y
\gets $\=$y
[0 \bitsto b
] \cat
1041 y
[b +
\ell \bitsto |y|
] \cat y
[b
\bitsto b + t
]$; \- \\
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
1049 \subsection{Proof of theorem~
\ref{thm:cbc
}}
1050 \label{sec:cbc-proof
}
1052 Consider an adversary $A$ attacking CBC encryption using an ideal random
1053 permutation $P(
\cdot)$. Pick some point in the attack game when we're just
1054 about to encrypt the $n$th plaintext block. For each $i
\in \Nupto{n
}$,
1055 let $x_i$ be the $i$th block of plaintext we've processed; let $y_i$ be the
1056 corresponding ciphertext; and let $z_i = P^
{-
1}(y_i)$, i.e., $z_i = x_i
\xor
1057 I$ for the first block of a message, and $z_i = x_i
\xor y_
{i-
1}$ for the
1060 Say that `something went wrong' if any $z_i = z_j$ for $i
\ne j$. This is
1061 indeed a disaster, because it means that $y_i = y_j$ , so he can detect it,
1062 and $x_i
\xor y_
{i-
1} = x_j
\xor y_
{j-
1}$, so he can compute an XOR
1063 difference between two plaintext blocks from the ciphertext and thus
1064 (possibly) reveal whether he's getting his left or right plaintexts
1065 encrypted. The alternative, `everything is fine', is much better. If all
1066 the $z_i$ are distinct, then because $y_i = P(z_i)$, the $y_i$ are all
1067 generated by $P(
\cdot)$ on inputs it's never seen before, so they're all
1068 random subject to the requirement that they be distinct. If everything is
1069 fine, then, the adversary has no better way of deciding whether he has a left
1070 oracle or a right oracle than tossing a coin, and his advantage is therefore
1071 zero. Thus, we must bound the probability that something went wrong.
1073 Assume that, at our point in the game so far, everything is fine. But we're
1074 just about to encrypt $x^* = x_n$. There are two cases:
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
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}$.
1084 Either way, the adversary's choice of $x^*$ is independent of $y^*$. Let
1085 $z^* = x^*
\xor y^*$. We want to know the probability that something goes
1086 wrong at this point, i.e., that $z^* = z_i$ for some $
0 \le i < n$. Let's
1087 call this event $C_n$. Note first that, in the first case, there are
1088 $
2^
\ell$ possible values for $y^*$ and in the second there are $
2^
\ell - n +
1089 1$ possibilities for $y^*$. Then
1090 \begin{eqnarray
}[rl
]
1092 & =
\sum_{x
\in \Bin^
\ell} \Pr[C_n
\mid x^* = x
] \Pr[x^* = x
] \\
1093 & =
\sum_{x
\in \Bin^
\ell}
1094 \Pr[x^* = x
] \sum_{0\le i<n
} \Pr[y^* = z_i
\xor x
] \\
1095 &
\le \sum_{0\le i<n
} \frac{1}{2^
\ell - n
}
1096 \sum_{x
\in \Bin^
\ell} \Pr[x^* = x
] \\
1097 & =
\frac{n
}{2^
\ell - n
}
1100 Having bounded the probability that something went wrong for any particular
1101 block, we can proceed to bound the probability of something going wrong in
1102 the course of the entire game. Let's suppose that $q =
\mu_E/
\ell \le
1103 2^
{\ell/
2}$; for if not, $q (q -
1) >
2^
\ell$ and the theorem is trivially
1104 true, since no adversary can achieve advantage greater than one.
1106 Let's give the name $W_i$ to the probability that something went wrong after
1107 encrypting $i$ blocks. We therefore want to bound $W_q$ from above.
1108 Armed with the knowledge that $q
\le 2^
{\ell/
2}$, we have
1109 \begin{eqnarray
}[rl
]
1110 W_q &
\le \sum_{0\le i<q
} \Pr[C_i
]
1111 \le \sum_{0\le i<q
} \frac{i
}{2^
\ell - i
} \\
1112 &
\le \frac{1}{2^
\ell -
2^
{\ell/
2}} \sum_{0\le i<q
} i \\
1113 &=
\frac{q (q -
1)
}{2 \cdot (
2^
\ell -
2^
{\ell/
2})
}
1115 Working through the definition of LOR-CPA security, we can see that $A$'s
1116 (and hence any adversary's) advantage against the ideal system is at most $
2
1119 By using an adversary attacking CBC encryption as a statistical test in an
1120 attempt to distinguish $P_K(
\cdot)$ from a pseudorandom permutation, we see
1123 \InSec{prp
}(P; t + q t_P, q)
\ge
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})
}
1128 where $t_P$ expresses the overhead of doing the XORs and other care and
1129 feeding of the CBC adversary; whence
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}}
1137 %%%----- That's all, folks --------------------------------------------------
1139 \bibliography{mdw-crypto,cryptography,cryptography2000,rfc
}
1142 %%% Local Variables:
1144 %%% TeX-master: "wrestlers"