Is CBC mode with a fixed IV secure, if a counter is prepended to the plaintext?

Question

In this answer to an earlier, related question I noted that encrypting a nonce, such as a sequential counter, using the same block cipher and key as used for the message encryption itself is one of the recommended ways described in NIST SP 800-38A, Appendix C, of generating an unpredictable IV for CBC mode encryption.

I further noted that this is, in fact, mathematically equivalent to using an all-zero IV and simply prepending the nonce (padded to a full cipher block) to the plaintext before applying CBC mode encryption.

However, in the comments to another answer, it was noted that this construction is trivially CPA-insecure (as noted e.g. in section 4 of this paper by Rogaway) if the nonce may be chosen by the attacker. (Of course, it could be argued that, if your nonces may be controlled by an attacker, you really should be using a fully nonce-misuse resistant mode like SIV instead of CBC anyway.)

That said, let's take this opportunity to hopefully settle this issue once and for all:

1. Assuming that the nonce values are unique and generated according to some fixed public counter sequence that is not under the attacker's control, is the encryption scheme described above (i.e. pad the nonce to a full cipher block, prepend it to the plaintext, and encrypt the result using CBC mode with an all-zero IV) actually IND-CPA secure?

2. If so, is there a published proof of this? If not, is there a known attack under the IND-CPA model that doesn't assume the attacker can choose the nonces?

