Take the 2-minute tour ×
Reverse Engineering Stack Exchange is a question and answer site for researchers and developers who explore the principles of a system through analysis of its structure, function, and operation. It's 100% free, no registration required.

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

share|improve this question
    
You mean xor encoding - as far as I know, there is no such thing as XOR encryption :) –  xort Oct 12 '13 at 20:20
    
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 '13 at 19:30

3 Answers 3

up vote 8 down vote accepted

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)
share|improve this answer
    
Extremely nice tool ! Thanks for the link. –  perror May 20 '13 at 20:47

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.

share|improve this answer

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

share|improve this answer
1  
Nice link indeed - thanks for sharing! –  Till May 21 '13 at 12:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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