1
$\begingroup$

I was intrigued by this question: Does adding complexity mean a more secure cipher?
And it led me to wonder: What are the implications (if any) of XORing a ciphertext with the original plaintext message? So:

$$C=(E_k(m)\oplus m)$$

My first impression was: "That sounds like a bad idea.", but is it necessarily? Seems like something similar is being used for Propagating Cipher Block Chaining.

"In PCBC mode, each block of plaintext is XORed with both the previous plaintext block and the previous ciphertext block before being encrypted."

|improve this question|||||
$\endgroup$
5
$\begingroup$

This is not a correct encryption scheme because it cannot be properly decrypted. Consider $E_k$ to be the one-time pad (OTP), the key being all zeroes. Then, for any message, you have:

$$C = E_{0^{|m|}}(m) \oplus m = (m \oplus 0^{|m|}) \oplus m = m \oplus m = 0^{|m|}$$

Or consider encrypting some random string $r$, then you have:

$$C = E_k(r) \oplus r$$

Which is basically the OTP. How would you expect to decrypt that?

The PCBC mode also does not output this construct as part of the ciphertext but feeds it as input to the block cipher encryption XORed with a plaintext block.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ You lost me. Why OTPs? I was really just thinking of generic block or stream ciphers. Why all zeroes? And what is that first equation? Ciphertext equals message XOR message equals 0 to the power of the length of the message? $\endgroup$ – voices May 14 '19 at 21:52
  • 1
    $\begingroup$ Because encryption schemes are usually required to fulfill the correctness requirement that $Dec_k(Enc_k(m)) = m$. If distinct messages encrypt to zero-strings, this cannot hold. So your approach does not work in general, for example when $Enc_k$ is the encryption function of the OTP. The answer you linked already mentions this: "Xoring the message into the ciphertext removes the ability to decrypt the ciphertext." This is easy to see if you think of encrypting random messages. $0^{|m|}$ is the notation for a string of zeroes that is as long as the message $m$. $\endgroup$ – user69201 May 14 '19 at 22:16
  • $\begingroup$ Is $D_k(E_k(m))=m$ the same as $m=E_k^{-1}(C)$? $\endgroup$ – voices May 14 '19 at 22:50
  • 1
    $\begingroup$ Yes, because $C$ is $E_k(m)$ and the inverse of $E_k$ is of course decryption $D_k$ (presuming that $-1$ is the inverse op. of course). $\endgroup$ – Maarten Bodewes♦ May 14 '19 at 23:40
  • $\begingroup$ @user69201 Quick question about that notation: Wouldn't $0^{|m|}$ just $= 0$? Say the length of $m$ was $8$ bits – doesn't $0^8$ still $=0$? I just want to make sure I get it right before I try to repeat it. $\endgroup$ – voices May 15 '19 at 16:30
0
$\begingroup$

Initially, I thought one use-case could be hiding ciphertext in ciphertext, which requires a dummy key that will result in a dummy plaintext while the real key reveals the real plain text.

However, the answer to this specific question being asked uses the same "original message" with the same ciphertext that resulted from XOR'ing it with a private key, which would be the computation of the same private key by XOR'ing those two! This breach would be equal to reusing the private key on a new message (as XOR'ing two ciphertexts signed with the same key would also compute the private key. This type of XOR operation is akin to the one-time pad cipher, assuming no padding and all strings are of same length.

Here is an example using a random 31-bit binary string:

  • plain text = 1001011110010111101001010000101
  • private key = 1111011011010110110101101101111
  • ciphertext = 0110000101000001011100111101010

(i.e. ciphertext is computed by plaintext ${\oplus}$ private key

Test that answers the question being asked: ciphertext ${\oplus}$ plain text = private key.

The associativity and commutativity of XOR is pretty interesting, among other qualities that can be seen here: https://en.wikipedia.org/wiki/Exclusive_or

Side note: One exercise I developed and found useful for exploring XOR is expanding the 1-bit truth table of XOR to 2-bits which will quadruple the combinations from 4 to 16, and then mapping all the possible combination pairs (inputs) into respective XOR operations, which will reveal that every ciphertext repeats n number of times, where n is equal to square root of the number of combinations which is the bit-length multiplied by 2 and raised to the power of 2 (i.e. in this case 2 bits, multiplied by 2, is 4, raised to the second power is 16, the square root of which is 4.

This fits with the notion that any arbitrary ciphertext computed will repeat exactly n number of times where n is equal to the square root of the message space multiplied by the keyspace. So from a range of 2^n possible messages, multiplied by 2^n possible keys, the square root of that sum is 2^n. (of which every one of them will have uniquely ordered inputs into the XOR function which result in the identical ciphertext output).

|improve this answer|||||
$\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.