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.

1. Repeating Key XOR Encryption Example
2. Summary
3. How to Break it - Step 1
4. How to Break it - Step 2
5. How to Break it - Step 3
6. Results

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:

[+] 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>

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