From 16ad8466d3b3ad677cfc9371201a9eee81f79148 Mon Sep 17 00:00:00 2001 From: Mark Wooding Date: Sat, 19 Aug 2006 08:37:32 +0100 Subject: [PATCH] Various improvements. A small selection: * Fix errors in abstract noticed by Vicky. * Fix `ackonowledgements', noticed by Nicko. * Improve notation in prop:rog-and-lor * Remove redundant IV-prediction algorithm from mode definition. * Fix statement of prop:enc-info-to-real. * Expand and fix proof of prop:enc-hybrid. * Fix IV notation in CBC proof (v_0 -> V_0). * Expand note on IV-stealing. * Expand and explain material on sliding strings. --- modes.tex | 201 ++++++++++++++++++++++++++++++++++++++++---------------------- 1 file changed, 129 insertions(+), 72 deletions(-) diff --git a/modes.tex b/modes.tex index 69c8329..2f986ea 100644 --- a/modes.tex +++ b/modes.tex @@ -81,6 +81,7 @@ } \fi \def\fixme{\marginpar{FIXME}} +\def\hex#1{\texttt{#1}_{x}} \newslowboxenv{cgraph}{\par$$}{\begin{graph}}{\end{graph}}{$$\par} \newslowboxenv{vgraph} @@ -105,11 +106,11 @@ 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 @@ -510,6 +511,8 @@ adversary's plaintext selection. 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, @@ -520,14 +523,19 @@ notions of security. \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 @@ -552,16 +560,16 @@ notions of security. \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)}$: \+ \\ @@ -572,15 +580,14 @@ notions of security. $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} @@ -722,9 +729,6 @@ Not all of these methods are secure for all of the modes we consider. 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 @@ -743,10 +747,7 @@ Not all of these methods are secure for all of the modes we consider. \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} @@ -877,8 +878,8 @@ The following simple and standard result will be very useful in our proofs. 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) . @@ -887,8 +888,8 @@ The following simple and standard result will be very useful in our proofs. 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) . @@ -1007,15 +1008,23 @@ definition~\ref{def:enc-scheme}. \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} %%%-------------------------------------------------------------------------- @@ -1102,7 +1111,7 @@ See figure~\ref{fig:cbc} for a diagram of CBC encryption. \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} @@ -1114,12 +1123,12 @@ We now present our main theorem on CBC mode. \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. @@ -1142,7 +1151,7 @@ simple corollaries. \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*} @@ -1158,8 +1167,8 @@ simple corollaries. $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, @@ -1301,8 +1310,9 @@ figure~\ref{fig:cbc-steal}. \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. @@ -1392,7 +1402,7 @@ simplify notation slightly, we shall write $n = n_L + n_E$. Our main goal is 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)}. \] @@ -1407,7 +1417,7 @@ and, noting that there are precisely $q = \mu_E/\ell$ PRP-applications, we 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 @@ -1426,7 +1436,7 @@ shown in figure~\ref{fig:cbc-garbage}. \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$; \\ @@ -1461,11 +1471,11 @@ game -- are distinct, the two games look identical. 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 @@ -1689,15 +1699,49 @@ ability to decrypt. 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} @@ -1709,6 +1753,16 @@ ability to decrypt. 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} @@ -1767,18 +1821,21 @@ section~\ref{sec:cfb-proof}. 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. @@ -1846,7 +1903,7 @@ that an adversary is \emph{block-respecting} if all of its plaintext queries 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$. @@ -2242,7 +2299,7 @@ wait, or I'll have to drop this bit. %%%-------------------------------------------------------------------------- -\section{Ackonowledgements} +\section{Acknowledgements} Thanks to Clive Jones for his suggestions on notation, and his help in structuring the proofs. -- 2.11.0