0
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ In your modification, what do you XOR the input of the block cipher with? Do you use the same key as the second xor operand in the new block cipher construct? $\endgroup$ – Marc Ilunga Jan 2 at 9:57
  • 3
    $\begingroup$ This question was already answered by before I could ask if this is homework. It really smells like a homework question and those are required to show effort from your side. Please do try to keep this in mind for any new questions that you decide to post. $\endgroup$ – Maarten Bodewes Jan 2 at 11:12
  • 1
    $\begingroup$ This is exactly classical autokey cipher. $\endgroup$ – kelalaka Jan 2 at 19:47
  • $\begingroup$ @Maarten-reinstateMonica for a statement, I will never post a homework question; I have no homework. $\endgroup$ – Legorooj Jan 2 at 22:34
  • $\begingroup$ @kelalaka I don't think so; edited $\endgroup$ – Legorooj Jan 2 at 23:25
2
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks for this answer - it highlights a danger I didn't see... I'll tag you when I've reviewed a modification.. $\endgroup$ – Legorooj Jan 3 at 0:25
9
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ I think you misunderstood me; I've edited $\endgroup$ – Legorooj Jan 2 at 23:25
  • 1
    $\begingroup$ The 3rd, 5th and so on blocks can also be solved for without the key, as I show in my answer. $\endgroup$ – Luis Casillas Jan 3 at 0:13
  • $\begingroup$ @Legorooj Regardless of your edit, basically your cipher is a Vigenere cipher with fixed keysize, just a bit more complicated (or it's actually worse than Vigenere, depending on how you use it exactly). Reuse of the key directly is just bad, and completely broken. Since you accepted the other answer after your edit, I don't think this needs to be updated to your edit. $\endgroup$ – tylo Jan 3 at 0:36
  • $\begingroup$ @tylo your answer appears to miss out the IV. By my understanding, with the IV, your first equation ought to be $c_1 = m_1 \oplus IV \oplus k$ $\endgroup$ – Legorooj Jan 3 at 0:39
  • $\begingroup$ @tylo yes, block-based vigénere with an IV to stop ECB-like problems. $\endgroup$ – Legorooj Jan 3 at 0:40
6
$\begingroup$

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.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ I think you might have misunderstood - but I'm not sure - is your answer still valid with my edit? $\endgroup$ – Legorooj Jan 2 at 23:26
  • $\begingroup$ @Legorooj I've changed my answer to make it compatible with your new description of XOR-CBC, which is compatible with my understanding. I've also shown a simpler attack on a full block of known plaintext, which hopefully will make the answer a bit more clear (even though the attack is slightly less strong). $\endgroup$ – Maarten Bodewes Jan 4 at 0:33
  • $\begingroup$ This is much clearer. Thanks - I'll tag you when I've taken this into account and modified the construction. I've an idea that uses counters, an untried key/block size idea, and a more stream-based approach. $\endgroup$ – Legorooj Jan 4 at 1:46
  • $\begingroup$ Please do not append that to your question here. $\endgroup$ – Maarten Bodewes Jan 4 at 4:49

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.