Why does error propagation in CBC mode encryption affect two blocks?

Question

From Wikipedia:

Error propagation

It was common to discuss the "error propagation" properties as a selection criterion for a mode of operation. It might be observed, for example, that a one-block error in the transmitted ciphertext would result in a one-block error in the reconstructed plaintext for ECB mode encryption, while in CBC mode such an error would affect two blocks.

I read this similar post before. And I can understand that in CBC decryption, only two blocks are affected due to error propagation (error in 1 block).

But, for the same case in CBC encryption, why are still only two blocks affected? It looks like all the following blocks will be affected.

Answer 1

Encryption process in CBC mode is performed as \begin{align} C_1 &= Enc_k(P_1 \oplus IV)\\ C_i &= Enc_k(P_i \oplus C_{i-1}),\;\; 1 < i \leq nb, \end{align} where $nb$ is the number of blocks.

CBC is designed for chaining, therefore while encryption, if there is one block error at position $i$, it will affect the rest of ciphertext. This also can be seen from below if write the equation of encryption of $j$-th block.

$$C_j = Enc_k(P_j \oplus Enc_k(P_{j-1} \oplus \cdots Enc_k(P_1 \oplus IV)\cdots)).$$ If $i < j$ then the $j$-th plaintext block will be affected.

However, while decryption of the ciphertext, that is encryption of the plaintext that contains the errored block, you will get only one block with error, the errored plaintext block. Or simply, you will get what you encrypted if there is no error/corruption on the ciphertext blocks.

Note: if there is an error on one of the ciphertext blocks, it can affect one or two plaintext blocks depending on the index of the ciphertext block. One block if the last ciphertext block is corrupted, two blocks otherwise, see bit flipping attack to visiualize. The question is on the error on the plaintext.

Answer 2

Consider a four-block message $P_1 \mathbin\| P_2 \mathbin\| P_3 \mathbin\| P_4$. The corresponding ciphertext under initialization vector $\mathit{IV}$ is $C_1 \mathbin\| C_2 \mathbin\| C_3 \mathbin\| C_4$, where:

\begin{equation*}\newcommand{\diff}[1]{\color{red}{#1}} \begin{matrix} &&P_1 &&\diff{P_2} &&P_3 &&P_4 \\ &&\downarrow&&\diff\downarrow&&\downarrow&&\downarrow \\ \mathit{IV}&\rightarrow& E_k(\mathit{IV} \oplus P_1)&\rightarrow& E_k(C_1 \oplus \diff{P_2})&\diff\rightarrow& E_k(\diff{C_2} \oplus P_3)&\diff\rightarrow& E_k(\diff{C_3} \oplus P_3) \\ &&\| &&\diff\| &&\diff\| &&\diff\| \\ &&C_1&&\diff{C_2}&&\diff{C_3}&&\diff{C_4} \end{matrix} % It is tempting to use the commutative diagram below, but % AMScd doesn't support diagonal arrows as we need for the % decryption diagram. So, let's keep the style consistent % and use two janky diagrams instead of one OK one and one % janky one. Also it's gotten kind of wide at this point, % and AMScd can't obviously color the arrows. %\require{AMScd} \\ %\begin{CD} %@. P_1 @. \diff{P_2} @. P_3 @. P_4 \\ %@. @VVV @VVV @VVV @VVV \\ %\mathit{IV} @>>> E_k(\mathit{IV} \oplus P_1) % @>>> E_k(C_1 \oplus \diff{P_2}) % @>>> E_k(C_2 \oplus \diff{P_3}) % @>>> E_k(C_3 \oplus \diff{P_4}) \\ %@. @| @| @| @| \\ %@. C_1 @. \diff{C_2} @. \diff{C_3} @. \diff{C_4} %\end{CD} \end{equation*}

Note that every block of ciphertext depends on every prior block of plaintext, because $C_i = E_k(C_{i-1} \oplus P_i)$ recursively, where $C_0 = \mathit{IV}$, so every block of plaintext affects the corresponding block of ciphertext and all subsequent ones. Consequently, if you change, say, $P_2$, then $C_2$ as well as $C_3$ and $C_4$ (and $C_5$ etc. for longer messages) will change, but not $P_1$. This is why the initialization vector must be chosen independently—and unpredictably!—in each message in order to prevent eavesdroppers from breaking confidentiality; otherwise, for example, the eavesdropper can learn when two messages start with the same prefix or not.

When reversed, the decryption of the ciphertext $C_1 \mathbin\| C_2 \mathbin\| C_3$ under initialization vector $\mathit{IV}$ looks like:

\begin{equation*}\newcommand{\diff}[1]{\color{red}{#1}} \begin{matrix} &&C_1 & &\diff{C_2} & &C_3 & &C_4 \\ &&\downarrow&\searrow&\diff\downarrow&\diff\searrow&\downarrow&\searrow&\downarrow \\ \mathit{IV}&\rightarrow& \mathit{IV} \oplus D_k(C_1)&& C_1 \oplus D_k(\diff{C_2})&& \diff{C_2} \oplus D_k(C_3)&& C_3 \oplus D_k(C_4) \\ &&\| &&\diff\| &&\diff\| &&\| \\ &&P_1&&\diff{P_2}&&\diff{P_3}&&P_4 \end{matrix} \end{equation*}

Note that each plaintext depends only on two blocks of ciphertext: $P_i = C_{i-1} \oplus D_k(C_i)$, where $C_0 = \mathit{IV}$, so every block of ciphertext $C_i$ affects at most two blocks of plaintext, $P_i$ and $P_{i+1} = C_i \oplus D_k(C_{i+1})$ (if there is a $P_{i+1}$). Consequently, if you change, say, $C_2$, then only $P_2$ and $P_3$ will change, but not $P_1$, $P_4$, or any other blocks.

---

Note: Error propagation of CBC mode is not relevant to any modern cryptography. The concept is a relic of the dark ages of cryptography from the last millennium before we understood the importance of authenticated ciphers like crypto_secretbox_xsalsa20poly1305 and AES-GCM, or deterministic authenticated ciphers. Textbooks that discuss it, other than to point out how silly it is in modern cryptography, are obsolete.

The first diagram shows that CBC cannot provide deterministic cipher security, because not every block of plaintext affects every block of ciphertext, so attackers learn even more information than when a message is repeated. And, of course, CBC can't provide authentication—that is, can't prevent forgery by an active adversary—because every bit string of an appropriate length is a valid CBC ciphertext, so there's no way to distinguish legitimate ones from forged ones a priori.

More generally, you should forget modes of operation and focus on security contracts.