# Importance of block size in CBC mode

Why is it necessary to use a sufficiently long block size when implementing a CBC block cipher with a truly random initialization vector? In ECB mode it's easy to get information about the message if you can encrypt arbitrary plaintexts and look for matching blocks, but I'm not sure how this applies to CBC mode.

-

CBC mode encryption is defined as:

$C_i = E_k(P_i\oplus C_{i-1})$

(with $P_i$ being the $i$th plaintext block, and $C_{i-1}, C_i$ being the ciphertext blocks.

What might happen if we have a lot of ciphertext encrypted with the same key is if two ciphertexts happen to be the same, that is:

$C_i = C_j$

If we see that, we can then immediately deduce that:

$E_k(P_i \oplus C_{i-1}) = E_k(P_j \oplus C_{j-1})$

or

$P_i \oplus P_j = C_{i-1} \oplus C_{j-1}$

Now, the attacker knows the values of $C_{i-1}, C_{j-1}$, and hence the attacker can then deduce the relationship between those two plaintext blocks. If he happens to know one of the plaintext blocks, he can immediately deduce the other.

Is this information leakage fatal? Well, maybe, maybe not, the attacker has no control over what data blocks are leaked, even with chosen plaintext (because he can't predict $C_{i-1}$ before the encryption process). However it's more leakage than we want.

And, how likely is this? Well, that's where we come to block size. $C_{i-1}$ is effectively random and uncorrelated to $P_i$, and so $P_i \oplus C_{i-1}$ is also effectively random; if the block size is $n$ bits, this is a random value between $0$ and $2^{n}-1$; by the birthday paradox, we would expect a collision after about $2^{n/2}$ block encryptions.

That is the point in not using too small of a block size; if we were to take $n=32$ bits, we would expect a collision (and hence some leakage) after about $2^{16}$ blocks; since we generally want to encrypt more than that with a single key, that's not enough. For $n=64$, we would expect a collision after about $2^{32}$ blocks; that's getting better, however by today's standards, that's not that much data (and there is a chance of leakage with less data). For $n=128$, we probably won't get a leakage until we get close to $2^{64}$ blocks; we'll never encrypt that much with a single key.

-