Cryptography - Breaking Repeating Key XOR Encryption
Post
Cancel

# Cryptography - Breaking Repeating Key XOR Encryption

In this post we’ll cover how to decrypt messages that have been XOR encrypted using a repeated key, such as `84 d2 7a 09`. The method we’ll be using to break the encryption uses statistics (letter frequencies and use of common words, bigrams, and trigrams), so the cipher-text needs to be a decent size otherwise it won’t work. The key used can be any arbitrary number of bytes long, but in general, the shorter the easy it is to break.

This technique requires you to know how to break single byte XOR encryption. If you’re unsure how to do that, please see my post about it here.

This post is also a solution to challenge 6 on the cryptopals website. This site is a great resource for hands on learning about cryptography. The technique used to complete this challenge is outlined on that page. This post will explain the same technique with a bit more detail and visual examples.

# Repeating Key XOR Encryption Example

Key (4 Byte Length)

 84 d2 7a 09

Plain-Text

This is the HEX representation of “ABCDEFGH”:

 41 42 43 44 45 46 47 48

Encryption

XOR the Plain-Text with key

 41 ⊕ 84 42 ⊕ d2 43 ⊕ 7a 44 ⊕ 09 45 ⊕ 84 46 ⊕ d2 47 ⊕ 7a 48 ⊕ 09

Cipher-Text

 c5 90 39 4d c1 94 3d 41

# Summary

As previously mentioned, we’ll use statistics to break the encryption. Because of this, very short cipher-texts such as the example above will not be able to be broken using this method.

The steps we’ll use to break the encryption are as follows:

1. Find the key length, we’ll call this length KEYSIZE.
2. Split the cipher-text into KEYSIZE length sections, and create KEYSIZE different blocks where block 1 contains the 1st byte of every section, block 2 contains the 2nd byte of every section etc.
3. Find the key for each block by performing single byte key XOR decryption.

Let’s get into some more detail on each step.

# How to Break it - Step 1

To find the key length, we’ll use some brute force and statistics. We don’t know the KEYSIZE, so we’ll guess that it’s from between 2 and 40 bytes long.

For each KEYSIZE we’ll take the first KEYSIZE worth of bytes, and the second KEYSIZE worth of bytes and find the hamming distance between them. We’ll then normalise this value by dividing by KEYSIZE. This should be repeated multiple times and the average taken. That is, do the same process with the second KEYSIZE worth of bytes, and the third KEYSIZE worth of bytes. Then the 3rd and 4th, 4th and 5th etc.

The KEYSIZE with the lowest normalised hamming distance should be the KEYSIZE.

Let’s show an example for a KEYSIZE of 2. Below is the first 8 bytes of cipher-text:

 1d 42 1f 4d 0b 0f 02 1f

We need to find the hamming distance between block 1 `0x1d42` and block 2 `0x1f4d`, which is `5`. We then need to divide this by KEYSIZE to normalise it. So we are left with `5/2 = 2.5`.

We repeat this with block 2 `0x1f4d` and block 3 `0x0b0f`, which is `4`. `4/2 = 2`.

Then again with block 3 `0x0b0f` and block 4 `0x021f`, which is `3`. `3/2 = 1.5`.

We can repeat this as many times as we like if we have more cipher-text. Since we did it 3 times above, we need to add the 3 results together and divide by 3 to get the average hamming distance:

(2.5 + 2 + 1.5) / 3 = 2

We have completed the step for a KEYSIZE of 2. We need to repeat all of this for each KEYSIZE (2-40).

The KEYSIZE with the lowest normalised hamming distance should be correct, but it’s not guaranteed. We’ll take the top performing KEYSIZEs and continue with the next step.

# How to Break it - Step 2

We’ll now convert the problem into a series of single byte XOR encryption problems. Here’s how to do that.

Let’s say that after Step 1 we think the KEYSIZE is 5. We’ll split the cipher-text into KEYSIZE length sections, and then we’ll create KEYSIZE number of blocks.

The first byte of each section goes into block 1. The second byte of each section goes into block 2. The third byte of each section goes into block 3 etc.

Here is how that would look visually with the first 16 bytes of cipher-text:

 1d 42 1f 4d 0b 0f 02 1f 4f 13 4e 3c 1a 69 65 1f

Block 1 (1st byte of each section)

 1d 0f 4e 1f

Block 2 (2nd byte of each section)

 42 02 3c

Block 3 (3rd byte of each section)

 1f 1f 1a

Block 4 (4th byte of each section)

 4d 4f 69

Block 5 (5th byte of each section)

 0b 13 65

We’re now ready to find the key.

# How to Break it - Step 3

For each of the blocks in Step 2, we’ll break them as if they are single byte key XOR encrypted, which if we have the right KEYSIZE, they are. After doing so, let’s say we get the following results:

