Challenge

Weakened Keys

400 points

Local politicians and their anti crypto opinions have forced us to dumb down our AES encryption. It’s OK because we think we can still use these weakened keys and still encrypt our message securely by encrypting it twice. Have a look at our code and see what you think.

sample_encrypted_base64 = '0mu0T97looX5/Oorw8ASGxfqMqrNoFajZupXrjtIAj7ECJdQXZzEmbEwdRV2J2MI'

sample_plaintext = 'Double AES encryption for twice the strength.Win'

flag_encrypted_base64 = 'lIZMVkA+pbiOxh3nNdV2bWz3gXovIy4fG7yCHa5FT44='

Hint: our keys only include printable ASCII characters

File: doubleAES.zip

What do we know?

Let’s read the doubleAES.py file:

 1import hashlib
 2import base64
 3from Crypto.Cipher import AES
 4from Crypto.Random import get_random_bytes
 5
 6# set the flag value to some secret message
 7flag = 'Double AES encryption for twice the strength.Win'
 8
 9data = flag.encode('utf-8')
10
11# Local political concerns about strong encryption,
12# means first 224 bits of all keys have been set to 0.
13
14# temp keys for testing
15key1 = get_random_bytes(32) 
16key2 = get_random_bytes(32)
17
18iv = hashlib.md5(b"infernoCTF").digest()
19
20# === Encrypt ===
21cipher_encrypt = AES.new(key1, AES.MODE_CBC, iv=iv)
22ciphertext = cipher_encrypt.encrypt(data)
23
24# === Defeat weakenend keys by encrypting again ===
25cipher_encrypt = AES.new(key2, AES.MODE_CBC, iv=iv)
26ciphered_bytes = cipher_encrypt.encrypt(ciphertext)
27
28print(base64.b64encode(ciphered_bytes))

We have the following information:

data is encrypted two times using AES in CBC mode
keys are 32 bytes long, but the first 224 bits have been set to 0, making them 4 bytes long in practice
keys only include printable ASCII characters (32-126)
we assume the initial vector is the md5 hash of b'infernoCTF'

My first approach was just to brute-force both keys, making all possible permutations with the printable ASCII characters. However, after hours of frustration, I was not able to solve the challenge. After the CTF ended, I asked for a little nudge and was able to solve it performing a meet-in-the-middle attack (MITM).

We can read from the Wikipedia page:

Source: Wikipedia

Assume someone wants to attack an encryption scheme with the following characteristics for a given plaintext P and ciphertext C:

$$ C = \mathit{ENC}_{k_2}(\mathit{ENC}_{k_1}(P)) $$ $$ P = \mathit{DEC}_{k_1}(\mathit{DEC}_{k_2}(C)) $$

where $\mathit{ENC}$ is the encryption function, $\mathit{DEC}$ the decryption function defined as $\mathit{ENC}^{−1}$ (inverse mapping) and $k_1$ and $k_2$ are two keys.

The naive approach at brute-forcing this encryption scheme is to decrypt the ciphertext with every possible $k_2$, and decrypt each of the intermediate outputs with every possible $k_1$, for a total of $2^{k_1} \times 2^{k_2}$ (or $2^{k_1+k_2}$) operations.

The meet-in-the-middle attack uses a more efficient approach. By decrypting C with $k_2$, one obtains the following equivalence:

$$ C = \mathit{ENC}_{k_2}(\mathit{ENC}_{k_1}(P)) $$ $$ \iff \mathit{DEC}_{k_2}(C) = \mathit{DEC}_{k_2}(\mathit{ENC}_{k_2}[\mathit{ENC}_{k_1}(P)]) $$ $$ \iff \mathit{DEC}_{k_2}(C) = \mathit{ENC}_{k_1}(P) $$

The attacker can compute $\mathit{ENC}_{k_1}(P)$ for all values of $k_1$ and $\mathit{DEC}_{k_2}(C)$ for all possible values of $k_2$, for a total of $2^{k_1} + 2^{k_2}$ (or $2^{k_1+1}$, if $k_1$ and $k_2$ are the same size) operations. If the result from any of the $\mathit{ENC}_{k_1}(P)$ operations matches a result from the $\mathit{DEC}_{k_2}(C)$ operations, the pair of $k_1$ and $k_2$ is possibly the correct key. This potentially-correct key is called a candidate key.

