What's wrong with XOR encryption?

Question

I wrote a short C++ program to do XOR encryption on a file, which I may use for some personal files (if it gets cracked it's no big deal - I'm just protecting against casual viewers). Basically, I take an ASCII password and repeatedly XOR the password with the data in the file.

Now I'm curious, though: if someone wanted to crack this, how would they go about it? Would it take a long time? Does it depend on the length of the password (i.e., what's the big-O)?

Benedetto

Or you could just break down and use something like TrueCrypt... – Blithering

Answer 1

The problem with XOR encryption is that for long runs of the same characters, it is very easy to see the password. Such long runs are most commonly spaces in text files. Say your password is 8 chars, and the text file has 16 spaces in some line (for example, in the middle of ASCII-graphics table). If you just XOR that with your password, you'll see that output will have repeating sequences of characters. The attacker would just look for any such, try to guess the character in the original file (space would be the first candidate to try), and derive the length of the password from length of repeating groups.

Binary files can be even worse as they often contain repeating sequences of 0x00 bytes. Obviously, XORing with those is no-op, so your password will be visible in plain text in the output! An example of a very common binary format that has long sequences of nulls is .doc.

Own

Note that it is nearly trivial to XOR a whole file with a space character, at which point any sensible strings leap out as a likely password. For a binary file XORed with an ASCII string, any strings in the result are the password. The strings command at a shell prompt will find them. – Demoniac

FWIW you should be clear that you're talking about an XOR scheme when the "key" is less than the plaintext. If the key is the same size as the plaintext, and "truly" random (at least from the POV of the attacker) it's a OTP; aka unbreakable. – Mack

Good explanation. But couldn't XOR be made more secure if the password is the same length as the plaintext? – Raimund

See comment above. Yes, if you have a one-time pad (same length, and crypto-quality random), then XOR is perfectly fine. – Own

@NoonSilk - Are you aware of any approach where a small password was fed into a Key Derivation Function to generate a plain text sized key? Would that make XOR safe and fast? KDFs are slow, but if one is looking to generate a 1MBit sized key, can one reduce the iterations on the KDF and be safe? – Congenital

Answer 2

I concur with Pavel Minaev's explanation of XOR's weaknesses. For those who are interested, here's a basic overview of the standard algorithm used to break the trivial XOR encryption in a few minutes:

1. Determine how long the key is. This is done by XORing the encrypted data with itself shifted various numbers of places, and examining how many bytes are the same.

