# Double Trouble

Aperi'CTF 2019 - Cryptography (250 pts).

# 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
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 = {}
try:
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))
break
except:
pass


Output:

Starting attack, this takes about 2 minutes to complete

APRK{Th4t's_A_M33t_1n_tH3_m1dd1e_4774ck!}