Cracking repeating XOR key crypto

My last post here, XOR'd play: Normalized Hamming Distance, was a lengthy bit about the reliability of Normalized Hamming Distance to determine the size of a repeating XOR key that was used to encrypt a string of text and was based on my experience working on the Matasano Crypto Challenges at cryptopals.com.

After a few weeks of focusing on other things, I returned to that effort and finished problem six from challenge set one, which says to use Normalized Hamming Distance to determine the probable key size and then use English letter frequency analysis to determine the probable bytes that make up the key. That's the short version.

The script I wrote for challenge applies some extra math to the problem of determining key size, because I found normalized Hamming Distance alone to not be very reliable. However, even with the extra math, the problem is still one of probability, not certainty. If you have no idea about the key size, the problem is even more expansive, though not completely open ended because if it's repeating key, it has to be no more than half the size of the encrypted byte stream.

Let's look at an example. Below I have already populated two variables, $plaintext and $key and am using XOR-Encrypt.ps1 to encrypt the $plaintext value with the $key and return a base64 encoded string. In the second command, I'm populating the $ciphertext variable with that base64 encoded string.

Click to enlarge

Now that we have a string of plaintext encrypted with a repeating XOR key, let's try cracking it.



Click to enlarge

In the screenshot above, I've run the Crack-XORRepeatingKeyCrypto.ps1 script with about the minimum set of command line parameters. The VERBOSE output line tells me that I didn't provide a MaxKeySize value, so the script has calculated the number of bytes in the ciphertext and has set the MaxKeySize to half of that value. If we're dealing with repeating key XOR crypto, the key must be at most half the size of the ciphertext, otherwise the key can't repeat (completely).

The script applies normalized Hamming Distance to find the top n most likely key sizes, five is the default, which you can see listed towards the bottom of the screen. Next, the script calculates the most frequently occurring greatest common denominator, hereafter MFOGCD, of those top n probable key sizes. In my testing, calculating the MFOGCD of the top n normalized average Hamming Distance values can be used to more accurately find the correct key size. This is a good example, as you can see, the correct key size is 30, but its normalized average Hamming Distance is fourth in the list of the top five.

My script has a programmatic bias towards smaller key sizes, especially where they are the MFOGCD. This formula returns the correct key size more than 90% of the time in my testing where I was able to control for the MaxKeySize, whereas normalized average Hamming Distance alone only returns the correct key size about 40% of the time where MaxKeySize is controlled. If MaxKeySize is unknown, your mileage may vary.

After the script determines the most probable key size, it transposes the ciphertext into blocks aligned on the key size byte boundaries. In other words, if the script determines the key size is 30 bytes, the first block will be comprised of ciphertext bytes 0, 29, 59, 89, 119, etc. The next block begins with ciphertext byte 1, then 30, 60, 90, 120, etc. This process repeats until all ciphertext bytes have been allocated to their respective blocks.

Next the script moves into the actual brute-force phase, XORing each byte of the transposed blocks against ASCII printable characters. That's the default, you can apply all bytes 0x00 - 0xFF, via the -includeNonPrintable command line switch. If you think this takes longer, you're right.

After each transposed block is XOR'd with each byte, the English letter frequency calculation is applied and the byte that results in the highest score, is deemed to be the most probable byte for that position in the key and the process repeats for each byte in the key.

Once all the likely key bytes have been determined, the original ciphertext is XOR'd against that key and the likely plaintext is returned. You can see this above in the ProbableDecryptedValue property of the output. At first glance, the output looks pretty good, but if you read it carefully, you'll see it's not exactly correct. Remember we're dealing with probabilities.

If you look at that ProbableKey property, you can see the probable key and you may be able to guess which byte is incorrect. You could use the XOR-Decrypt.ps1 script, which can take a user supplied key string and decrypt the ciphertext if you want to be more exact. Without a key, XOR-Decrypt.ps1, assumes a single byte key and attempts to brute force it, but I digress.

So that's the script when it's working well, but the probabilities sometimes don't come out so nicely. Here's another example:



Click to enlarge

If you look at the ProbableDecryptedValue property here, you can plainly see this does not look like English plaintext. What happened? The script worked as written. It calculated the MFOGCD among the top five most probable key sizes, but that value, 16, was not also listed in the top five most probable key sizes, so it didn't try 16 as a key size. Instead, it selected the smallest key among the keys with the smallest normalized average Hamming Distance, 416 and that turned out to be horribly wrong, but all is not lost.

One approach that I've tried at this point, is to run the script again, but add the -MaxKeySize parameter with an argument matching the smallest key size from the above run, 48. Here's the output of that run:

Click to enlarge

This looks more like English plaintext, but it's still not perfect. Note the ProbableKeySize property is 16 bytes, that was the MFOGCD from the previous run so I'm not surprised to see it is the probable key size. 48 still has the lowest normalized average Hamming Distance, but remember, the script has a bias towards smaller keys, especially when those keys are also the MFOGCD in the list of the top n ProbableKeySizes.

Our key is obviously not 100% correct, but again there may be enough of the correct value there that you can make some guesses and use the XOR-Decrypt.ps1 script to try them out until you have the correct key.

What happens if you run the script again and pass -MaxKeySize as 16, unfortunately, if you do that, the most probable key size becomes two because that is the MFOGCD and that yields even more inaccurate results.

What's the practical use for this script? There is some malware that uses repeating XOR key encryption because it's easy to implement. You may be able to apply it in your analysis. Does it work against code?

Here's an example:

Click to enlarge

Crack-XORRepeatingKeyCrypto.ps1's accuracy could be improved at a performance cost. If you look at XOR-Decrypt.ps1, you'll see that it has multiple scoring functions, a sort of mini-neural network. One for English letter frequency, one for English bigram frequency and one for English trigram frequency. All of the values returned from those functions factor into determining the most probable key for XOR-Decrypt.ps1, but because of the way Crack-XORRepeatingKeyCrypto.ps1 works, determining the most probable byte for each position of the key against the transposed blocks, bigrams and trigrams can't be used because we're not looking at the bytes in context, so bigrams and trigrams won't follow their natural frequency of occurrence.

Crack-XORRepeatingKeyCrypto.ps1 could factor in bigram and trigram scores when it moves to the stage of decrypting the original ciphertext, using what it has calculated as the most probable key, but that would require maintaining a list of the top n most probable keys and trying each of them, scoring them and choosing the one with the best score.

Maybe if time permits, I'll trying making this change, but I'm afraid of what it may do to the run time.

Lastly, the script includes a .SYNOPSIS section with help and examples, like any PowerShell script should. So do a Get-Help -Full .\Crack-XORRepeatingKeyCrypto.ps1 | more for additional information.