# Security proofs for CBC mode

I'm looking for different approaches to proofs for the security of CBC mode encryption. What are the best sources of information about this subject?

-
I believe that Katz and Lindell's Introduction has a formal proof contained therein, or at least contains a reference to one. Sadly, I don't have my copy with me at the moment. I did find these lecture notes which contain a rough sketch of a proof, though. Here is another set of lecture notes that also proves CBC mode is IND-CPA secure, but I haven't verified their argument myself. – Reid Nov 6 '13 at 19:55
Katz and Lindell refer to the 1997 paper by Bellare et al. – Dmitry Khovratovich Nov 6 '13 at 22:35

The classic proof is contained in http://www.cs.ucdavis.edu/~rogaway/papers/sym-enc.pdf (1997), but it is not quite easy.

-

Here's a nice paper I came across a while ago: Wooding, Mark (2008), "New proofs for old modes", Cryptology ePrint Archive, report 2008/121:

"Abstract: We study the standard block cipher modes of operation: CBC, CFB, and OFB and analyse their security. We don't look at ECB other than briefly to note its insecurity, and we have no new results on counter mode. Our results improve over those previously published in that (a) our bounds are better, (b) our proofs are shorter and easier, (c) the proofs correct 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 pay attention to different methods for selecting initialization vectors for the block cipher modes, and prove security for a number of different selection policies. In particular, we introduce the concept of a `generalized counter', and prove 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 three modes. "

-
Thank you very much. – Dingo13 Nov 9 '13 at 9:36

Here is an example of a proof. This proves why CBC mode needs an IV that is random: (fyi many people think a nonce will suffice, but it won't, it needs to be random)

Our definition of a probabilistically secure encryption scheme:

Imagine two oracles taking two inputs: a plaintext $P$ and initialization vector $IV$. The 1st oracle $Enc_{k}(P, IV)$ performs CBC encryption and outputs a ciphertext with the same length of $P$. The second oracle $Rand(P, IV)$ returns a random string of bit with the same length of $P$.

Under our notion of security, it should be indistinguishable in polynomial time with respect to the length $n$ of the encryption key $k$ whether a given output is produced from $Enc_{k}(P, IV)$ or $Rand(P, IV)$.

Now, an adversary $A$ has access to an oracle $O(P, IV)$ fulfilled either by $Enc_k$ or $Rand$. But $A$ is unaware of which. Adversary $A$ must choose $(P,IV)$ values to input into $O$ and decide based on the output whether the oracle is of type $Enc_k$ or $Rand$. Thus, the scheme is probabilistically secure in polynomial time if an adversary has an advantage of correctly guessing the oracle type defined as follows, where $\epsilon^n$ is negligible:

$Adv = |Pr[O^{Enc} \rightarrow 1] - Pr[O^{Rand} \rightarrow 1]|= \epsilon^{n}$

In other words, if the encryption scheme is probabilistically secure in polynomial time, then the adversary should, with negligible probability, determine whether an oracle output is random bits or a true ciphertext within polynomial time in terms of $n$.

Proof of why this isn't secure with non-random IV's (e.g. nonces):

Adversary $A$ does guesses the oracle type by querying $O$ with two different $(P,IV)$ pairs. If the corresponding outputs are equal, then the adversary outputs $1$, signifying the oracle $O$ is of type $Enc_k$. Otherwise $A$ outputs $0$, signifying the oracle is of type $Rand$.

On the first query, $A$ chooses $P_1^n = IV_1^n = 1^n$ (i.e. an $n$ series of 1 bits for $(P_1,IV_1)$). If the oracle is $Enc_k$, then it will first perform $P_1 \oplus IV_1$ to produce an $n$ bit string of 0's which will then be encrypted to some ciphertext $C_1$. On the second query, $A$ chooses $P_2^n = IV_2^n = 0^n$ (i.e. an $n$ series of 0 bits for $(P_2,IV_2)$). Again, the $Enc_k$ oracle will perform $P_2 \oplus IV_2$ to produce an $n$ bit string of 0's which will then be encrypted to some ciphertext $C_2$. Thus, $C_1 = C_2$ with 100% probability if the oracle is of type $Enc_k$

However, if the oracle is $Rand$, regardless of input, the output of both queries will be random strings $R_1, R_2$ such that:

$Pr[R_1^n=R_2^n] = (1/2)^n = \epsilon^n$

Thus, if $C_1 = C_2$ then $A$ outputs 1, else 0. Thus, under this game, $A$ knows with $1 - \epsilon^n$ probability whether oracle $O$ is $Enc_k$ or $Rand$.

Thus, the encryption scheme is distinguishable in polynomial time with a nonce as the $IV$. And thus, a random $IV$ must be used for encryption.

-

If you can go through these lecture notes by Goldwaser and Bellare you will get the point

-