• Block 1 Key = 69
• Block 2 Key = 20
• Block 3 Key = 69
• Block 4 Key = 6e
• Block 5 Key = 69

Our final decryption key would be the concatenation of all these, so it would be `69 20 69 6e 69`.

Back at the end of Step 1 we said we didn’t know for sure what the KEYSIZE was, only that we had a good idea. For each of the best performing KEYSIZEs, we do Step 2 & 3. This will give a decryption key for each of the KEYSIZEs.

To find out which one is most likely to be correct, we decrypt the cipher-text using each decryption key, then score the results based on how English it is. Scoring English was covered in the breaking single byte XOR key encryption, and the exact same method is used here.

And that’s all there is to it! You now know how to break repeated key XOR encryption. As a side note, Step 1 isn’t technically necessary as it only serves to reduce the amount of computation done in the subsequent steps.

# Results

Using this exact technique on the challenge cipher-text yielded the following results.

The best performing KEYSIZEs were:

• KEYSIZE of 2 (Hamming Distance: 2)
• KEYSIZE of 3 (Hamming Distance: 2.66)
• KEYSIZE of 29 (Hamming Distance: 2.79)
• KEYSIZE of 5 (Hamming Distance: 2.79)
• KEYSIZE of 18 (Hamming Distance: 2.94)

English scores after doing Steps 2 & 3 with each of the above KEYSIZEs:

• KEYSIZE of 29 (English Score: 4782)
• KEYSIZE of 18 (English Score: 1768)
• KEYSIZE of 2 (English Score: 1727)
• KEYSIZE of 5 (English Score: 1697)
• KEYSIZE of 3 (English Score: 1670)

A KEYSIZE of 29 was clearly the winner when it came to English scoring. Here is that decrypted cipher-text using the discovered 29 byte key:

```1 2 [+] Best Key Length: 29 [+] Key: <Buffer 54 65 72 6d 69 6e 61 74 6f 72 20 58 3a 20 42 72 69 6e 67 20 74 68 65 20 6e 6f 69 73 65> ```
```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 I'm back and I'm ringin' the bell A rockin' on the mike while the fly girls yell In ecstasy in the back of me Well that's my DJ Deshay cuttin' all them Z's Hittin' hard and the girlies goin' crazy Vanilla's on the mike, man I'm not lazy. I'm lettin' my drug kick in It controls my mouth and I begin To just let it flow, let my concepts go My posse's to the side yellin', Go Vanilla Go! Smooth 'cause that's the way I will be And if you don't give a damn, then Why you starin' at me So get off 'cause I control the stage There's no dissin' allowed I'm in my own phase The girlies sa y they love me and that is ok And I can dance better than any kid n' play Stage 2 -- Yea the one ya' wanna listen to It's off my head so let the beat play through So I can funk it up and make it sound good 1-2-3 Yo -- Knock on some wood For good luck, I like my rhymes atrocious Supercalafragilisticexpialidocious I'm an effect and that you can bet I can take a fly girl and make her wet. I'm like Samson -- Samson to Delilah There's no denyin', You can try to hang But you'll keep tryin' to get my style Over and over, practice makes perfect But not if you're a loafer. You'll get nowhere, no place, no time, no girls Soon -- Oh my God, homebody, you probably eat Spaghetti with a spoon! Come on and say it! VIP. Vanilla Ice yep, yep, I'm comin' hard like a rhino Intoxicating so you stagger like a wino So punks stop trying and girl stop cryin' Vanilla Ice is sellin' and you people are buyin' 'Cause why the freaks are jockin' like Crazy Glue Movin' and groovin' trying to sing along All through the ghetto groovin' this here song Now you're amazed by the VIP posse. Steppin' so hard like a German Nazi Startled by the bases hittin' ground There's no trippin' on mine, I'm just gettin' down Sparkamatic, I'm hangin' tight like a fanatic You trapped me once and I thought that You might have it So step down and lend me your ear '89 in my time! You, '90 is my year. You're weakenin' fast, YO! and I can tell it Your body's gettin' hot, so, so I can smell it So don't be mad and don't be sad 'Cause the lyrics belong to ICE, You can call me Dad You're pitchin' a fit, so step back and endure Let the witch doctor, Ice, do the dance to cure So come up close and don't be square You wanna battle me -- Anytime, anywhere You thought that I was weak, Boy, you're dead wrong So come on, everybody and sing this song Say -- Play that funky music Say, go white boy, go white boy go play that funky music Go white boy, go white boy, go Lay down and boogie and play that funky music till you die. Play that funky music Come on, Come on, let me hear Play that funky music white boy you say it, say it Play that funky music A little louder now Play that funky music, white boy Come on, Come on, Come on Play that funky music ```