8
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Another relevant reference is this additional paper of Rogaway's, sections 4.6 and 4.7, pp. 36-39, where he directly addresses the NIST SP 800-38A recommendation you cite. But this may indeed hinge on what degree of control we assume the adversary to have over the nonce. Rogaway's formulation does assume a "nonce-respecting" adversary that adaptively chooses the nonces but does not repeat them. $\endgroup$ – Luis Casillas May 10 '17 at 20:31
  • $\begingroup$ @LuisCasillas: Indeed, the note at the end of page 38 looks particularly relevant here. $\endgroup$ – Ilmari Karonen May 10 '17 at 23:12
  • 3
    $\begingroup$ Not really an answer to your question, but some info. The scenario you are describing, is precisely what recent versions of TLS and DTLS are doing when they are using CBC mode. That scheme it called CBC wit implicit IV and was originally invented to enable CBC usage with DTLS. $\endgroup$ – mat May 11 '17 at 9:08
  • 1
    $\begingroup$ @mat: citation? SSL3 and TLS1.0 in 1999 (which I don't call recent) use what is actually implicit IV but don't use that word or phrase for it; TLS1.1 in 2006 changes to explicit IV and allows encrypting a random block (not a counter block as in this Q) as one method, and TLS1.2 in 2008 simply says explicit random. Both versions of DTLS, actually based on TLS1.1 and 1.2, use explicit IV with no mention in 4347 and only a mention that TLS1.0 was implicit in 6347. $\endgroup$ – dave_thompson_085 Mar 13 at 7:58
  • $\begingroup$ @dave_thompson_085: You are correct, of course. I messed up explicit and implicit in my comment. Please interchange them. $\endgroup$ – mat Mar 13 at 11:07
3
$\begingroup$
  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.

  1. 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.)

  1. 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).

  1. 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$.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.