TUCTF 2018: XORient Write up — XOR Basics

XOR is one of the most basic and widely used operations in cryptography so I thought that this write up is a good opportunity to give an overview of how XOR is used as an encryption primitive and how it can be cracked.

First of all, lets see why the XOR operation is so popular in cryptography in contrast with AND, OR, NOT operations. There are two fundamental reasons for that:

1. XOR does not leak information about the plaintext

More specifically, if I have a random variable with random distribution A and XOR it with another random variable with a uniform distribution, then the result will also have a uniform distritbution. In other words, the probability of getting a specific value at any certain point will be the same for all values.

2. It is reversible

Another very nice property of the XOR operation is that it is reversible. That is, if I have a message M and xor it with key K of the same length, then if I XOR it again with K, I will end up with my original message which is somewhat handy when encrypting/decrypting stuff isn’t it?

Here is a handy list of XOR’s properties for future reference:

Now that we covered the basics of XOR let’s go back to the CTF challenge. We have been given a file called encrypted and also the source used to encrypt the file with:

From that, it is easy to see that there is a msg read from a file that is XORed with a key which is repeated across the whole message. Simple enough. Plus, there are some interesting assertions on lines 15,16 that give us some useful information about the key.

We know that:

1. Key is alphanumeric,
2. It has a length of 9 characters
3. Message contains “TUCTF”

Solving the challenge

Now given the XOR properties above we can exploit the information that we have been provided to find the key. Since we know the TUCTF is in the plaintext message, I will go one step further and guess that TUCTF{ is in the message as this is the standard prefix of the flag.

With this information we can start XOR the encrypted message in a sliding window manner with text “TUCTF{“ and examine the result. If it is alphanumeric we know that the result is a candidate key.

I went ahead and did that using the script below:

This yielded the following candidate keys:

Luckily that list of candidates is not that large but we still need to find the rest 3 remaining characters of the key ( Remember key length was 9). One way to do that would be to try all the keys and bruteforce the remaining 3 slots with alphanumeric characters and print the result only when the message contains only printable characters.

HOWEVER! There is one candidate key here that really caught my attention! It starts with “XORISC” so my guess was that this is probably the key. It wasn’t hard to also guess the remaining 3 characters which would be ‘OOL’ resulting to the key “XORISCOOL”.

Therefore, I XORed the message with that key and without much surprise I got the plaintext message:

Hope you are enjoying TUCTF! This is a challenge designed to get you oriented with how XOR works.

Here’s your flag: TUCTF{XOR_1$_V3RY_U$3FUL_T0_CRYPT0}

Tada!! That’s the flag over there. Hope you enjoyed the write up guys. You can find the files and solution script in my github repository below:

apogiatzis/ctf-writeups