24

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) ?

Improve this question
2
  • You mean xor encoding - as far as I know, there is no such thing as XOR encryption :)
    – xort
    Oct 12, 2013 at 20:20
  • 2
    In fact, I think that 'xor encoding', 'xor encryption' and 'xor cipher' are all equally used to refer to this technique. Don't you think ?
    – perror
    Nov 28, 2013 at 19:30

3 Answers 3

Reset to default
16

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.

Improve this answer
1
  • 1
    Is there any way if your ciphertext is relatively short?
    – Vedaad Shakib
    Nov 6, 2015 at 6:02
13

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)
Improve this answer
2
  • 1
    Extremely nice tool ! Thanks for the link.
    – perror
    May 20, 2013 at 20:47
  • Or in case of Windows binary executable the first two bytes will be 0x4D5A (the MZ magic header).
    – Dominik Antal
    Sep 23, 2015 at 9:19
7

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

Improve this answer
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.