1
$\begingroup$

I am new to cryptography. My professor's slides say that "Disadvantage: altered ciphertext only influences two blocks" for the CBC. However, since we xor the ciphertext from the previous block and the present plaintext, before encryption; it seems to me like if I alter a ciphertext block, every ciphertext block coming afterwards will change. I do not understand why would this chain reaction only influence two blocks.

$\endgroup$
  • 2
    $\begingroup$ Note that we don't care about error propagation that much anymore. It is generally assumed that you either use authenticated encryption or you don't. Modern crypto should heavily prefer cipher modes such as GCM that provide message authentication (i.e. they will not decrypt unless the authentication tag is correct). Error propagation is only interesting for historical purposes, to understand cipher modes in general and possibly a few niche problems. To speak about a disadvantage for CBC is thoroughly outdated. $\endgroup$ – Maarten Bodewes Sep 19 '18 at 10:59
3
$\begingroup$

One way is simply to look at the usual illustration of CBC decryption and follow the arrows. Here is the figure from Wikipedia:

CBC decryption

Imagine you alter the first block of ciphertext. Follow the arrows to see what will be altered in the plaintext: only two blocks.

We can also do this with math formulas: CBC mode encryption can be described as follow, where $ P_n $ and $ C_n $ are the $n$th plaintext and ciphertext blocks, respectively:

$$ C_n = Enc(P_n \oplus C_{n-1}) $$

(With the IV playing the role of $ C_0 $)

Thus

$$ P_n = Dec(C_n) \oplus C_{n-1} $$

As a result, if you alter $ C_n $ it is clear that $ P_n $ and $ P_{n+1} $ will be affected but not $ P_{n+2} $ and the next blocks.

If you want to see this in practice, you may want to do the cryptopals challenges up to challenge 17.

$\endgroup$
2
$\begingroup$

You do know how CBC mode decryption works, right? So let's say you want to decrypt the $n$-th plaintext block in the message. Which ciphertext blocks do you need to know in order to be able to do that? And what happens if one of those ciphertext blocks is changed, say by flipping one of its bits? What happens if any other ciphertext block is changed?

I suggest pausing at this point, looking at your textbook (or course slides or even just the Wikipedia page linked above) and trying to figure it out yourself before reading further. It's a useful educational exercise.


OK, did you figure it out? If yes, let's see if my way of looking at it matches yours. If not, just read on anyway.

In CBC encryption, each ciphertext block is calculated based on the corresponding plaintext block and the previous ciphertext block (or the IV, for the first block). This means that if some plaintext block is changed, that change will (naturally enough) cause the corresponding ciphertext block to change, which will indeed then also affect the next ciphertext block after it, and so on all the way to the end of the message.

In CBC decryption, however, each plaintext block is calculated based on the corresponding ciphertext block and, still, the previous ciphertext block. Not the previous plaintext block, but just two adjacent ciphertext blocks. So changing the $n$-th ciphertext block will cause then $n$-th and the $n+1$ -th plaintext blocks to change, but the change will not propagate any further, since none of the other plaintext blocks depend on any of those changed blocks.

One consequence of this asymmetry is that CBC decryption can easily be done in parallel, whereas CBC encryption is necessarily a serial process that cannot be significantly parallelized.

Another consequence is that modifying a CBC ciphertext block will only change two of the plaintext blocks, and leave all others unchanged. Furthermore, since the only dependency between the $n$-th ciphertext block and the $n+1$ -th plaintext block is via a simple unkeyed XOR operation, changing a ciphertext block by flipping some bits will change the following plaintext block in a way that is easily predictable even by an attacker who does not know the key. Thus, CBC mode encryption is sufficiently malleable to allow practical attacks if the ciphertext can be modified by the attacker.


For visualization, these diagrams from Wikipedia may be useful:

CBC mode encryption diagram.

CBC mode decryption diagram.

The arrows in the diagrams above show how the input data (and thus also any changes to it) propagate through the CBC encryption and decryption processes to the outputs.

If you look at a particular plaintext block in the first (encryption) diagram and follow the arrows from it, you can see that they connect to all following ciphertext blocks.

However, if you start from a particular ciphertext block in the second (decryption) diagram, you'll find that the arrows from it only lead to two plaintext blocks, and no further. Also, only one of the paths from the ciphertext blocks to the two plaintext blocks passes through the block cipher; the other does not, which means that the way any changes propagate from the ciphertext to the plaintext along that path does not depend on the block cipher key in any way.

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