SU-CTF 2014 - Cryptography 100 - Huge key

Brute-force the key of a weak AES encryption implementation and decrypt the message.

Introduction

This is a write-up about one of the Sharif University CTF cryptography challenge. The goal of this challenge was to recover the original content of an AES encrypted file.

Context

We were given two files, the PHP script below which was used to encipher the flag and ciphertext.bin which the IV concatenated with the encrypted flag.
The PHP script encipher the flag with Rijndael which is the algorithm used in AES, used functions are part of the mcrypt library.

<?php
    $plaintext = file_get_contents("flag.txt");

    $key = "\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0\x0";
    $hugekey = file_get_contents("hugekey.bin");
    foreach (str_split($hugekey, 2) as $block)
        for ($j = 0; $j < 2; $j++)
            $key[$j] = chr(ord($block[$j]) ^ ord($key[$j]));

    $iv_size = mcrypt_get_iv_size(MCRYPT_RIJNDAEL_128, MCRYPT_MODE_CBC);
    $iv = mcrypt_create_iv($iv_size, MCRYPT_RAND);

    $ciphertext = mcrypt_encrypt(MCRYPT_RIJNDAEL_128, $key, $plaintext, MCRYPT_MODE_CBC, $iv);

    $ciphertext = $iv . $ciphertext;
    file_put_contents("ciphertext.bin", $ciphertext);
?>

The flaw inside AES key generation

The flaw lies in the foreach loop, each iteration only the first two bytes of the key are XORed.
This leave us with an AES key with mostly NULL bytes in it. All we have to do to decrypt the flag is to brute-force the first two bytes.

Brute force AES key with python

We created a small Python script to brute-force the solution.

#!/usr/bin/env python
from Crypto import Random
from Crypto.Cipher import AES

iv = "\x8C\xAE\x65\x24\xA8\x63\xE3\x0F\x9B\x9D\x8D\xA2\xED\x05\xAA\x48"
ciphertext = "\x16\xD0\x7A\x30\x8E\x24\xED\xF8\xE7\x71\x57\x03\xC5\x74\xB6\xE3\x26\x40\x56\xE7\xE9\x56\xCF\x76\x61\xBD\x72\xE3\xC7\xFC\x6C\x15\x27\x3D\x2A\xED\xA6\xB6\xEA\x04\xF1\xCC\xFE\xF6\x77\xB4\x41\x66"


def decrypt(key):
    cipher = AES.new(key, AES.MODE_CBC, iv)
    result = cipher.decrypt(ciphertext)
    return result

def brute():
    for i in range(256):
        for j in range(256):
            key = "".join([chr(j), chr(i)]).ljust(16, "\x00")
            result = decrypt(key)
            if "flag" in result:
                print(result)
                print("key :", key.encode("hex"))
                return

if __name__ == "__main__":
    brute()