InCTF 2017- GiantXOR Writeup

Author: s0rc3r3r

Points: 250

Standard Encryption but can you break it?

Intended Solution

This challenge is a little bit tricky as compared to other crypto tasks. The text is encrypted using Repeating Key XOR, but instead of encrypting the normal plaintext, the function first encodes the message in base64 and then encrypts using Repeated Key XOR.

The first step to break the encryption is to get the key length used for encryption. You can either write a script for yourself or use a tool of mine for this. The tool gives the most probable key length using the concept of Index of Coincidence. You can check it out here: https://github.com/ashutosh1206/Crypta-Tools/blob/master/RepeatingKeyXOR/exploit.py

I gave the input ciphertext and got the following results:

As you can see, the most probable length of the key is 12 (Since the Index of Coincidence is maximum for 12). We will test taking this key length into consideration.

The next step is to get the value of the key. We can do it by exhaustive search (brute force) but let’s do it the optimal way, I wrote a function for doing a relatively faster exhaustive search. We already know from the encryption script that key only contains printable characters – whitespaces. So, it narrows down our exhaustive search but not much. The idea for a faster search is to check inside each loop whether the key character being XORed is giving a plaintext output that contains base64’ed characters or not. This will significantly reduce the decryption time required to get the value of the key.

Here is the entire exploit where I have implemented the above idea:

import string

def multiplyKey(ct, k):
    while len(k) < len(ct):
        k += k
    k = k[:len(ct)]
    return k

def decrypt(ciphertext, k):
    ciphertext = ciphertext.decode("hex")
    k = multiplyKey(ciphertext, k)
    plaintext = ""
    for i in range(len(ciphertext)):
        plaintext += chr(ord(ciphertext[i]) ^ ord(k[i]))
    return plaintext

def check_keychar_validity(ciphertext, keychar, index = 0, keylength = 12):
    key = "\x00"*index + keychar + "\x00"*(keylength-index-1)
    pt = decrypt(ciphertext, key)
    for i in range(index, len(pt), keylength):
        if pt[i] not in base64str:
            return False
    return True

# From the Index of Coincidence, we know that the most probable keylength is 12
# We also know that the keylength contains all printable characters excluding whitespaces
ciphertext = open("ciphertext.txt").read().strip()
base64str = string.ascii_letters + string.digits + "=+/" + "\n"
key_chars = string.printable + string.whitespace

def fast_exhaustive_srch(ciphertext, sub_block):
    key = ""
    for i in key_chars:
        if check_keychar_validity(ciphertext, i, sub_block, 12):
            key += i
            for j in key_chars:
                if check_keychar_validity(ciphertext, j, sub_block+1, 12):
                    key += j
                    for k in key_chars:
                        if check_keychar_validity(ciphertext, k, sub_block+2, 12):
                            key += k
                            for l in key_chars:
                                if check_keychar_validity(ciphertext, l, sub_block+3, 12):
                                    key += l
                                else:
                                    continue
                        else:
                            continue
                else:
                    continue
        else:
            continue
    return key

# Generating the entire key
key = ""
for i in range(0, 12, 4):
    key += fast_exhaustive_srch(ciphertext, i)
print decrypt(ciphertext, key).decode("base64")

This will give the output as: I hope this was a fun challenge. Adding base64 encoding before a repeated key XOR really made things a bit more difficult, or did it? Btw, Congrats on solving the challenge! Good work! Here is your flag: inctf{base64_d1d_4ll_7he_m4g1c_right?}

The script takes less than a second to give the output which is quite less as compared to brute-forcing directly.