Aperi’CTF 2019 - Double Trouble

Challenge details

Event	Challenge	Category	Points	Solves
Aperi’CTF 2019	Double Trouble	Cryptography	250	2

Vous avez été mandaté par la société ENO.corp pour analyser le logiciel de chiffrement des backups développé par un de leurs meilleurs stagiaires.

Votre mission est de trouver les vulnérabilités cryptographiques présentes dans son code et les exploiter pour déchiffrer ce fichier de backup.

Fichiers :
- crypt.py - md5sum: 7349cc9656477d97de63a406bf743320
- flag.txt.zip.enc - md5sum: 282e839cd962fc1ed416f8d4578b87d4

TL;DR

It was a double RC4 Meet-In-The-Middle attack.

Identifying the flaws

The encryption process is the following : 1. Generate a 8 bytes nonce 2. Derive 2 keys from the nonce and the 6 bytes masterkey 3. Encrypt the file with the RC4 keystream derived from the first subkey 4. Encrypt the file again with the RC4 keystream derived from the second subkey 5. Append the nonce at the beginning of the encrypted data and write the result to a file

Let’s take a closer look at step 2.

Subkey derivation process

The code for the subkey derivation looks wierd :

def genSubkeys(nonce):
    s1 = ""
    for i in range(3):
        s1 += nonce[3*i:3*(i+1)]+secret.KEY[i]
    s2 = ""
    for i in range(3):
        s2 += nonce[::-1][3*i:3*(i+1)]+secret.KEY[i+3]
    return s1, s2

Let’s see what the output would be with known values :

secret.KEY = "ABCDEF"
nonce = "12345678"

Output :

('123A456B78C', '876D543E21F')

You’ll notice that in every subkey we have only 3 bytes that are unknown because the nonce is known.

Additionnaly, we know that the file was a Zip file. Thus we know the first 4 bytes of the plaintext.

With this two informations combined we can perform a meet-in-the-middle attack !

MITM

The principle of the attack is to split the encryption process in two stages that can be threated separately.

Because we have knowledge over the plaintext, we can construct a table with all possible results of the first round of encryption. 3 bytes to brute-force is doable.

Because we have the ciphertext in our possession, we can decrypt it with all possible values of the second subkey (again 3 bytes too brute-force) and then compare with the table found previously for the same intermediate results.

If we find the same intermediate result, we have found a potential masterkey that will produce the plaintext we know. There will be multiple matching masterkeys because we only knew 4 bytes of the plaintext, but it will drastically reduce the number of possible masterkeys to test.

Full script available here

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
import pickle
import itertools
import zipfile
import string

def rc4(key, text):
    def KSA(key):
        key_length = len(key)
        S = range(256)
        j = 0
        for i in range(256):
            j = (j + S[i] + key[i % key_length]) % 256
            S[i], S[j] = S[j], S[i]  # swap values
        return S

    def PRGA(S):
        i = 0
        j = 0
        while True:
            i = (i + 1) % 256
            j = (j + S[i]) % 256
            S[i], S[j] = S[j], S[i]
            K = S[(S[i] + S[j]) % 256]
            yield K

    def get_keystream(key):
        S = KSA(key)
        return PRGA(S)

    keyBytes = [ord(c) for c in key]
    keystream = get_keystream(keyBytes)
    r = ""
    for c in text:
        r += chr(ord(c) ^ next(keystream))
    return r

def genSubkeys(nonce):
    s1 = ""
    for i in range(3):
        s1 += nonce[3*i:3*(i+1)]+KEY[i]
    s2 = ""
    for i in range(3):
        s2 += nonce[::-1][3*i:3*(i+1)]+KEY[i+3]
    return s1, s2

if __name__ == "__main__":
    # open the encrypted file
    f = open("flag.txt.zip.enc", "r").read()
    nonce = f[:8]
    data = f[8:]
    magic = "PK\x03\x04"

    print("Starting attack, this takes about 2 minutes to complete")
    save = "save.bin"
    # attempt to load saved progress
    table = {}
    print("Attempting to load progress...")
    try:
        table = pickle.load(file(save, "r"))
    except:
        table = {}
    if table == {}:
        print("Generating first table...")
        # generate first table
        for t in itertools.product(string.printable, repeat=3):
            KEY = "".join(t) + "AAA"
            subkey1, _ = genSubkeys(nonce)
            encrypted = rc4(subkey1, magic)
            table[encrypted] = KEY
        # save in a file for later in case a mistake was made so we don't have to recalculate this step
        pickle.dump(table, file(save,"w"))

    # search for matching candidates
    print("Searching for matches... (progress saved)")
    # values = list(table.values())
    # keys = list(table.keys())
    for t in itertools.product(string.printable, repeat=3):
        KEY = "AAA" + "".join(t)
        _, subkey2 = genSubkeys(nonce)
        decrypted = rc4(subkey2, data[:4])
        value = table.get(decrypted)
        if value:
            # index = values.index(decrypted)
            KEY = value[:3] + KEY[3:]
            # match found attempt to decrypt whole file
            s1, s2 = genSubkeys(nonce)
            decryptedZip = data
            decryptedZip = rc4(s1, decryptedZip)
            decryptedZip = rc4(s2, decryptedZip)
            open("flag.zip", "w").write(decryptedZip)
            try:
                zip_ref = zipfile.ZipFile("flag.zip", "r")
                zip_ref.extractall(".")
                zip_ref.close()
                print("Solution found, key = "+repr(KEY))
                print(open("flag.txt", "r").read())
                break
            except:
                pass

Output:

Starting attack, this takes about 2 minutes to complete
Attempting to load progress...
Generating first table...
Searching for matches... (progress saved)
Solution found, key = 'l9Js/}'
APRK{Th4t's_A_M33t_1n_tH3_m1dd1e_4774ck!}

Flag

APRK{Th4t's_A_M33t_1n_tH3_m1dd1e_4774ck!}

ENOENT