CryptoScripting +325 points

8 months ago - 114 views

# Meet me halfway

This was a crypto challenge where the solution was a trick I had not seen before, so I looked online for writeups of similar challenges and found a very similar challenge (link to post). I used that trick in this challenge to solve it.

# The Challenge

We get a python script that gives us a ciphertext of the flag and allows us to encrypt our own text with the same generated key. This means that if the key is not very randomly generated, we could brute force lots of different keys until it matches our plaintext and ciphertext.
Here is the full script:

Python

``````from random import randint
from Crypto.Cipher import AES
import json

flag = b'HTB{dummyflag}'

def gen_key(option=0):
alphabet = b'0123456789abcdef'
const = b'[email protected]#'
key = b''
for i in range(16-len(const)):
key += bytes([alphabet[randint(0,15)]])

if option:  # 1
return key + const
else:  # 0
return const + key

def encrypt(data, key1, key2):
cipher = AES.new(key1, mode=AES.MODE_ECB)
cipher = AES.new(key2, mode=AES.MODE_ECB)
ct = cipher.encrypt(ct)
return ct.hex()

def challenge():
k1 = gen_key()   # Generate key with const prepended
k2 = gen_key(1)  # Generate key with const appended

ct = encrypt(flag, k1, k2)

print('Super strong encryption service approved by the elves X-MAS spirit.\n'+\
'Message for all the elves:\n' +ct + '\nEncrypt your text:\n> ')
try:
pt = bytes.fromhex(dt['pt'])
res = encrypt(pt, k1, k2)
print(res + '\n')
exit(1)
except Exception as e:
print(e)
exit(1)

if __name__ == "__main__":
challenge()``````

Two different keys are generated using the `gen_key()` function. The first key is generated with a constant value (`'[email protected]#'`) and 4 random hex characters appended. The second key also uses the constant value but with 4 other random hex characters prepended.
After that, the flag gets encrypted with both keys, in two separate AES ECB encryptions after one another. The ciphertext that this generated is printed to us. Then we get the option to encrypt our own text, in JSON and hex format. Example:

Text

``````Super strong encryption service approved by the elves X-MAS spirit.
Message for all the elves:
6ba6f2563bcebe82dd9813f277fe2df3
> {"pt": "48656c6c6f2c20776f726c6421"}
21b76ed84a740ef6867a4d613a06d659``````

## Brute force

The `gen_key()` function only adds 4 random hex characters to the known `const`. This means a single key can only be one of `16**4 = 65536` possibilities. Cracking this is very doable for a computer, so trying all possibilities for one key should be fine. The problem is the fact that the data is encrypted with two different keys, meaning we need to also know both keys to check if a ciphertext matches the plaintext. With the two keys combined the number of possible keys is `16**8 = 4294967296` which would take `(16**8) / 50000 = 85899` seconds (24 hours) if you could encrypt 50000 times per second. In a real scenario, this might be feasible, but since this is a CTF there must be another solution.

## Idea

I thought a lot about ways to see if only one key is correct, so you could brute force each key separately. The problem is that you don't know if single decryption was successful because the plaintext for that specific encryption was already randomized by the previous encryption, so you can't check if there are alphanumeric characters for example.

The trick here is the fact that we get a plaintext of our own, and the ciphertext for it. This means we can encrypt our plaintext with all possible `key1`'s, and save these middle values, then we can decrypt our ciphertext with all possible `key2`'s until any of those values are equal to the middle values we made with key1. This way we meet in the middle and know both keys it took to get there.
We are essentially doing the same amount of operations because for every `key2`, we need to check against every possible middle value for `key1`. The reason this is better is that we aren't encrypting every time. Simple string comparison is way faster than AES encrypting, and since we already know the plaintext of our own, we don't have to encrypt it every time, just once so we can re-use the middle values.

## Solution

First we'll initialize some variable we already know. We can use the `{"pt": "48656c6c6f2c20776f726c6421"}` from earlier as our plaintext. Putting this in the challenge program we get a ciphertext of `322cf03d32e927237269840a63acb96f`. We also get the ciphertext of the flag which is `1b0331b9aa44380aab7d0244c41f6a7b`. So the start of our script will be:

Python

``````from Crypto.Cipher import AES
import itertools

ALPHABET = b'0123456789abcdef'
CONST = b'[email protected]#'

flag_ciphertext = bytes.fromhex("1b0331b9aa44380aab7d0244c41f6a7b")
input = {"pt": "48656c6c6f2c20776f726c6421"}
real_plaintext = bytes.fromhex(input['pt'])
real_ciphertext = bytes.fromhex("322cf03d32e927237269840a63acb96f")``````

First, we need to generate all possible `key1`'s from `[email protected]#0000` to `[email protected]#ffff`. We can use `itertools.product` to generate all the possible combinations for this hex alphabet. Then just encrypt our plaintext with all these possible keys and save them to check later. These are all the possible middle values for our plaintext.

Python

``````possible_middles = {}  # {middle: key}

for key1 in itertools.product(ALPHABET, repeat=4):  # Generate all possible combinations
key1 = CONST + bytes(key1)
cipher = AES.new(key1, AES.MODE_ECB)

possible_middles[middle] = key1  # Save middle values with corresponding key``````

Then we can do the reverse for `key2`. We again generate all possible keys from `[email protected]#` to `[email protected]#`. Then we decrypt the ciphertext and check if this middle value is one we've seen with `key1`. If it is, that means this key2 was correct. Since we saved the key1 earlier we also now know what that is.

Python

``````for key2 in itertools.product(ALPHABET, repeat=4):
key2 = bytes(key2) + CONST
cipher = AES.new(key2, AES.MODE_ECB)
middle = cipher.decrypt(real_ciphertext)

if middle in possible_middles:
key1 = possible_middles[middle]  # key1 was saved as value
print(key1, key2)``````

Now that we know both keys, we can just decrypt the ciphertext, and also the flag because it used the same two keys.

Python

``````cipher1 = AES.new(key1, AES.MODE_ECB)
cipher2 = AES.new(key2, AES.MODE_ECB)
print(cipher1.decrypt(cipher2.decrypt(real_ciphertext)))
print(cipher1.decrypt(cipher2.decrypt(flag_ciphertext)))``````

Running this script gets us the dummy flag we set ourselves in the challenge script, but because we only used values it gave us we can start the remote server and give it the same plaintext. Putting the new ciphertexts in the script it tries all possible keys and finds them, and after decrypting prints us the flag!
`HTB{m337_m3_1n_7h3_m1ddl3_0f_3ncryp710n}`