How to break a repeating key XOR encryption

Break a repeating key XOR encryption

A repeating key XOR encryption uses a key that is longer than one byte in size and is repeatedly used to encrypt the entire plain text.

XOR encryption is symmetric encryption that uses the same key to encrypt and decrypt the message. It secures communication between two endpoints by XORing plain text with the key.

Note: To read more about XOR encryption, click here.

Methodology

We'll assume that the text is written in English, and will use letter frequency to break the XOR encryption. To crack repeating key XOR encryption, we must understand how breaking a single byte key XOR encryption works.

Steps

To break XOR encryption, we need to figure out two things:

• Key size
• Encryption key

Step 1

To find the key size, we'll use the brute force method. Either we can keep guessing the size of the key linearly or randomly. For each key size, calculate its Hamming distanceThe number of bits by which two strings differ.

To calculate the Hamming distance:

• Divide the cipher texts into blocks of length equal to the key size guessed above.
• Calculate the Hamming distance between the first two blocks.
• Normalize the distance by dividing it by the key size.
• Repeat the same for at least 4-5 blocks.
• Take the average of the calculated distances.
• Keep the top three best-performing key sizes that have the lowest hamming distance.

Note: We can calculate the hamming distance by XORing the two strings and counting the number of ones in the resulting string.

Example

Let's look at an example below to understand the calculation of Hamming distance in step 1:

The diagram below demonstrates calculating the Hamming distance between block one and block two in detail:

Step 2

Now that we have the top three key sizes, repeat the following procedure for all key sizes:

• Split the cipher text into blocks of length equal to the key size.
• Transpose the blocks and make new blocks out of them
• Each new block should have the exact positioned cipher text from the previous block.
• Break single byte key XOR encryption for the new blocks.
• Concatenate the single byte keys to get the primary key used for encryption.
• Repeat the steps for all candidate keys.

The illustration below depicts the steps with a key size of three:

Step 3

Decrypt the text and give it a score on the basis of alphabet recurrence using letter frequency.Number of times a character appears in written language. Repeat the same procedure for all the top three keys identified in step 1.

The key that achieves the highest English score is most probable to be the encryption key.