7
$\begingroup$

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.

$\endgroup$

migrated from stackoverflow.com Apr 11 at 14:18

This question came from our site for professional and enthusiast programmers.

10
$\begingroup$

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)

$\endgroup$
  • 3
    $\begingroup$ In this case we actually could decrypt the message. The problem is everybody can :-(. Because in addition to $E_k(m) \oplus m$ we also get $E_k(m) \oplus 111\ldots 11$ $\endgroup$ – Marc Ilunga Apr 11 at 14:59
  • $\begingroup$ @MarcIlunga I actually failed to pay attention to the mathjax part of the question, which is different than what the text part asks! Thanks for bringing that to my attention $\endgroup$ – Ella Rose Apr 11 at 15:01
  • $\begingroup$ Thank you to both of you. Greatly appreciate the help. Definitely need to work on my number theory. $\endgroup$ – melloncollie Apr 11 at 15:14
  • $\begingroup$ Why is it relevant that the length of the algorithm is made public? $\endgroup$ – voices May 13 at 6:58
  • $\begingroup$ @tjt263 I do not understand what you are asking; I don't see anything in the answer or question that relates to your comment. Can you please reformulate the question and/or quote the part of the question/answer you are asking about? $\endgroup$ – Ella Rose May 13 at 14:25
6
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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)$.

$\endgroup$

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.