8
$\begingroup$

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.

$\endgroup$

1 Answer 1

12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ How do you conclude that $E_k(P_i \oplus C_{i-1}) = E_k(P_j \oplus C_{j-1}) \Rightarrow P_i \oplus P_j = C_{i-1} \oplus C_{j-1}$? $\endgroup$ Oct 23, 2015 at 13:07
  • $\begingroup$ @EmilLundberg: because the block cipher $E_k$ is invertable; $E_k(a) = E_k(b)$ implies that $a=b$. Once you've seen that $E_k(P_i \oplus C_{i-1}) = E_k(P_j \oplus C_{j-1})$ implies $P_i \oplus C_{i-1} = P_j \oplus C_{j-1}$, rearranging terms gives you the result $\endgroup$
    – poncho
    Oct 23, 2015 at 13:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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