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.

diff --git a/modes.tex b/modes.tex
index 69c8329..2f986ea 100644 (file)
--- a/modes.tex
+++ b/modes.tex
@@ -81,6 +81,7 @@
   }
 \fi
 \def\fixme{\marginpar{FIXME}}
   }
 \fi
 \def\fixme{\marginpar{FIXME}}

+\def\hex#1{\texttt{#1}_{x}}

 
 \newslowboxenv{cgraph}{\par$$}{\begin{graph}}{\end{graph}}{$$\par}
 \newslowboxenv{vgraph}
 
 \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
   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
 \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.
 
 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,
 \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
          \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}
        \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
   \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$
     \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}
     \begin{program}

-      Garbage emitter $W(n)$: \+ \\
+      Garbage emitter $\Wror(n)$: \+ \\

         \IF $K_W = \bot$ \THEN $K_W \gets G()$; \\
         $x \getsr \Bin^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}
     \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)}$: \+ \\
     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}
         $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}
   \end{enumerate}
 \end{proof}

-
+\endgroup

 
 
 \subsection{Message authentication}
 
 
 \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)$. 
     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
   \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 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}
 
   \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
     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) .
     \[ \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
     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) .
     \[ \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}
 \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}
 
 %%%--------------------------------------------------------------------------
 \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
       \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}
   $\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
 \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}
   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.
      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}
           \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*}
     & \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
   $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,
     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}
 
   \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.
 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$}
 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)}.
 \]
        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
 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
 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; \\
     \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$; \\
       \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
 
 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
 \[ 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}
 
   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}
 
 \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}
   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}
 
 \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)
   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') +
     \\
     \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)
     \\
     \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)
     \\
   \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.
   \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*}
 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$.
   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.
 
 Thanks to Clive Jones for his suggestions on notation, and his help in
 structuring the proofs.