2. If the bytes that are equal are greater than a certain percentage (6% according to Bruce Schneier's Applied Cryptography second edition), then you have shifted the data by a multiple of the keylength. By finding the smallest amount of shifting that results in a large amount of equal bytes, you find the keylength.

3. Shift the cipher text by the keylength, and XOR against itself. This removes the key and leaves you with the plaintext XORed with the plaintext shifted the length of the key. There should be enough plaintext to determine the message content.

Read more at Encryption Matters, Part 1

Peeples

Can you explain part 3? I have attempted this but it doesn't seem to work. For example if I do this in decimal numbers. plain text is 23456, key is 12, cipher is then 31577 then XOR gives me gibberish – Rivulet

Note that as of 2020-02-07, it appears that the http://www.kuro5hin.org/?op=displaystory&sid=2000/4/10/174741/423 URL is no longer available — the domain appears to be for sale. You can, however, find the original article on the WayBack Machine (Internet Archive) at Encryption Matters, Part 1. – Fed

Answer 3

XOR encryption can be reasonably* strong if the following conditions are met:

• The plain text and the password are about the same length.
• The password is not reused for encrypting more than one message.
• The password cannot be guessed, IE by dictionary or other mathematical means. In practice this means the bits are randomized.

*Reasonably strong meaning it cannot be broken by trivial, mathematical means, as in GeneQ's post. It is still no stronger than your password.

Germaun

For a one-time pad, the key must be the same length as the plaintext. When this is true, and the key is never reused, the one-time pad is absolutely secure. If you're at all interested in the history of cryptography, I highly recommend The Codebreakers, by David Kahn: amazon.ca/… – Habited

"reasonably secure" - One time pads cannot be broken by any means, ever (assuming the pad is completely random). They are the only absolutely secure method of encryption. – Windle

One-time pad is not absolutely secure; it is only as secure as the method of sharing the pad between the encrypting end and the decrypting end. – Epigenous

Answer 4

In addition to the points already mentioned, XOR encryption is completely vulnerable to known-plaintext attacks:

cryptotext = plaintext XOR key
key = cryptotext XOR plaintext = plaintext XOR key XOR plaintext

where XORring the plaintexts cancel each other out, leaving just the key.

Not being vulnerable to known-plaintext attacks is a required but not sufficient property for any "secure" encryption method where the same key is used for more than one plaintext block (i.e. a one-time pad is still secure).

Overload

+1 it is worth mentioning that if even a small portion of the file is known (such as the headers used by most file-formats), the key can be easily obtained and the entire file decrypted. – Windle

Answer 5

Ways to make XOR work:

Use multiple keys with each key length equal to a prime number but never the same length for keys. Use the original filename as another key but remember to create a mechanism for retrieving the filename. Then create a new filename with an extension that will let you know it is an encrypted file. The reason for using multiple keys of prime-number length is that they cause the resulting XOR key to be Key A TIMES Key B in length before it repeats. Compress any repeating patterns out of the file before it is encrypted. Generate a random number and XOR this number every X Offset (Remember, this number must also be recreatable. You could use a RANDOM SEED of the Filelength.

After doing all this, if you use 5 keys of length 31 and greater, you would end up with a key length of approximately One Hundred Meg!

For keys, Filename being one (including the full path), STR(Filesize) + STR(Filedate) + STR(Date) + STR(Time), Random Generation Key, Your Full Name, A private key created one time.

A database to store the keys used for each file encrypted but keep the DAT file on a USB memory stick and NOT on the computer.

This should prevent the repeating pattern on files like Pictures and Music but movies, being four gigs in length or more, may still be vulnerable so may need a sixth key.

I personally have the dat file encrypted itself on the memory stick (Dat file for use with Microsoft Access). I used a 3-Key method to encrypt it cause it will never be THAT large, being a directory of the files with the associated keys.

The reason for multiple keys rather than randomly generating one very large key is that primes times primes get large quick and I have some control over the creation of the key and you KNOW that there really is no such thing as a truely random number. If I created one large random number, someone else can generate that same number.

Method to use the keys: Encrypt the file with one key, then the next, then the next till all keys are used. Each key is used over and over again till the entire file is encrypted with that key.

Because the keys are of different length, the overlap of the repeat is different for each key and so creates a derived key the length of Key one time Key two. This logic repeats for the rest of the keys. The reason for Prime numbers is that the repeating would occur on a division of the key length so you want the division to be 1 or the length of the key, hense, prime.

OK, granted, this is more than a simple XOR on the file but the concept is the same.

Lance

Armed

Answer 6

I'm just protecting against casual viewers

As long as this assumption holds, your encryption scheme is ok. People who think that Internet Explorer is "teh internets" are not capable of breaking it.

If not, just use some crypto library. There are already many good algorithms like Blowfish or AES for symmetric crypto.

Iatrogenic

Answer 7

The target of a good encryption is to make it mathematically difficult to decrypt without the key.
This includes the desire to protect the key itself.
The XOR technique is basically a very simple cipher easily broken as described here.

It is important to note that XOR is used within cryptographic algorithms.
These algorithms work on the introduction of mathematical difficulty around it.

Andantino

Answer 8

Norton's Anti-virus used to use a technique of using the previous unencrypted letter as the key for next letter. That took me an extra half-hour to figure out, if I recall correctly.

If you just want to stop the casual viewer, it's good enough; I've used to hide strings within executables. It won't stand up 10 minutes to anyone who actually tries, however.

That all said, these days there are much better encryption methods readily available, so why not avail yourself of something better. If you are trying to just hide from the "casual" user, even something like gzip would do that job better.

Emperor

Answer 9

Another trick is to generate a md5() hash for your password. You can make it even more unique by using the length of the protected text as an offset or combining it with your password to provide better distribution for short phrases. And for long phrases, evolve your md5() hash by combining each 16-byte block with the previous hash -- making the entire XOR key "random" and non-repetitive.

Reinke

Answer 10

RC4 is essentially XOR encryption! As are many stream ciphers - the key is the key (no pun intended!) you must NEVER reuse the key. EVER!

Leake

Answer 11

I'm a little late in answering, but since no one has mentioned it yet: this is called a Vigenère cipher.

Wikipedia gives a number of cryptanalysis attacks to break it; even simpler, though, since most file-formats have a fixed header, would be to XOR the plaintext-header with the encrypted-header, giving you the key.

Windle

Answer 12

That ">6%" GeneQ mentions is the index of coincidence for English telegraph text - 26 letters, with punctuation and numerals spelled out. The actual value for long texts is 0.0665.

The <4% is the index of coincidence for random text in a 26-character alphabet, which is 1/26, or 0.385.

If you're using a different language or a different alphabet, the specific values will different. If you're using the ASCII character set, Unicode, or binary bytes, the specific values will be very different. But the difference between the IC of plaintext and random text will usually be present. (Compressed binaries may have ICs very close to that of random, and any file encrypted with any modern computer cipher will have an IC that is exactly that of random text.)

Once you've XORed the text against itself, what you have left is equivalent to an autokey cipher. Wikipedia has a good example of breaking such a cipher

http://en.wikipedia.org/wiki/Autokey_cipher

Haber

Answer 13

If you want to keep using XOR you could easily hash the password with multiple different salts (a string that you add to a password before hashing) and then combine them to get a larger key. E.G. use sha3-512 with 64 unique salts, then hash your password with each salt to get a 32768 bit key that you can use to encrypt a 32Kib (Kilibit) (4KiB (kilibyte)) or smaller file. Hashing this many times should be less than a second on a modern CPU. for something more secure you could try manipulating your key during encryption like AES (Rijndael). AES actually does XOR times and modifies the key each repeat of the key using a switch table. It became an internation standard so its quite secure.

Towhead