After reading this, I made the following script:

 1#!/usr/bin/python3
 2import hashlib
 3import base64
 4import itertools
 5from Crypto.Cipher import AES
 6
 7# Meet in the middle attack
 8
 9encrypted_message = "0mu0T97looX5/Oorw8ASGxfqMqrNoFajZupXrjtIAj7ECJdQXZzEmbEwdRV2J2MI"
10encrypted_message = base64.b64decode(encrypted_message)
11message = b"Double AES encryption for twice the strength.Win"
12iv = hashlib.md5(b"infernoCTF").digest()
13
14# Get all printable ASCII chars
15printable_ascii_chars = []
16for i in range(32, 127):
17    printable_ascii_chars.append(i)
18
19prefix = b'0000000000000000000000000000'
20
21# Write all possible keys using permutations in a file
22with open('keys_output.txt', 'w') as fk:
23    for i in itertools.permutations(printable_ascii_chars, 4):
24        fk.write(f"{(prefix + bytes(list(i))).decode()}\n")
25
26with open('enc_output.txt', 'w') as fe:
27    for i in itertools.permutations(printable_ascii_chars, 4):
28        m = hashlib.new('md5')
29        kf = prefix + bytes(list(i))
30        cipher = AES.new(kf, AES.MODE_CBC, iv=iv)
31        m.update(cipher.encrypt(message))
32        fe.write(f"{m.hexdigest()}\n")
33
34with open('dec_output.txt', 'w') as fd:
35    for i in itertools.permutations(printable_ascii_chars, 4):
36        m = hashlib.new('md5')
37        kb = prefix + bytes(list(i))
38        cipher = AES.new(kb, AES.MODE_CBC, iv=iv)
39        m.update(cipher.decrypt(encrypted_message))
40        fd.write(f"{m.hexdigest()}\n")

After quite some time, we end up with 3 files:

keys_output.txt, with all the possible keys
enc_output.txt, which is $\mathit{md5}(\mathit{ENC}_{k_1}(P))$ for all values of $k_1$
dec_output.txt, which is $\mathit{md5}(\mathit{DEC}_{k_2}(C))$ for all values of $k_2$

Note:

I used the MD5 hash function in an attempt to reduce the weight of the files ($16$ bytes instead of $32$ bytes for each key) and increase the speed of the script.

Now what we need to do is:

find the common lines between enc_output.txt and dec_output.txt
find the line number where the content of common line is found in both files
retrieve the keys in the keys_output.txt file

Let’s do that with bash:

# Sorting the files to use comm
> sort enc_output.txt > enc_sorted.txt 
> sort dec_output.txt > dec_sorted.txt

> comm -12 enc_sorted.txt dec_sorted.txt # Finding common lines
982ee07b1b9d3540dae8a085999c2cfc

# Now we need to find where this hash is in both files and retreive the keys
> fgrep -n '982ee07b1b9d3540dae8a085999c2cfc' enc_output.txt
13015195:982ee07b1b9d3540dae8a085999c2cfc
> sed -n 13015195p keys_output.txt
0000000000000000000000000000021Q

> fgrep -n '982ee07b1b9d3540dae8a085999c2cfc' dec_output.txt
12943236:982ee07b1b9d3540dae8a085999c2cfc
> sed -n 12943236p keys_output.txt
00000000000000000000000000000(iA

We found the candidate keys:

$k_1$ = 0000000000000000000000000000021Q

$k_2$ = 00000000000000000000000000000(iA

Using a simple script we decode the flag:

 1#!/usr/bin/python3
 2import hashlib
 3import base64
 4import itertools
 5from Crypto.Cipher import AES
 6
 7encrypted_flag = "lIZMVkA+pbiOxh3nNdV2bWz3gXovIy4fG7yCHa5FT44="
 8encrypted_flag = base64.b64decode(encrypted_flag)
 9
10iv = hashlib.md5(b"infernoCTF").digest()
11
12key1 = b'0000000000000000000000000000021Q'
13key2 = b'00000000000000000000000000000(iA'
14
15cipher2 = AES.new(key2, AES.MODE_CBC, iv=iv)
16intermediate = cipher2.decrypt(encrypted_flag)
17cipher1 = AES.new(key1, AES.MODE_CBC, iv=iv)
18final = cipher1.decrypt(intermediate)
19print(final.decode())

> ./decode.py
infernoCTF{M33t_in_Th£_M1ddL3!}

>> Home

infernoCTF: Weakened Keys

2019/12/29

Challenge

Weakened Keys

400 points

What do we know?