X-Git-Url: https://git.distorted.org.uk/~mdw/doc/modes/blobdiff_plain/b98a7b3e9d73d581675b036b53acbebb330eec82..16ad8466d3b3ad677cfc9371201a9eee81f79148:/modes.tex

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.
