SPG

3 minutes to read

We are given the Python source code used to encrypt the flag:

from hashlib import sha256
import string, random
from secret import MASTER_KEY, FLAG
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from base64 import b64encode

ALPHABET = string.ascii_letters + string.digits + '~!@#$%^&*'

def generate_password():
    master_key = int.from_bytes(MASTER_KEY, 'little')
    password = ''

    while master_key:
        bit = master_key & 1
        if bit:
            password += random.choice(ALPHABET[:len(ALPHABET)//2])
        else:
            password += random.choice(ALPHABET[len(ALPHABET)//2:])
        master_key >>= 1

    return password

def main():
    password = generate_password()
    encryption_key = sha256(MASTER_KEY).digest()
    cipher = AES.new(encryption_key, AES.MODE_ECB)
    ciphertext = cipher.encrypt(pad(FLAG, 16))

    with open('output.txt', 'w') as f:
        f.write(f'Your Password : {password}\nEncrypted Flag : {b64encode(ciphertext).decode()}')  

if __name__ == '__main__':
    main()

And we also have the output of the script:

Your Password : t*!zGnf#LKO~drVQc@n%oFFZyvhvGZq8zbfXKvE1#*R%uh*$M6c$zrxWedrAENFJB7xz0ps4zh94EwZOnVT9&h  
Encrypted Flag : GKLlVVw9uz/QzqKiBPAvdLA+QyRqyctsPJ/tx8Ac2hIUl8/kJaEvHthHUuwFDRCs

Source code analysis

Basically, the script takes a secret value MASTER_KEY and generates a password based on it. Then, the value of MASTER_KEY is used to derive an AES key using SHA256 to encrypt the flag. That’s what we have in main:

def main():
    password = generate_password()
    encryption_key = sha256(MASTER_KEY).digest()
    cipher = AES.new(encryption_key, AES.MODE_ECB)
    ciphertext = cipher.encrypt(pad(FLAG, 16))

    with open('output.txt', 'w') as f:
        f.write(f'Your Password : {password}\nEncrypted Flag : {b64encode(ciphertext).decode()}')

Therefore, the objective is to find out the value of MASTER_KEY, so that we can derive the same AES key and decrypt the ciphertext.

To achieve this, we must use the generated password, which comes from generate_password:

def generate_password():
    master_key = int.from_bytes(MASTER_KEY, 'little')
    password = ''

    while master_key:
        bit = master_key & 1
        if bit:
            password += random.choice(ALPHABET[:len(ALPHABET)//2])  
        else:
            password += random.choice(ALPHABET[len(ALPHABET)//2:])
        master_key >>= 1

    return password

As can be seen, it takes the bits of MASTER_KEY (interpreted as a little-endian integer) to choose a random character from ALPHABET:

ALPHABET = string.ascii_letters + string.digits + '~!@#$%^&*'

The key point is that if the bit is 1, the character is taken randomly from the first half of ALPHABET, whereas if the bit is 0, the character is taken from the second half.

Solution

The idea is to take the generated password one character at a time and determine if it belongs to the first or the second half of ALPHABET. As a result, we will know if the coresponding bit of MASTER_KEY is set to 1 or 0.

We can implement a simple algorithm to crack the password and find MASTER_KEY:

def crack_password(password):
    master_key = 0

    for i, p in enumerate((password)):
        if p in ALPHABET[:len(ALPHABET) // 2]:
            master_key |= 1 << i

    return master_key.to_bytes((7 + len(password)) // 8, 'little')

Now we can use this main function to find MASTER_KEY and decrypt the ciphertext:

def main():
    password = 't*!zGnf#LKO~drVQc@n%oFFZyvhvGZq8zbfXKvE1#*R%uh*$M6c$zrxWedrAENFJB7xz0ps4zh94EwZOnVT9&h'  
    ciphertext = 'GKLlVVw9uz/QzqKiBPAvdLA+QyRqyctsPJ/tx8Ac2hIUl8/kJaEvHthHUuwFDRCs'
    MASTER_KEY = crack_password(password)
    encryption_key = sha256(MASTER_KEY).digest()
    cipher = AES.new(encryption_key, AES.MODE_ECB)

    print(unpad(cipher.decrypt(b64decode(ciphertext)), AES.block_size).decode())

Flag

If we run the script, we will get the flag:

$ python3 solve.py
HTB{m4ll34bl3_p4ssw0rd_g3n3r4t0r!}

The full script can be found in here: solve.py.