3. How does the quantitative security (e.g. attacker's advantage as a function of the number of encryption oracle queries) compare to standard CBC mode with random IVs? AFAICT, both are basically only secure up to the birthday bound, but a more detailed analysis could be useful.

4. As a bonus, what if the nonce is padded to some fixed length that is less than a full cipher block? Is the resulting scheme still IND-CPA secure (assuming that the nonce doesn't overflow, of course) and if so, how does this affect the number of messages that can be safely encrypted?

Answer 1

1. Assuming that the nonce values are unique and generated according to some fixed public counter sequence that is not under the attacker's control, is the encryption scheme described above (i.e. pad the nonce to a full cipher block, prepend it to the plaintext, and encrypt the result using CBC mode with an all-zero IV) actually IND-CPA secure?

Yes, nonce-based CBC has reasonable IND-CPA security bounds just like traditional CBC.

2. If so, is there a published proof of this? If not, is there a known attack under the IND-CPA model that doesn't assume the attacker can choose the nonces?

Yes: there is a published proof just below. (I leave it to the asker to specify restrictions on venue that would exclude pseudonymous feathery bloviators on the internet.)

3. How does the quantitative security (e.g. attacker's advantage as a function of the number of encryption oracle queries) compare to standard CBC mode with random IVs? AFAICT, both are basically only secure up to the birthday bound, but a more detailed analysis could be useful.

Quantitatively, the security drops with the number of queries times the number of blocks, because there is a potential for a ciphertext-chaining block to coincide with a nonce. But the security of CBC itself already drops with the square of the total number of blocks, which is larger than that already (unless every message is a single block long).

4. As a bonus, what if the nonce is padded to some fixed length that is less than a full cipher block? Is the resulting scheme still IND-CPA secure (assuming that the nonce doesn't overflow, of course) and if so, how does this affect the number of messages that can be safely encrypted?

How you format the nonce is inconsequential as long as nonces are distinct. The crux is that in case (2) below, $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ is uniform random, so it has equal probability of coinciding with any fixed nonce. Although stated in terms of the nonce $n_0$, the proof really assumes only that the first block fed to the cipher is unique.

---

Details. An attack $A$ on a cipher is random algorithm that submits a sequence $m_0, m_1, \dots, m_{q-1}$ of $q$ queries (possibly adaptively), for messages up to $\ell$ blocks long, to an encryption oracle; for the last two queries the oracle returns the encryption of only one of them, determined by a fair coin toss, and the attack wins if it guesses correctly which face the coin landed on. The IND-CPA advantage of an attack $A$ is defined to be $$\operatorname{Adv}^{\operatorname{IND-CPA}}_{\mathcal O}(A) := |\Pr[A(\mathcal O)] - 1/2|,$$ where $\Pr[A(\mathcal O)]$ is the success probability of $A$ on the oracle $\mathcal O$. (The oracle is assumed to know how to count.)

Fix a block size $b$. Each message $m_n = m_{n,0} \mathbin\| m_{n,1} \mathbin\| \cdots$ will be an integral number of $b$-bit blocks. For a function $F$ and a block $\mathit{iv}$, define $$\operatorname{CBC}_F(\mathit{iv}, m_n) := F(\mathit{iv} \oplus m_{n,0}) \mathbin\| F(F(\mathit{iv} \oplus m_{n,0}) \oplus m_{n,1}) \mathbin\| \cdots.$$

• In traditional CBC mode for a random function $F\colon \{0,1\}^b \to \{0,1\}^b$ of blocks, to answer a query for the $n^{\mathit{th}}$ message $m_n$, the encryption oracle samples $\mathit{iv}_n$ uniformly at random and reveals $$\operatorname{TCBC}_F(m_n) := \mathit{iv}_n \mathbin\| \operatorname{CBC}_F(\mathit{iv}_n, m_n).$$ The success probability $\Pr[A(\operatorname{TCBC}_F)]$ of any attack $A$ against traditional CBC is bounded by the standard CBC theorem: for uniform random $f$, $$\Pr[A(\operatorname{TCBC}_f)] \leq 1/2 + O(q^2 \ell^2/2^b).$$ To allow decryption one usually instantiates traditional CBC with $F = E_k$ for a block cipher $E$ and a uniform random key $k$; the standard permutation-for-function substitution lemma just adds $O(q^2/2^b)$ to the probability.

• Define the following alternative scheme, where $G\colon \{0,1\}^b \to \{0,1\}^b$ is another random function of blocks: To answer a query for the $n^{\mathit{th}}$ message $m_n$, the oracle reveals $$\operatorname{NCBC}_{F,G}(m_n) := G(n) \mathbin\| \operatorname{CBC}_F(G(n), m_n).$$ If $F = G$, call it $\operatorname{NCBC}_F$. Consider the following cases:

  1. $G = g$ is a uniform random function $g$ independent of $F$. Obviously, this is identical to traditional CBC mode for any $F$, because each output $g(n)$ is independent uniform random for distinct $n$ just like $\mathit{iv}_n$, so $$\Pr[A(\operatorname{NCBC}_{F,g})] = \Pr[A(\operatorname{TCBC}_F)].$$
  2. $F$ and $G$ are the same uniform random function $f$. This case is distinguishable from the preceding one only in the event that $n_0$ coincides with $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ for some $n_0$, $n_1$, $i$ among the messages submitted to the oracle, which happens with probability bounded by $O(q^2 \ell/2^b)$ where $\ell$ is the mean query length. Thus, if $R$ is the event of this coincidence, \begin{align*} \Pr[A(\operatorname{NCBC}_f)] &= \Pr[A(\operatorname{NCBC}_f) \mathrel| R] \Pr[R] \\ &\quad + \Pr[A(\operatorname{NCBC}_f) \mathrel| \lnot R] \Pr[\lnot R] \\ &\leq \Pr[R] + \Pr[A(\operatorname{NCBC}_f) \mathrel| \lnot R] \\ &= O(q^2 \ell/2^b) + \Pr[A(\operatorname{NCBC}_{f,g})]. \end{align*} (Exercise for reader: Write down a concrete formula for a bound on $\Pr[R]$. To make it simpler, replace $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ by, say, $m_{n_1,i+1} \oplus f(n_1\mathbin\|i)$: ensuring distinct inputs to $f$ can only raise the probability that one of the chaining values coincides with one of the nonces, and every output of $f$ on distinct inputs is independent uniform random.)
  3. $F = G = \pi$ for a uniform random permutation $\pi$. By a standard theorem about substituting uniform random permutations for uniform random functions, for any algorithm $A$ making $q$ queries, \begin{align*} \Pr[A(\operatorname{NCBC}_\pi)] &\leq \Pr[A(\operatorname{NCBC}_f)] + q(q - 1)/2^{b + 1} \\ &= \Pr[A(\operatorname{NCBC}_f)] + O(q^2/2^b). \end{align*} (Alternatively, one can use the somewhat better but less standard bound $\Pr[A(\operatorname{NCBC}_\pi)] \leq \delta \cdot \Pr[A(\operatorname{NCBC}_f)]$ where $\delta = (1 - (q - 1)/2^b)^{-q/2}$.)
  4. $F = G = E_k$ for a uniform random key $k$ and a block cipher $E$. The distance between $\Pr[A(\operatorname{NCBC}_{E_k})]$ and $\Pr[A(\operatorname{NCBC}_\pi)]$ is the PRP advantage $\operatorname{Adv}^{\operatorname{PRP}}_E(A')$ of $A'(\phi) := A(\operatorname{NCBC}_\phi)$ to distinguish the block cipher $E$ from a uniform random permutation; presumably $E$ was chosen by years of cryptanalysis to put a confident bound on this distance for all reasonable numbers $q \ell$ of block cipher evaluations.

Thus, the success probability of an attack on nonce-based CBC making $q$ queries of mean length $\ell$ is bounded by:

\begin{align*} \Pr[A(\operatorname{NCBC}_{E_k})] &\leq \Pr[A(\operatorname{NCBC}_\pi)] + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\ &\leq \Pr[A(\operatorname{NCBC}_f)] + O(q^2/2^b) + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\ &\leq \Pr[A(\operatorname{NCBC}_{f,g})] + O(q^2 \ell/2^b) + O(q^2/2^b) + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\ &= \Pr[A(\operatorname{TCBC}_f)] + O(q^2 \ell/2^b) + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\ &\leq 1/2 + O(q^2 \ell^2/2^b) + O(q^2 \ell/2^b) + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\ &= 1/2 + O(q^2 \ell^2/2^b) + \operatorname{Adv}^{\operatorname{PRP}}_E(A'), \end{align*}

or

\begin{equation} \operatorname{Adv}^{\operatorname{IND-CPA}}_{\operatorname{NCBC}_{E_k}} \leq O(q^2 \ell^2/2^b) + \operatorname{Adv}^{\operatorname{PRP}}_E(A'), \end{equation}

i.e. essentially the same as for traditional CBC with a block cipher $E$.

Answer 2

Hand-wavy qualitative argument using standard crypto engineering approximations:

The security contract for CBC mode of a block cipher $E_{k_0}$ is that (a) the key $k_0$ be uniform random secret and (b) the initialization vector be unpredictable in advance by an adversary. Here is an example of an approximation to a pseudorandom function of a nonce $n$ that you could use to unpredictably pick an initialization vector: $n \mapsto E_{k_1}(n)$, indexed by a uniform random secret $k_1$.

This obviously works if $k_0$ and $k_1$ are independent—but the input to the IV derivation function, namely the nonce, and the input to the block cipher, namely $P_i \oplus C_{i-1}$ for some plaintext block $P_i$ and the previous ciphertext block $C_{i-1}$, are independently distributed, with uniform distribution on $P_i \oplus C_{i-1}$, so even if $k_0 = k_1$, there is only a negligible probability that past a ciphertext $C_i = E_k(P_i \oplus C_{i-1})$ will reveal a future initialization vector $E_k(n)$ for nonce $n$.