Does adding complexity mean a more secure cipher?

Question

I have a cryptography workshop question I'm having trouble with as follows;

Person A creates a cipher $E_k(m)$ which produces a ciphertext from message $m$ using key $k$. The function inside $E$ is kept secret but the length of $E_k(m)$ is known.

Person B recommends "increasing" security of the cipher by instead doing :

$(E_k(m) \oplus m)\ ||\ (E_k(m) \oplus 1111...11)$

Does this in fact increase security of the cipher or increase new problems.

My thinking is, depending on the function within $E$, xoring the output of the cipher with the plaintext message $m$ could expose the key $k$, meaning the extra complexity is for nothing. Am I on the right track, or am I missing something?

I have tried searching for examples of similar schemes and found nothing (which probably means it's not a good scheme) but I need to justify my answer.

Any steers in the right direction would be greatly appreciated, I'm more than happy to do the research myself just unsure what specifically to look for.

Unfortunately the above context is all I have been provided for this question.

Answer 1

xoring the output of the cipher with the plaintext message

Xoring the message into the ciphertext removes the ability to decrypt the ciphertext.

If all you have is $k, c = E_k(m) \oplus m$, then you need to know $m$ in order to strip the external $m$ off of $E_k(m)$ before you can apply $m = D_k(E_k(m))$; Basically, you would need to know the message in order to "decrypt" the message, but since you already know the message, then there would be no knowledge gained from "decrypting".

$(E_k(m)\oplus m)||(E_k(m) \oplus 1111...11)$

The previous section was striked out, because there was more to the suggestion than simply xoring the message into the ciphertext.

In fact, the complete suggestion is far, far worse then simply implying the inability to decrypt a ciphertext: Anyone can decrypt a ciphertext from this scheme without requiring the key.

$$c = (E_k(m) \oplus m) || E_k(m) \oplus 1111\dots 11)\\c_{\text{a}} = E_k(m) \oplus m\\c_{\text{b}} = E_k(m) \oplus 1111 \dots 11\\c' = c_{\text{b}} \oplus 1111\dots11\\m = c_{\text{a}} \oplus c'$$

The value $1111\dots11$ is known to all, so anyone can compute $$E_k(m) = E_k(m) \oplus 1111\dots11 \oplus 1111\dots11$$

So $E_k(m)$ is effectively public knowledge, so again anyone can compute $$m = E_k(m) \oplus m \oplus E_k(m)$$

This scheme is completely broken.

I have tried searching for examples of similar schemes and found nothing (which probably means it's not a good scheme) but I need to justify my answer.

See the previous section - "encryption" is an invertible process: You have to be able to undo the transformation so that you can retrieve the plaintext from any given ciphertext.

It is completely broken, so you won't find anything similar to it (other than situations where people asked this same question and found it to be broken)

Does this in fact increase security of the cipher or increase new problems.

It's a lot easier to determine whether or not doing x or y will increase/decrease security once you have a clear goal of what it means to be secure. This is a context dependent notion.

It helps to list:

• What you have
• What your adversary can do
• What you want to accomplish (in very specific terms).

If you don't know where to start, then look for the standard notions of security that cryptographers have already worked out for the context of interest (e.g. indistinguishability for ciphers)

Answer 2

This is indeed a example of complexity not adding security and actually weakening it.

The second encryption can be written as $c = c_1|| c_2$, where $c_1 = E_k(m) \oplus m$ and $c_2 = E_k(m) \oplus 111\ldots11$.

Now observe that $m' = c_1 \oplus c_2 = m \oplus 111\ldots11$. And we can easily get $m$ as $m' \oplus 111\ldots 11$

Answer 3

Even ignoring the complete and total brokenness of the full cipher, the $(E_k(m) \oplus 1111...11)$ component keeps any possible first half from adding security. Since XORing the ciphertext with all 1s is an operation independent of either the key or the message, the cipher

$(f(x)) || (E_k(m) \oplus 1111...11)$

permits the recovery of $E_k(m)$ for any possible $f(x)$.