CryptoScripting +325 points

12 months ago - 150 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
from Crypto.Util.Padding import pad
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)
    ct = cipher.encrypt(pad(data, 16))
    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:
        dt = json.loads(input().strip())
        pt = bytes.fromhex(dt['pt'])
        res = encrypt(pt, k1, k2)
        print(res + '\n')
        exit(1)
    except Exception as e:
        print(e)
        print('Invalid payload.\n')
        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
Encrypt your text:
> {"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
from Crypto.Util.Padding import pad
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)
    middle = cipher.encrypt(pad(real_plaintext, 16))

    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}