What is the most efficient way to detect and to break xor encryption?

Question

I know that modern cryptographic algorithms are as close as they can to fully random data (ciphertext indistinguishability) and that trying to detect it is quite useless. But, what can we do on weak-crypto such as xor encryption ? Especially if we can get statistical studies of what is encrypted ?

What are the methods and which one is the most efficient (and under what hypothesis) ? And, finally, how to break efficiently this kind of encryption (only based on a statistical knowledge of what is encrypted) ?

Answer 1

XOR encryption with a short pad (i.e., shorter than the plaintext) is basically the Vigenère cipher. So standard techniques to break Vigenère should break xor encryption.

The basic idea is that if the encryption key is d symbols long, every d-th symbol is encrypted with the same pad. Thus, take every d-th ciphertext symbol and treat it like simple substitution cipher, break that and you have the 1st symbol of the key. Repeat for the d+1-th ciphertext symbols, d+2-th ciphertext symbols, etc. Eventually you will have all d symbols of the key.

To break the simple substitution ciphers, you might try brute force (if the symbol set is small) and compare possible plaintexts with the statistical data you know. For certain plaintexts (english language for example) you can often break most of it even quicker (e.g., with english language text the most frequent symbol in ciphertext probably maps back to an e, etc).

Now, you may be thinking, what if you don't know d. Often with Vigenère, the length of the key is brute forced. Try d=1, d=2, d=3,... For each d, see how well the output plaintext matches the statistical data. Return the key for which the plaintext most closely matched the statistical data.

Answer 2

In case of multibyte XOR frequency analysis is the way to go.

As is commonly known, most frequent character in regular English text is E (etaoinshrdlu being the top 12) but in some cases space (0x20 in ascii) can be more frequent, especially in shorter messages.

For executable code on the other hand, tho I can't find a reference, most frequent characters would be 0x00 or 0xFF both being common for integers. Do note that for executable code and binary files you can have some shortcuts. For example if you know that on some location in the ciphertext a 0x00 byte (or a sequence) MUST occur, it will leak the part of the key.

In case of single byte XOR, the keyspace is limited to 256 characters obviously.

There is a simple python tool by hellman called xortool which is particularly handy for CTF challenges :)

A tool to do some xor analysis:

• guess the key length (based on count of equal chars)
• guess the key (base on knowledge of most frequent char)

Answer 3

Just to add to the list. SANS posted a blog about a week ago on different tools for XOR encryption. The list is very good and it provides several tools, all which are good in my opinion.

Here is the link : SANS Blog on XOR tools