Saturday, March 4, 2017

Repeated XOR

Problem

There's a secret passcode hidden in the robot's "history of cryptography" module. But it's encrypted! Here it is, hex-encoded: encrypted.txt. Can you find the hidden passcode?

Hint

Like the title suggests, this is repeating-key XOR. You should try to find the length of the key - it's probably around 10 bytes long, maybe a little less or a little more.

Answer

Overview

Preform Kasiski elimination to find the key length. For this problem, the keylength is 8. Since the cipher text is encrypted using repeateing xor, you can do a frequency analysis on the 0th, 8th, 16th characters, and then another one on the 1st, 9th, and 17th characters, adn then on the 2nd, 10th, and 18th character.

Details

About repeated XOR

In a repeating XOR cipher, if the key is shorter than the message (it almost always is), the key is duplicated in order to cover the whole message. Then each byte of the plain text is XORed with each according byte of the key. For example, suppose we are trying to encrypt the message 'THIS IS A MESSAGE', with the key 'YOU', we first convert all of the characters to integers using ASCII encoding. (More examples may be found on the Wikipedia page)
T   H   I   S       I   S       A       M   E   S   S   A   G   E
84, 72, 73, 83, 32, 73, 83, 32, 65, 32, 77, 69, 83, 83, 65, 71, 69
Then we duplicate the key and convert it to an integer sequence.
Y   O   U   Y   O   U   Y   O   U   Y   O   U   Y   O   U   Y   O
89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79
Then we XOR the integers together.
84, 72, 73, 83, 32, 73, 83, 32, 65, 32, 77, 69, 83, 83, 65, 71, 69
89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79, 85, 89, 79
xor --------------------------------------------------------------
13,  7, 28, 10,111, 28, 10,111, 20,121,  2, 16, 10, 28, 20, 30, 10
Do you notice the repeating 28, 10, 111? That is because there was a repeat in the paintext that was a multiple of the keylength apart. In reality, repeats happen quite frequently, but it is just as likely to get a repeat 3 characters apart as it is to get one 4 characters apart. If they are 4 characters apart, a repeat is not shown in the cipher text, because the length of the offset (4) is not a multiple of the key length (3). For example, encrypting 'THIS MESSAGE IS NOT' with the key 'YOU' gives:

Cielo e terra (duet with Dante Thomas)