2
$\begingroup$

In CBC mode, the XOR operation is used to combine the previous encrypted block with the current plaintext, to be used as the block to encrypt. Apart from other known disadvantages inherent to the mode itself, usage of XOR creates a collision vulnerability, where if there's a collision in the output, and the plaintext block can be known or guessed, then another plaintext block can be exposed, as noted in this answer: https://crypto.stackexchange.com/a/14325

This is due to the fact that from $E_k(P_i\oplus C_{i-1}) = E_k(P_j\oplus C_{j-1})$, it is immediately obvious that $P_i\oplus C_{i-1} = P_j\oplus C_{j-1}$, and due to the properties of XOR, we have that $P_j = P_i\oplus(C_{i-1}\oplus C_{j-1})$, therefore by XORing the ciphertexts that precede the collision and the guessed/known block, we can obtain the other plaintext block.

Of course, many other operations have that same problem (modular addition or subtraction, for example). Is there any other operation or function that can replace XOR, to make CBC mode not be vulnerable to this flaw?

Edit: To make the question clearer, I'd like to know of a reversible operation/function $\circ$ that takes $P_i$ and $C_{i-1}$ as input, and for which it's computationally infeasible to find $x$ such that $P_i\circ C_{i-1} = x\circ C_{j-1}$ when $P_i$, $C_{i-1}$ and $C_{j-1}$ are known. I guess that some cipher function $F_k(p)$ for which $k$ and $p$ are both the same width where $k = C_{i-1} || secret$ and $p = P_i$ would fit that purpose, but are there other simpler choices?

And while I'm here, is CTR mode safe against this kind of flaw?

$\endgroup$
  • 1
    $\begingroup$ It wouldn't be the same mode as CBC if you fixed it. No more than ECB would still be ECB if you fixed its flaws. (Which is the reason there exists other modes of operation, like CBC, to begin with.) $\endgroup$ – Future Security Oct 26 '18 at 16:56
  • 1
    $\begingroup$ CBC uses an initial value specifically to address this exact problem $\endgroup$ – Richie Frame Oct 27 '18 at 0:21
4
$\begingroup$

Without completely restructuring how CBC mode works, that would not appear to be possible.

Your generalized CBC mode encryption would be defined as:

$$C_i = Enc_k( P_i \circ C_{i-1} )$$

for some operator $\circ$ (which need not be commutative, or even associative).

What this means is that, during decryption, we have:

$$Dec_k(C_i) = P_i \circ C_{i-1}$$

To make decryption, that is, the recovery of $P_i$ feasible, we must have an easy way, given $A, B$, to find the solution $x$ for $A = x \circ B$.

In the problem you're asking to be infeasble, that is, $P_i\circ C_{i-1} = x\circ C_{j-1}$, if we set $A = P_i\circ C_{i-1}$ and $B = C_{j-1}$, we see that must also be an easy problem (otherwise decryption would be difficult)

$\endgroup$
  • $\begingroup$ What if $\circ$ is a cipher with $C_{i-1}$ plus a secret key part as a key? Say for example, $C_i = E_k(P_i\oplus MD5(C_{i-1}||secret))$. Decryption would still be easy, but not without knowing the secret part. $\endgroup$ – Pedro Gimeno Oct 27 '18 at 1:50
  • 2
    $\begingroup$ @PedroGimeno: if you're going to do that, why not $C_i = E_{k_1}( P_i \oplus E_{k_2}( C_{i-1} ))$ ? $\endgroup$ – poncho Oct 27 '18 at 3:02
  • $\begingroup$ I'm not "going to do that" :) it was just a random example of a cipher having $P_i$ and $C_{i-1}$ as inputs and a secret part. And yes, your method works as well. $\endgroup$ – Pedro Gimeno Oct 27 '18 at 9:02
1
$\begingroup$

Bitwise operations

$\oplus$ is one of the invertible bit functions. This enables us to remove a variable if applied again. That is the power of it.

$$ P \oplus C \oplus C = P$$

And one other important property;

XOR does NOT generate entropy, it merely preserves it. Namely one random Bitvector (a number of bits of fixed size) XORed with a nonrandom Bitvector equals a new random Bitvector1.

$\oplus$ is a natural choice. There is no other binary invertible function than $\oplus$ and $\neg\oplus$

Any other boolean function loses information, as AND and OR therefore not invertible for CBC mode.

For general case see Poncho's answer.


CTR Mode

The CTR mode uses a 64-bit nonce on the upper part and counter on the lower part of the 128-bit input value to the encryption algorithm. $$(nonce\|counter+i)$$ The nonce is randomly generated for each message. Since the counter always incremented, therefore the output stream is always different.

Let's call; $O_i = E_k(nonce\|counter+i)$

$$C_i = O_i \oplus P_i$$


If the nonce is reused for another message $P'$, then we can have a $$(O_i \oplus P_i) \oplus (O_i \oplus P'_i) = P_i \oplus P'_i,$$ Here, the attacker even do not need to know the Nonce itself. This is same as reusing the key of one-time pad and an attack on this can be performed as in How does one attack a two-time pad.


If the nonce is not reused, The streams generated by the CTR mode under the same encryption key will be different. Since the attacker cannot access the $O_i = E_k(nonce\|counter+i)$, the output of the Encryption algorithm, cannot have an equation.

$$ C_i \oplus C'_i = (O_i \oplus P_i) \oplus (O'_i \oplus P'_i)$$

With some negligible probability that we will have;

$$ C_i = C'_j \Rightarrow (O_i \oplus P'_i) = (O_j \oplus P'_j), i \neq j$$

But, this aparts from CBC mode, where we used only ciphertext to get an equation of the plaintexts. The attacker cannot access the $O_i$'s to get an equation for plaintexts.

$\endgroup$
  • $\begingroup$ Thanks for your answer. This answers my second question, but not the first. I've edited my post to clarify the first question. $\endgroup$ – Pedro Gimeno Oct 26 '18 at 17:50
  • $\begingroup$ @PedroGimeno the $\neg (a \oplus b)$ :) $\endgroup$ – kelalaka Oct 26 '18 at 19:42
  • $\begingroup$ @PedroGimeno actually I gave an answer to your first question, too, $\oplus$ is a natural choice. There is no other binary invertible function than $\oplus$ and $\neg\oplus$ $\endgroup$ – kelalaka Oct 26 '18 at 20:29
  • $\begingroup$ In my question I didn't specify it had to be a bitwise operator. In fact I mentioned modular addition/subtraction as an example candidate, which works on numbers of multiple bits as a whole. For example, a trivial variant of CBC is to use modular addition when encoding, and modular subtraction when decoding (modulo $2^{block\,size}$), instead of bitwise XOR. $\endgroup$ – Pedro Gimeno Oct 26 '18 at 23:11
  • $\begingroup$ see poncho's answer for the general case. $\endgroup$ – kelalaka Oct 27 '18 at 7:52

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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