How secure is XOR-CBC?

Question

How secure would this be? To be clear, I mean replacing the block cipher encryption step in the Wikipedia diagram explaining CBC with plain old XOR?

EDIT:

Replace block cipher encryption part of diagram with XOR ($\oplus$)

CBC diagram

Or: ($C_0 = IV$)

$$C_i \equiv \left(\bigoplus_{C_{i-1}}^{P_i}\right) \oplus {K}$$

Answer 1

So the XOR-CBC encryption of the i-th block $P_i$ with the key $K$ would be given by the following equation:

$$ C_i = C_{i-1} \oplus P_i \oplus K $$

Similarly, the encryption of the previous block is given by:

$$ C_{i-1} = C_{i-2} \oplus P_{i-1} \oplus K $$

Now the really bad thing is that we can substitute the right-hand side of the second equation into the occurrence of $C_{i-1}$ in the first and obtain equations for $C_i$ and $P_i$ where the $K$ terms cancel out:

$$ \begin{align} C_i & = C_{i-2} \oplus P_{i-1} \oplus K \oplus P_i \oplus K \\ C_i & = C_{i-2} \oplus P_{i-1} \oplus P_i \\ P_i & = C_{i-2} \oplus P_{i-1} \oplus C_i \\ \end{align} $$

Another way of putting this is we can rewrite the whole encryption scheme so that only the value of the first block (not counting the IV) depends on the secret key, and the rest of the ciphertext blocks only depend on previous ciphertext blocks (known to attackers) and plaintext:

$$ \begin{align} C_1 & = IV \oplus K \oplus P_1 \\ C_2 & = C_1 \oplus K \oplus P_2 & = IV \oplus P_1 \oplus P_2 \\ C_3 & = C_2 \oplus K \oplus P_3 & = C_1 \oplus P_2 \oplus P_3 \\ C_4 & = C_3 \oplus K \oplus P_4 & = C_2 \oplus P_3 \oplus P_4 \\ \vdots \end{align} $$

Which means that if we have guesses about the values of plaintext blocks beyond the first one, we can trivially test them without even thinking about the key. Like, if we hypothesize the first bits of $P_2$ and $P_3$ are equal, then it follows that the first two bits of $C_1$ and $C_3$ must be equal too, because:

$$ P_2 \oplus P_3 = C_1 \oplus C_3 $$

Also, if you can learn the value of any one plaintext block, you can figure out all of the following ones. (Try working out why.)

It should go without saying this is super bad.

Answer 2

Completely insecure.

If you just replace the encryption with XOR with the key, then the first ciphertext block is just $c_1=m_1 \oplus k$. The second block would be $c_2=m_2 \oplus c_1 \oplus k = m_2 \oplus m_1$.

The second block is actually not encrypted at all. And that goes on, the first, third, fifth and so on block is just an XOR with the key, the second, fourth, sixth and so on doesn't depend on the key at all.

Answer 3

XOR-CBC offers little to no protection, especially against known plaintext.

Let's take the definition of the question:

For $i=0$:

$$C_{i=0} \equiv \left(\bigoplus_{IV}^{P_{i=0}}\right) \oplus {K}$$

for $i \ge 1$:

$$C_i \equiv \left(\bigoplus_{C_{i-1}}^{P_i}\right) \oplus {K}$$

then an iteration for a given $i$ of XOR-CBC encryption is, for $i \ge 1$:

$$C_i = \operatorname{E}(K, C_{i-1} \oplus P_i) \to$$ $$C_i = K \oplus (C_{i-1} \oplus P_i)$$

The block size is necessarily the same size as the key size in this scheme.

---

Then let's show that the value of $K$ is immediately leaked if a single $P_i$ for a specific $i$ is known:

$$K = (C_{i-1} \oplus P_{i}) \oplus C_{i}$$

You simply XOR both sides with $K$ and then with $C_{i}$ to get to this equation, in case your math is rusty.

As the IV is generally known, information about the first plaintext block equality leaks information about the key.

---

Even worse, you can perform that attack for any known bit $b$ for any iteration, and you can combine those known bits of a key to find a full key, or to bruteforce the rest of the key.

$$C_{i,b} = K_b \oplus (C_{i-1,b} \oplus P_{i,b})$$

Now assume that $P_{i,b}$ is known (known plaintext) and $C_{i-1,b}$ is known, then $K_b$ is immediately known as:

$$K_b = (C_{i-1,b} \oplus P_{i,b}) \oplus C_{i,b}$$

Since the key is repeated, the above equation holds for any bit in the key: known plaintext at the same location (modulus the block / key size) will immediately expose the key bit at the same location within the block.

This is the original stronger attack that I had shown, which is slightly more complex and confusing. I showed it to indicate that known even a single bit of known plaintext already breaks the cipher. Each bit in the ciphertext only depends on a single bit of the key instead of all bits - as usual for ciphers!

---

The security in CBC relies for a large part on the protection of the key value that the block cipher offers. If that protection is taken away, then CBC mode - and most if not all other block cipher modes - will fail.

---

Also compare XOR-CBC with a one-time-pad where the key bits become known if the plaintext is known. For an OTP though the key stream should never repeat, so the the knowledge of the key bits doesn't expose any other information. XOR-CBC implies the reuse of the bits in the key.

So you don't even need "advanced" analysis like in tylo's answer. Commonly ciphers are required to be secure under for known- and even chosen plaintext and CBC clearly doesn't hold under assumption if XOR is used instead of a block cipher.