2
$\begingroup$

Long ago I created a simple program which obfuscated a file by taking the first byte, then XORing it with the second, taking the (original) 2nd byte and X-ORing with the 3rd, etc, down the line. The file size is unchanged, and I could invoke the same program to undo the obfuscation. No key or password was required. It was just a simple way to hide the contents of a file from casual view.

My Question Is: Does this result in a uniform distribution of byte values such that it appears to be encrypted, and the usual analysis would not turn up anything?

I know that this is not encryption. Also that the first byte is plaintext, but one could simply stick a random value in the source file, use a space or some other harmless byte there.

|improve this question
$\endgroup$

migrated from security.stackexchange.com Jun 29 '16 at 16:41

This question came from our site for information security professionals.

  • $\begingroup$ I don't feel steganography applies here. In the traditional example, if you had an image file and appended your xor obfuscated data after the ending byte, then this would apply to steganography. This is more about encoding. Think about a slightly less complicated version of your question but using the ever-so useful ROT13 encoding. $\endgroup$ – d0nut Jun 29 '16 at 16:47
  • $\begingroup$ @iismathwizard ROT13 would be easily detected as a Vigenere cipher or even just a Caesar cipher, right? This is not the case here. It is more like a very simple Enigma encoding, where previous input (past byte) affects current input (this byte). Much harder to determine what is happening, isn't it? (Else why was the Enigma so hard to break?) $\endgroup$ – user36481 Jun 29 '16 at 17:01
  • 1
    $\begingroup$ @Biv OK, but in general use it means: "render obscure, unclear, or unintelligible." How did it become scoped down to only source code? Don't we wish to obscure anything else? $\endgroup$ – user36481 Jun 29 '16 at 17:15
  • 4
    $\begingroup$ The biggest problem is that your technique does not provide diffusion. Each byte only influences the one next to it. If you xor all the bytes of your data together into a single "key" byte, then proceed to add the key to each byte in succession (and xor the output byte back into the "key"), then this technique will produce better statistically random looking data. $\endgroup$ – Ella Rose♦ Jun 29 '16 at 17:17
  • 1
    $\begingroup$ @bmm6o I edited my explanation of the algorithm, thank you! "Better 1, or 2?" $\endgroup$ – user36481 Jun 29 '16 at 17:30
2
$\begingroup$

It sound like you're using something like an XOR cipher to obfuscate your code. It will appear to be encrypted, but this can still be broken by frequency analysis since the use of a constant shift means that the encryption effectively has no key. An example of how to break a similar XOR cipher can be found here. As @iismathwizard mentioned, decryption requires no more knowledge than the fact that XOR is in use, in the same way as as ROT13 cipher might be broken

|improve this answer
$\endgroup$
  • $\begingroup$ What is the repeating key? I use the bytes of the file: 1st byte X-OR with 2nd, 2nd with 3rd, and so on. Nothing repeats there. If anything, the "key" is the file itself. I don't see how analysis would "leak" the method or the plaintext. $\endgroup$ – user36481 Jun 29 '16 at 16:45
  • $\begingroup$ My mistake, reread question and corrected answer. $\endgroup$ – Paradox Jun 29 '16 at 16:51
  • $\begingroup$ It is not a "constant shift". Each byte is X-ORed only with the previous byte, which could be anything. Was my explanation not clear? $\endgroup$ – user36481 Jun 29 '16 at 16:52
  • $\begingroup$ Your explanation was certainly clear. The shift would be performing an XOR with the next byte down the line which is a constant shift of 1. $\endgroup$ – Paradox Jun 29 '16 at 16:55
  • $\begingroup$ Sorry. I was too ignorant of terminology to understand your sentence. $\endgroup$ – user36481 Jun 29 '16 at 16:56
1
$\begingroup$

Some vocabulary (to answer your comments):

Obfuscation is used in computer science to hide source code while maintaining it executable see here. The idea is to hide the source code and make it hard to copy, disassemble.

Steganography is to hide a message such as the attacker does not know its existence. By having a encrypted file, this defeat this purpose as... the attacker see the file.

About your scenario:

You are assuming a weak attacker: it has only access to the plain text (and in your case, not even to the algorithm).

In cryptography, we consider a strong attacker: he has full access to the algorithm and he can try to encrypt as many plaintext as he wants. The idea is to be able to retrieve the key in order to decrypt the initial cipher text.

The scenario is the following:

1. Eve has intercepted an encrypted message from Alice.
   She can't read it.

2. During lunch, she access Alice's computer.
   For some reason she can not decipher the message.
   But she can encrypt many more messages so she will be able to attack the key later.

3. With all this encrypted message (with the same key) Eve can find the encryption key.

4. With this encryption key, she can now decrypt the initial message.

This is the usual assumption. However in your case you have no keys, therefore you only need the knowledge of the algorithm. Unfortunately, assuming a strong attacker immediately break your scheme.

About your scheme:

You are basically doing a XOR cipher in such a way that is insecure:

$X_1 || X_2 || X_3 || X_4$ will get encrypted in:

$X_1 || X_2 || X_3 || X_4 \oplus$
$~~0_~ || X_1 || X_2 || X_3 $

So we can consider this as :
$~~0_~ || X_2 || X_2 || X_4 \oplus$
$X_1 || X_1 || X_3 || X_3 $

