5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ If you tamper with the plaintext, then it does affect more than 2 blocks in encryption. $\endgroup$ – forest Aug 26 at 7:25
  • $\begingroup$ The text you quoted talks about errors in transmitted ciphertext changing plaintext, so it's about decryption. Was there some other source that implied changes in the plaintext would also cause changes in only two blocks of ciphertext when encrypting? $\endgroup$ – ilkkachu Aug 27 at 12:04
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so "affect 2 blocks" is only true for decryption, not for encryption? error in encryption will affect all the following blocks? $\endgroup$ – TJCLK Aug 26 at 8:01
  • $\begingroup$ the wikipedia should change to "a one-block error in the reconstructed plaintext for ECB mode decryption (instead of encryption)", is it? $\endgroup$ – TJCLK Aug 26 at 8:03
  • $\begingroup$ Don't confuse. For encryption, the i-th and the rest are affected. They will differ from normal encryption. During the decryption, you can think that, actually, we are performing normal encryption so you will get all. But you will get what you have in the errored plaintext block. However, error in the cyphertext block can effect at most two blocks. $\endgroup$ – kelalaka Aug 26 at 8:04
  • $\begingroup$ ok, understand. $\endgroup$ – TJCLK Aug 26 at 8:05
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ so authenticated encryption is a method to check whether error happens in the ciphertext or plaintext? i read that authenticated encryption is something e.g, encrypt-then-MAC? how about error recovery? $\endgroup$ – TJCLK Aug 27 at 3:07
  • 2
    $\begingroup$ Authenticated encryption keeps your messages secret and detects forgeries (random errors in transit on a noisy channel are effectively forgery attempts by a particularly dumb forger). Error recovery is up to the higher-level protocol—drop the packet on the floor and ask the sender to retransmit, for example, or use erasure coding so loss of a single packet won't prevent the message from getting through. $\endgroup$ – Squeamish Ossifrage Aug 27 at 3:37

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.