}
\fi
\def\fixme{\marginpar{FIXME}}
+\def\hex#1{\texttt{#1}_{x}}
\newslowboxenv{cgraph}{\par$$}{\begin{graph}}{\end{graph}}{$$\par}
\newslowboxenv{vgraph}
errors we discovered in previous work, or some combination of these. We
provide a new security notion for symmetric encryption which turns out to
be rather useful when analysing block cipher modes. Finally, we define a
- new, condition for initialization vectors, introducing the concept of a
- `generalized counter', and proving that generalized suffice for security in
- (full-width) CFB and OFB modes and that generalized counters encrypted
- using the block cipher (with the same key) suffice for all the encryption
- modes we study.
+ new condition for initialization vectors, introducing the concept of a
+ `generalized counter', and proving that generalized counters suffice for
+ security in (full-width) CFB and OFB modes and that generalized counters
+ encrypted using the block cipher (with the same key) suffice for all the
+ encryption modes we study.
\end{abstract}
\iffancystyle
The following proposition relates our new notion to the existing known
notions of security.
+\begingroup
+\def\Wror{{W_{\text{ROR}}}}
\begin{proposition}[ROG $\Leftrightarrow$ LOR]
\label{prop:rog-and-lor}
Let $\E$ be a symmetric encryption scheme. Then,
\InSec{rog-cpa-$W$}(\E; t + t_E \mu_E, q_E, \mu_E)
\]
and
- \item there exists a garbage-emission algorithm $W$ for which
- \[ \InSec{rog-cpa-$W$}(\E; t, q_E, \mu_E)
+ \item there exists a garbage-emission algorithm $\Wror$ for which
+ \[ \InSec{rog-cpa-$\Wror$}(\E; t, q_E, \mu_E)
\le \InSec{lor-cpa}(\E; t + t_E \mu_E, q_E, \mu_E)
\]
\end{enumerate}
for some fairly small constant $t_E$.
\end{proposition}
-\begin{proof}
+\begin{remark}
+ Note the asymmetry between these two statements. ROG-CPA-$W$ implies
+ LOR-CPA for \emph{any} garbage emitter $W$, but LOR-CPA implies
+ ROG-CPA-$\Wror$ for the specific emitter $\Wror$ only.
+\end{remark}
+\begin{proof}[Proof of proposition \ref{prop:rog-and-lor}]
\begin{enumerate}
\item Let $W$ and $\E$ be given, and let $A$ be an adversary attacking the
LOR-CPA security of $\E$. Consider adversary $B$ attacking $\E$'s
\frac{1}{2}$. The result follows.
\item Let $\E = (G, E, D)$ be given. Our garbage emitter simulates the
real-or-random game of \cite{Bellare:2000:CST}. Let $K_W = \bot$
- initially: we define our emitter $W$ thus:
+ initially: we define our emitter $\Wror$ thus:
\begin{program}
- Garbage emitter $W(n)$: \+ \\
+ Garbage emitter $\Wror(n)$: \+ \\
\IF $K_W = \bot$ \THEN $K_W \gets G()$; \\
$x \getsr \Bin^n$; \\
- \RETURN $E_K(x)$;
+ \RETURN $E_{K_W}(x)$;
\end{program}
- We now show that $\InSec{rog-cpa-$W$}(\E; t, q_E, \mu_E) \le
- \InSec{lor-cpa}(\E; t + t_E \mu_E, q_E, \mu_E)$ for our $W$. Let $A$ be
- an adversary attacking the ROG-CPA-$W$ security of $\E$. Consider
+ We now show that $\InSec{rog-cpa-$\Wror$}(\E; t, q_E, \mu_E) \le
+ \InSec{lor-cpa}(\E; t + t_E \mu_E, q_E, \mu_E)$ for our $\Wror$. Let $A$
+ be an adversary attacking the ROG-CPA-$\Wror$ security of $\E$. Consider
adversary $B$ attacking $\E$'s LOR-CPA security:
\begin{program}
Adversary $B^{E(\cdot, \cdot)}$: \+ \\
$x' \getsr \Bin^{|x|}$; \\
\RETURN $E(x', x)$;
\end{program}
- The adversary simulates the ROG-CPA-$W$ games perfectly for our chosen
- $W$, since the game has chosen the random $K_W$ for us already: the
- `left' game returns only the results of encrypting random `garbage'
- plaintexts $x'$, while the right game returns correct results of
- encrypting the given plaintexts $x$. The result follows.
- \qed
+ The adversary simulates the ROG-CPA-$\Wror$ games perfectly, since the
+ game has chosen the random $K_W$ for us already: the `left' game returns
+ only the results of encrypting random `garbage' plaintexts $x'$, while
+ the right game returns correct results of encrypting the given plaintexts
+ $x$. The result follows. \qed
\end{enumerate}
\end{proof}
-
+\endgroup
\subsection{Message authentication}
all plaintexts $x$ and all initialization vectors $v$, if $(v', y) =
\id{encrypt}^{P(\cdot)}(v, x)$ then $x = \id{decrypt}^{P(\cdot),
P^{-1}(\cdot)}(v, y)$.
- \item There exists an efficient algorithm which, given a ciphertext $y$ and
- the initialization vector but \emph{not} access to $P$, computes the
- chaining value $v'$ such that $(v', y) = \id{encrypt}^P(v, x)$.
\end{enumerate}
Similarly, a \emph{PRF encryption mode} $m_F = (\id{encrypt},
\id{decrypt})$ is a pair of deterministic oracle algorithms (and
\item For all functions $F\colon \Bin^\ell \to \Bin^L$, all plaintexts $x$
and all initialization vectors $v$, if $(v', y) =
\id{encrypt}^{F(\cdot)}(v, x)$ then $x = \id{decrypt}^{F(\cdot)}(v, y)$.
- \item There exists an efficient algorithm which, given a ciphertext $y$ and
- the initialization vector but \emph{not} access to $F$, computes the
- chaining value $v'$ such that $(v', y) = \id{encrypt}^F(v, x)$.
- \qed
+ \qed
\end{enumerate}
\end{definition}
encryption schemes of definition~\ref{def:enc-scheme}, constructed from a
pseudorandom permutation $P\colon \Bin^\ell \leftrightarrow \Bin^\ell$.
If $q$ is an upper bound on the number of PRP applications required for
- the encryption $q_E$ messages totalling $\mu_E$ bits, and $t'$ is some
- small constant, then
+ the encryption $q_E$ messages totalling $\mu_E$ bits, then there is some
+ small constant $t'$ such that
\[ \InSec{lor-cpa}(\E^P; t, q_E, \mu_E) \le
\InSec{lor-cpa}(\E^{\Perm{\ell}}; t, q_E, \mu_E) +
2 \cdot \InSec{prp}(P; t + q t', q) .
symmetric encryption schemes of definition~\ref{def:enc-scheme},
constructed from a pseudorandom function $F\colon \Bin^\ell \to \Bin^L$.
If $q$ is an upper bound on the number of PRP applications required for
- the encryption $q_E$ messages totalling $\mu_E$ bits, and $t'$ is some
- small constant, then
+ the encryption $q_E$ messages totalling $\mu_E$ bits, then there is some
+ small constant $t'$ such that
\[ \InSec{lor-cpa}(\E^F; t, q_E, \mu_E) \le
\InSec{lor-cpa}(\E^{\Func{\ell}{L}}; t, q_E, \mu_E) +
2 \cdot \InSec{prf}(F; t + q t', q) .
\end{proposition}
\begin{proof}
- For 1, it suffices to note that $\Xid{E}{$m\$$}^F \equiv \Xid{E}{$m$H}^{c,
- V_0}_{0, 0, 0}$ for any $c$, $V_0$. For the others, we observe that, while
- the IVs returned in the ciphertexts differ, it's very easy to simulate
- encryption for the practical schemes given an encryption oracle for the
- hybrid scheme: for the counter and encrypted-counter schemes, the counter
- function is public knowledge; for the carry-over scheme, the correct IV for
- the first message is known, and the IV any subsequent messages can be
- computed from the previous IV and ciphertext according to condition~4 in
- definition~\ref{def:enc-scheme}.
+ For 1, it suffices to observe that $\Xid{E}{$m\$$}^F \equiv
+ \Xid{E}{$m$H}^{F, V_0, c}_{0, 0, 0}$ for any $c$, $V_0$. For 2, note that
+ $\Xid{E}{$m$C}^{F, c}$ behaves identically to $\Xid{E}{$m$H}^{F, V_0,
+ c}_{q_E, 0, 0}$ for any $c$, $V_0$ for the first $q_E$ encryption
+ queries; but no adversary is permitted to exceed this limit, and hence no
+ adversary can distinguish the two. Similarly, for 4, note that
+ $\Xid{E}{$m$L}^{F, V_0}$ behaves identically to $\Xid{E}{$m$H}^{F, V_0,
+ c}_{0, 0, q_E}$ for any $c$, $V_0$ for the first $q_E$ encryption
+ queries.
+
+ The case of 3 is slightly more complicated: $\Xid{E}{$m$E}^{F, c}$ behaves
+ identically to $\Xid{E}{$m$H}^{F, V_0, c}_{0, q_E, 0}$ for the first $q_E$
+ encryption queries \emph{except} that the latter returns different
+ initialization vectors from its encryption oracle. However, since the
+ counter $c$ is fixed public knowledge, it is trivial to construct a fully
+ faithful replica of the $m$E game given the hybrid oracle, such that no
+ adversary can distinguish the two.
\end{proof}
%%%--------------------------------------------------------------------------
\RETURN $(v, x)$;
\end{program}
Now, let $c$ be a generalized counter in $\Bin^\ell$. We define the
- encryption schemes $\Xid{E}{CBC$\$$}^P$, $\Xid{E}{CBCE}^P$ and
+ encryption schemes $\Xid{E}{CBC$\$$}^P$, $\Xid{E}{CBCE}^{P, c}$ and
$\Xid{E}{CBCH}^{P, c, \bot}_{0, 0, n_E}$, as described in
definition~\ref{def:enc-scheme}.
\end{definition}
\begin{theorem}[Security of hybrid CBC mode]
\label{thm:cbc}
Let $P\colon \keys P \times \Bin^\ell \to \Bin^\ell$ be a pseudorandom
- permutation; let $v_0 \in \Bin^\ell$ be an initialization vector; let $n_L
- \in \{\, 0, 1 \,\}$; let $c$ be a generalized counter in $\Bin^\ell$; and
+ permutation; let $V_0 \in \Bin^\ell$ be an initialization vector; let $n_L
+ \in \{ 0, 1 \}$; let $c$ be a generalized counter in $\Bin^\ell$; and
let $n_C \in \N$ be a nonnegative integer; and suppose that at most one of
$n_L$ and $n_C$ is nonzero. Then, for any $t$, $q_E \ge n$ and $\mu_E$,
\[ \InSec{lor-cpa}
- (\Xid{\E}{CBCH}^{P, c, v_0}_{n_L, 0, n_E}; t, q_E, \mu_E) \le
+ (\Xid{\E}{CBCH}^{P, c, V_0}_{n_L, 0, n_E}; t, q_E, \mu_E) \le
2 \cdot \InSec{prp}(P; t + q t_P, q) + \frac{q (q - 1)}{2^\ell - q}
\]
where $q = n_L + n_E + \mu_E/\ell$ and $t_P$ is some small constant.
\frac{q' (q' - 1)}{2^\ell - q'}
\\
\tabpause{and}
- \InSec{lor-cpa}(\Xid{\E}{CBCL}^{P, v_0}; t, 1, \mu_E)
+ \InSec{lor-cpa}(\Xid{\E}{CBCL}^{P, V_0}; t, 1, \mu_E)
& \le 2 \cdot \InSec{prp}(P; t + q t_P, q) +
\frac{q (q - 1)}{2^\ell - q}
\end{eqnarray*}
$2^\ell - q \approx 2^\ell$, and for larger $q$, the term $q (q - 1)/2^\ell
> 1$ anyway, so all security is lost (according to the above result).
Compared to \cite[theorem~17]{Bellare:2000:CST}, we gain the tiny extra
- term in the denominator, but lose the PRP-as-a-PRF term $q^2
- 2^{-\ell-1}$.\footnote{%
+ term in the denominator, but lose the PRP-as-a-PRF term
+ $q^2/2^{\ell-1}$.\footnote{%
In fact, they don't prove the stated bound of $q (3 q - 2)/2^{\ell+1}$
but instead the larger $q (2 q - 1)/2^\ell$. The error is in the
application of their proposition~8: the PRF-insecurity term is doubled,
\label{fig:cbc-steal}
\end{figure}
-Encrypting messages shorter than the block involves `IV stealing', which is a
-grotty hack but works fine if IVs are random; if the IVs are encrypted
+Encrypting messages shorter than the block involves `IV stealing' -- using
+the IV instead of the ciphertext from the last full-length block -- which is
+a grotty hack but works fine if IVs are random; if the IVs are encrypted
counters then there's nothing (modifiable) to steal from.
We formally present a description of a randomized CBC stealing mode.
to prove the claim that there exists a garbage-emitter $W$ such that
\[
\InSec{rog-cpa-$W$}
- (\Xid{\E}{CBCH}^{\Perm{\ell}, c, v_0}_{n_L, 0, n_E};
+ (\Xid{\E}{CBCH}^{\Perm{\ell}, c, V_0}_{n_L, 0, n_E};
t, q_E, \mu_E) \le
\frac{q (q - 1)}{2 \cdot (2^\ell - n)}.
\]
apply proposition~\ref{prop:enc-info-to-real} to obtain the required result.
Our garbage-emitter $W$ is a bit complicated. It chooses random but
-\emph{distinct} blocks for the `ciphertext'; for the IVs, it uses $v_0$ for
+\emph{distinct} blocks for the `ciphertext'; for the IVs, it uses $V_0$ for
the first message if $n_L = 1$, and otherwise it chooses random blocks
distinct from each other and the `ciphertext' blocks for the next $n_E$
messages, and just random blocks for subsequent ones. The algorithm $W$ is
\next
Garbage emitter $W(m)$: \+ \\
\IF $i \ge 2^\ell$ \THEN \ABORT; \\
- \IF $i < n_L$ \THEN $v \gets v_0$; \\
+ \IF $i < n_L$ \THEN $v \gets V_0$; \\
\ELSE \IF $i < n$ \THEN $v \gets \id{fresh}()$; \\
$i \gets i + 1$ \\
\ELSE $v \getsr \Bin^\ell$; \\
We need some notation to describe the values in the game. Let $c_i = c(i)$
be the $i$th counter value, for $0 \le i < n_E$, and let $v_i$ be the $i$th
-initialization vector, where $v_0$ is as given if $n_L = 1$, $v_i = P(c_i -
-n_L)$ if $n_L \le i < n$, and $v_i \inr \Bin^\ell$ if $n \le i < q_E$. Let
-$q' = \mu_E/\ell = q - n$ be the total number of plaintext blocks in the
-adversary's queries, let $x_i$ be the $i$th plaintext block queried, let
-$y_i$ be the $i$th ciphertext block returned, let
+initialization vector, where $v_0 = V_0$ is as given if $n_L = 1$, $v_i =
+P(c_i - n_L)$ if $n_L \le i < n$, and $v_i \inr \Bin^\ell$ if $n \le i <
+q_E$. Let $q' = \mu_E/\ell = q - n$ be the total number of plaintext blocks
+in the adversary's queries, let $x_i$ be the $i$th plaintext block queried,
+let $y_i$ be the $i$th ciphertext block returned, let
\[ w_i = \begin{cases}
v_j & if block $i$ is the first block of the $j$th query, and \\
y_{i-1} & otherwise
definition~\ref{def:enc-hybrid}.
\end{definition}
-\subsection{Security of CFB mode}
+\subsection{Sliding strings}
-%% I suspect David will want to put some negative results here, and complain
-%% about Alkassar et al.'s alleged proof. I'll press on with the positive
-%% stuff.
-%%
-%% The problems come when $t < \ell$. Then C-mode isn't necessarily secure
-%% (well, we get a similar bound with $t$ instead of $\ell$, which isn't very
-%% impressive). The L-mode needs careful selection of the initial IV.
+Consider for a moment the mode CFBL, i.e., with carry-over of IV from one
+plaintext to the next, with $t < \ell$. Then we find that some IVs are
+weak.
+
+Pretend for a moment that we're an adversary playing the LOR-CPA game using
+an ideal random function $F \inr \Func{\ell}{t}$, and that the initial IV
+$V_0 = 0^\ell$. We choose two distinct 8-bit plaintexts $l$ and $r$ as our
+first left-or-right query. With probability $2^{-t}$, the result of
+encrypting that first query is $0^t$. However, in this case, the IV for the
+\emph{next} query is $V_0 \shift{t} 0^t = 0^\ell = V_0$. If this happens,
+we have only to submit the pair $(l, l)$ as our second query. If the
+ciphertext to this second query also comes back zero, we guess that we're
+dealing with a left oracle; otherwise we guess right. If we don't get lucky
+with our first query, we just guess randomly.
+
+\begin{figure}
+ \begin{program}
+ Adversary $S^{E(\cdot, \cdot)}$: \+ \\
+ $l \gets 0^t$; $r \gets 0^{t - 1} 1$; \\
+ $y \gets E(l, r)$; \\
+ \IF $y[\ell \bitsto \ell + t] = 0^t$ \THEN \\ \ind
+ \IF $E(l, l) = y$ \THEN $b \gets 0$ \ELSE $b \gets 1$; \- \\
+ \ELSE \\ \ind
+ $b \getsr \{0, 1\}$; \- \\
+ \RETURN $b$;
+ \end{program}
+ \caption{Adversary $S$ attacking $\Xid{\E}{CFBL}^{\Func{\ell}{t}, 0^\ell}$}
+ \label{fig:adv-sliding}
+\end{figure}
+
+This attack is shown more formally as adversary~$S$ in
+figure~\ref{fig:adv-sliding}. Its resource usage is almost trivial --
+negligible computation and at most two encryption queries. However, its
+advantage is quite good:
+\[ \Adv{LOR-CPA}{\Xid{\E}{CFBL}^{\Func{\ell}{t}, 0^\ell}}(S) =
+ \frac{1}{2^t} \biggl( 1 - \frac{1}{2^t} \biggr).
+\]
+
+This attack works because $V_0[t \bitsto \ell] = V_0[0 \bitsto \ell - t]$.
+There are similar attacks for other such relationships. The following
+definition characterizes these kinds of `bad' IVs.
\begin{definition}[Sliding strings]
\label{def:slide}
For all $\ell > 0$ and $t < \ell$, the string $0^{\ell-1} 1$ does not
$t$-slide.
\end{remark}
+
+\subsection{Security of CFB mode}
+
+%% I suspect David will want to put some negative results here, and complain
+%% about Alkassar et al.'s alleged proof. I'll press on with the positive
+%% stuff.
+%%
+%% The problems come when $t < \ell$. Then C-mode isn't necessarily secure
+%% (well, we get a similar bound with $t$ instead of $\ell$, which isn't very
+%% impressive). The L-mode needs careful selection of the initial IV.
\begin{theorem}[Security of CFB mode]
\label{thm:cfb}
be as in theorem~\ref{thm:cfb}. Then for any $t_E$, $q_E$ and $\mu_E$,
\begin{eqnarray*}[rl]
\InSec{lor-cpa}(\Xid{\E}{CFB$\$$}^P; t_E, q_E, \mu_E)
- & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) +
+ \frac{q (q - 1)}{2^{\ell-1}}
\\
\InSec{lor-cpa}(\Xid{\E}{CFBE}^{P, c}; t_E, q_E, \mu_E)
& \le 2 \cdot \InSec{prp}(P; t_E + q' t_F, q') +
- \frac{q' (q' - 1)}{2^\ell}
+ \frac{q' (q' - 1)}{2^{\ell-1}}
\\
\InSec{lor-cpa}(\Xid{\E}{CFBL}^{P, V_0}; t_E, q_E, \mu_E)
- & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) +
+ \frac{q (q - 1)}{2^{\ell-1}}
\\
\tabpause{and, if $\ell \le t$,}
\InSec{lor-cpa}(\Xid{\E}{CFBC}^{P, c}; t_E, q_E, \mu_E)
- & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) + \frac{q (q - 1)}{2^\ell}
+ & \le 2 \cdot \InSec{prp}(P; t_E + q t_F, q) +
+ \frac{q (q - 1)}{2^{\ell-1}}
\end{eqnarray*}
where $q = \bigl\lfloor \bigl(\mu_E + q_E (t - 1)\bigr)/t \bigr\rfloor +
n_E$, $q' = q + q_E$, and $t_F$ is some small constant.
are a multiple of $t$ bits in length; obviously all of the oracle responses
for a block-respecting adversary are also a multiple of $t$ bits in length.
\begin{claim*}
- If $A'$ be a block-respecting adversary querying a total of $\mu_E$ bits of
+ Let $A'$ be a block-respecting adversary querying a total of $\mu_E$ bits of
plaintext queries; then
\[ \Adv{}{}(A') \le \frac{q (q - 1)}{2^{\ell+1}} \]
where $q = \mu_E/t$.
%%%--------------------------------------------------------------------------
-\section{Ackonowledgements}
+\section{Acknowledgements}
Thanks to Clive Jones for his suggestions on notation, and his help in
structuring the proofs.
~mdw / doc / modes / commitdiff