Therefore we have repetitions which can lead to statistical attacks (if we completely ignore the fact that we know the inversion of the algorithm).

|improve this answer
$\endgroup$
  • $\begingroup$ So pairs of bytes will reveal the pattern? Am I understanding you? $\endgroup$ – user36481 Jun 29 '16 at 17:04
  • $\begingroup$ Due to the repetition, assuming you only know half of the message, yes it will leak statistical informations. $\endgroup$ – Biv Jun 29 '16 at 17:07
  • $\begingroup$ Moreover if your content is pure text. $\endgroup$ – Biv Jun 29 '16 at 17:08
  • $\begingroup$ I think I am not following. Nobody knows half of the message. They just have a file of random-seeming bytes. It is kind of like Base64. $\endgroup$ – user36481 Jun 29 '16 at 17:08
  • $\begingroup$ @nocomprende do you think base64 doesn't leak statistical information? $\endgroup$ – d0nut Jun 29 '16 at 17:08
1
$\begingroup$

To answer your question, I obfuscated 1MB of data that consisted of a single 1 followed by all 0's, using your technique, and fed the results to ent:

Entropy = 0.000039 bits per byte.

Optimum compression would reduce the size of this 1048576 byte file by 99 percent.

Chi square distribution for 1048576 samples is 267385856.00, and randomly would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 0.0000 (127.5 = random).

Monte Carlo value for Pi is 4.000000000 (error 27.32 percent).

Serial correlation coefficient is 0.499999 (totally uncorrelated = 0.0).

As you can see, in the worst case scenario, this method does not provide very good statistical randomness. In order to produce output with any real entropy, the input already needs to contain a good amount.

Suggestions

However, that's not to say there's no way to improve your method to provide decent statistical randomness. A few small changes can provide positive results.

First, consider using a nonce. Since we'll be iterating through the array anyways, we can include the iterator index into our calculations. This will ensure that successive similar values do not produce the same result. This will contribute to solving the problem of low entropy input not producing high entropy output.

Second, your technique as proposed suffers from low diffusion. Each byte is influenced exclusively by the byte that follows it. So a change in one location in the input influences the output only a small amount.

One way to fix this could be by combining via XOR all the bytes up front, then successively remove each byte, "encrypt it" using the XOR of the rest of the bytes as the "key", re-insert the "encrypted" byte back into the "key" using XOR, and repeat. The removal step is only required for the steps to be invertible.

Note that if you use the above technique, you will want to use modular addition for any further combination operations, otherwise you'll simply be stacking/moving bytes around.

A similar (but evolved) version of your technique that incorporates these recommendations is capable of producing ent results that provide good statistical randomness after a single application:

Entropy = 7.889023 bits per byte.

Optimum compression would reduce the size of this 1048576 byte file by 1 percent.

Chi square distribution for 1048576 samples is 163954.21, and randomly would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 128.0863 (127.5 = random).

Monte Carlo value for Pi is 3.031574370 (error 3.50 percent).

Serial correlation coefficient is 0.008583 (totally uncorrelated = 0.0).

I think what you're effectively looking at/for is an unkeyed psuedorandom permutation. Interestingly, you can take an unkeyed psuedorandom permutation and make a secure cipher using the Even-Mansor construction. But key management and encryption is a whole 'nother level and not what you were attempting to accomplish judging by your description.

|improve this answer
$\endgroup$
  • $\begingroup$ I created another version of the algorithm (again, very long ago) which simply used the TurboC rand algorithm to generate a stream to X-OR the bytes. This effectively uses the recommended method of X-OR, but I relied on the fact that every time I started the program, it had the same seed. If I had written it to take a seed as a command-line argument, it would be like a one-time pad with X-OR, right? $\endgroup$ – user36481 Jun 30 '16 at 0:14
  • $\begingroup$ @nocomprende in as far as a stream cipher construction emulates a one-time pad, yes it's like that. Be sure to remember that it is not the same thing, though. A stream cipher is not a one time pad, even with unique seeds. $\endgroup$ – Ella Rose♦ Jun 30 '16 at 0:52
-1
$\begingroup$

I would agree with @Biv regarding the strength of XOR encryptions are generally linked to the key. i.e. they are only as strong as the key stream.Conventionally, XOR encryption, relies on bitwise exclusive OR operation to generate the ciphertext since it is hardware efficient.

In LTE, ciphering of user data takes place in the Packet Data Convergence Protocol (PDCP) sublayer where IP packets are encrypted after their header is compressed.It relies on a 128-bit Advanced Encryption Standard (AES) modeXOR encryption before the digital modulation (QAM/QPSK) and OFDM pulse shaping procedures.

Generally, if XOR encryption is combined with additional means of randomizing the data, security might be increased. Alternatively, substitution, shifting of rows, mixing of columns or an XOR operation with a key shuffling will also improve the security.

|improve this answer
$\endgroup$
  • $\begingroup$ A long time ago I wrote a routine that took the low six bits of ASCII text and "compressed" by cramming the bits together, so that 4 bytes reduced to 3. This had the advantage of automatically folding lowercase to uppercase (not reversibly) with no computational effort (our data was supposed to be just upper case letters, digits and punctuation). Would that method obfuscate in a way that does not yield readily to simple analysis, or am I just barking up the same tree? $\endgroup$ – user36481 Jun 29 '16 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy