<- CRYPTO

AbraCryptabra

15 minutes to read

We are provided with the server source code in Python:

from Crypto.Util.number import long_to_bytes, GCD
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import hashlib
import random
import socketserver
import signal
from secret import FLAG

LOGO = ("""
╭━━━┳╮╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╭╮╱╱╱╭╮
┃╭━╮┃┃╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╭╯╰╮╱╱┃┃
┃┃╱┃┃╰━┳━┳━━┳━━┳━┳╮╱╭┳━┻╮╭╋━━┫╰━┳━┳━━╮
┃╰━╯┃╭╮┃╭┫╭╮┃╭━┫╭┫┃╱┃┃╭╮┃┃┃╭╮┃╭╮┃╭┫╭╮┃
┃╭━╮┃╰╯┃┃┃╭╮┃╰━┫┃┃╰━╯┃╰╯┃╰┫╭╮┃╰╯┃┃┃╭╮┃
╰╯╱╰┻━━┻╯╰╯╰┻━━┻╯╰━╮╭┫╭━┻━┻╯╰┻━━┻╯╰╯╰╯
╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╭━╯┃┃┃
╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╰━━╯╰╯\n""")


class Handler(socketserver.BaseRequestHandler):

    def handle(self):
        signal.alarm(0)
        main(self.request)


class ReusableTCPServer(socketserver.ForkingMixIn, socketserver.TCPServer):
    pass


def sendMessage(s, msg):
    s.send(msg.encode())


def receiveMessage(s, msg):
    sendMessage(s, msg)
    return s.recv(4096).decode().strip()


def bytes_to_bits(input):
    return ''.join(format(i, '08b') for i in input)


class DisruptionSpell(object):

    def __init__(self, n):
        self.n = n

    def spawnScroll(self):
        intList = []
        intList.append(random.randint(1, self.n))
        sum = intList[0]

        for i in range(1, self.n):
            intList.append(random.randint(sum + 1, (sum + i) * 2))
            sum = sum + intList[i]

        x1 = random.randint(sum + 1, sum * 2)

        while True:
            x2 = random.randint(1, x1)
            if GCD(x2, x1) == 1:
                break

        scrollOfWorthiness = []

        for i in range(self.n):
            scrollOfWorthiness.append(x2 * intList[i] % x1)

        return scrollOfWorthiness

    def disrupt(self, scrollOfWorthiness, flag_bits):
        disruptedFlag = 0

        for i in range(len(flag_bits)):
            if int(flag_bits[i]) != 0: disruptedFlag += scrollOfWorthiness[i]

        return long_to_bytes(disruptedFlag).hex()


class Wizard:

    def __init__(self):
        self.magicka = 108314726549199134030277012155370097074
        self.armor = 31157724864730593494380966212158801467
        self.stamina = 32
        self.critChance = random.randint(1337, self.magicka - 1)
        self.spell = random.randint(1337, self.magicka - 1)

    def attack(self):
        self.spell = (self.armor * self.spell + self.critChance) % self.magicka
        spellAttack = self.spell >> (self.magicka.bit_length() - self.stamina)
        return spellAttack

    def dontAcceptDefeat(self, playerHealth, flag):
        flag = flag.lstrip('HTB{').rstrip('}')
        flag_bits = bytes_to_bits(flag.encode())

        distruptionSpell = DisruptionSpell(len(flag_bits))
        scrollOfWorthiness = distruptionSpell.spawnScroll()
        disruptedFlag = distruptionSpell.disrupt(scrollOfWorthiness, flag_bits)

        for _ in range(playerHealth):
            self.spell = (self.armor * self.spell +
                          self.critChance) % self.magicka

        finalSpellIngredient = str(self.spell >> (self.magicka.bit_length() -
                                                  self.stamina)).encode()
        finalSpellIngredient = hashlib.md5(finalSpellIngredient).digest()
        finalSpell = AES.new(finalSpellIngredient, AES.MODE_CBC)
        disruptedFlag = finalSpell.encrypt(
            pad("You're a wizard Harry, ".encode() + disruptedFlag.encode(),
                AES.block_size)).hex()

        return disruptedFlag, scrollOfWorthiness


def main(s):
    encryptionWizard = Wizard()
    playerHealth = 100
    wizardHealth = 200

    try:
        sendMessage(s, LOGO)
        sendMessage(s, " * The Basilisk is approaching... *\n")
        sendMessage(s, " - You think you're a wizard?")

        while playerHealth > 0 and wizardHealth > 0:
            block = receiveMessage(s, "\n > ")
            spellAttack = encryptionWizard.attack()
            if int(block) != spellAttack:
                playerHealth -= 1
                sendMessage(s, " - This is too easy...\n")
                sendMessage(s, str(spellAttack))
            else:
                wizardHealth -= 1
                sendMessage(s, " - You won't be so lucky next time!\n")

        if playerHealth <= 0:
            sendMessage(s, " - You can't even save your self!\n")
            s.close()
        else:
            disruptedFlag, scrollOfWorthiness = encryptionWizard.dontAcceptDefeat(
                playerHealth, FLAG)
            scrollOfWorthinessSize = len(scrollOfWorthiness)

            sendMessage(s, f"\n {str(scrollOfWorthinessSize)}\n")

            for i in scrollOfWorthiness:
                sendMessage(s, f"{str(i)}\n")

            sendMessage(s, f"{disruptedFlag}\n")

            s.close()

    except:
        try:
            sendMessage(s, "Unexpected error occured.\n")
            s.close()
        except:
            pass
        exit()


if __name__ == '__main__':
    socketserver.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer(("0.0.0.0", 1337), Handler)
    server.serve_forever()

The server simulates a game where we (as players) need to guess the number the wizard has generated. If our guess is correct, the wizard loses one health point; otherwise, we lose one health point:

$ nc 165.227.237.190 31839

╭━━━┳╮╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╭╮╱╱╱╭╮
┃╭━╮┃┃╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╭╯╰╮╱╱┃┃
┃┃╱┃┃╰━┳━┳━━┳━━┳━┳╮╱╭┳━┻╮╭╋━━┫╰━┳━┳━━╮
┃╰━╯┃╭╮┃╭┫╭╮┃╭━┫╭┫┃╱┃┃╭╮┃┃┃╭╮┃╭╮┃╭┫╭╮┃
┃╭━╮┃╰╯┃┃┃╭╮┃╰━┫┃┃╰━╯┃╰╯┃╰┫╭╮┃╰╯┃┃┃╭╮┃
╰╯╱╰┻━━┻╯╰╯╰┻━━┻╯╰━╮╭┫╭━┻━┻╯╰┻━━┻╯╰╯╰╯
╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╭━╯┃┃┃
╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╱╰━━╯╰╯
 * The Basilisk is approaching... *
 - You think you're a wizard?
 > 1234
 - This is too easy...
1053715130
 > 1337
 - This is too easy...
751145160
 >

Source code analysis

The guessing game is implemented in this while loop:

        while playerHealth > 0 and wizardHealth > 0:
            block = receiveMessage(s, "\n > ")
            spellAttack = encryptionWizard.attack()
            if int(block) != spellAttack:
                playerHealth -= 1
                sendMessage(s, " - This is too easy...\n")
                sendMessage(s, str(spellAttack))
            else:
                wizardHealth -= 1
                sendMessage(s, " - You won't be so lucky next time!\n")

And encryptionWizard.attack() is this method:

    def attack(self):
        self.spell = (self.armor * self.spell + self.critChance) % self.magicka
        spellAttack = self.spell >> (self.magicka.bit_length() - self.stamina)
        return spellAttack

The above expression is a Linear Congruential Generator (LCG):

However, the outputs are truncated. In the above expression, we already know (self.armor) and (self.magicka). These are the values:

    def __init__(self):
        self.magicka = 108314726549199134030277012155370097074
        self.armor = 31157724864730593494380966212158801467
        self.stamina = 32
        self.critChance = random.randint(1337, self.magicka - 1)
        self.spell = random.randint(1337, self.magicka - 1)

So, the problem here is that we are not given the outputs but the 32 most significant bits (self.stamina = 32). Let be the most significant bits of .

I found an excellent writeup from DownUnder CTF 2020 that involves a truncated LCG, but it is not exact for this challenge. However, it is a nice resource to learn more about LCG and lattice-based cryptanalysis.

Hidden Number Problem

Reading the code from crypto-attacks on truncated LCG, there is a function that tries to recover the LCG parameters from the outputs. Luckily, we already have and , so we would like to find and (the initial seed).

It is extremely hard to find the exact values of and , but notice that we are only interested in the most significant bits of to win the guessing game. So maybe, there is a way to find some values that give the expected results in the majority of rounds.

The code in crypto-attacks uses a lattice to find a solution to the Hidden Number Problem (but with two hidden numbers). This problem is usually stated as , where is the hidden number. This time, we can adapt it to , where we are interested in .

Let’s assume that we are taking 10 outputs from the game. So, let . Let be:

And let be:

Where is an upper-bound for . For instance, , where is the amount of bits hidden to us ( is the bit-length of and ).

Therefore,

If we operate the above matrices, we have this vector:

And simplifying a bit more, we have the following:

Summarizing, if we are able to solve the Hidden Number Problem, we will find (which are the hidden bits of ) and (the initial seed and the increment ).

The attack works by defining a lattice spanned by the columns of

Notice that the vector is in the lattice. Since it can be considered a short vector, we can use LLL to reduce the basis and see if it is within the new basis. Then, we will take the positions that correspond to and , which are the ones that are useful for the challenge.

For more information, you can read this paper and the code in crypto-attacks.

This is the implementation of this part of the challenge:

def do_round(io, guess=1337):
    io.sendlineafter(b'> ', str(guess).encode())
    io.recvline()

    if (r := io.recvline().decode()) != '\n':
        return int(r)


def hidden_number_problem(a, b, m, X):
    n1 = len(a)
    n2 = len(a[0])
    B = matrix(QQ, n1 + n2 + 1, n1 + n2 + 1)

    for i in range(n1):
        for j in range(n2):
            B[n1 + j, i] = a[i][j]

        B[i, i] = m
        B[n1 + n2, i] = b[i] - X // 2

    for j in range(n2):
        B[n1 + j, n1 + j] = X / QQ(m)

    B[n1 + n2, n1 + n2] = X

    B = B.LLL()

    for v in B.rows():
        xs = [int(v[i] + X // 2) for i in range(n1)]
        ys = [(int(v[n1 + j] * m) // X) % m for j in range(n2)]

        if all(y != 0 for y in ys) and v[n1 + n2] == X:
            return xs, ys


def crack_tlcg(yj, k, s, m, a):
    X = 2 ** (k - s)

    alpha = [[a, 1]]
    beta = [-X * y for y in yj]

    while len(alpha) < len(beta):
        alpha.append([alpha[-1][0] * a % m, (alpha[-1][1] * a + 1) % m])

    _, (s0, c) = hidden_number_problem(alpha, beta, m, X)
    return m, a, c, s0


class LCG:
    def __init__(self, m, a, s, c, s0):
        self.m = m
        self.a = a
        self.s = s
        self.c = c
        self.k = int(m).bit_length()
        self.state = s0

    def next(self):
        self.state = (self.a * self.state + self.c) % self.m
        return self.state >> (self.k - self.s)


def main():
    io = get_process()
    M, a = 108314726549199134030277012155370097074, 31157724864730593494380966212158801467
    k = int(M).bit_length()
    s = 32

    Y = [do_round(io) for _ in range(10)]

    _, _, c, s0 = crack_tlcg(Y, k, s, M, a)

    lcg = LCG(M, a, s, c, s0)

    try:
        for y in Y:
            assert y == lcg.next()
    except AssertionError:
        log.warning('LCG failed. Trying again...')
        io.close()
        main()

    log.success('LCG cracked')
    player_health, wizard_health = 90, 200

    prog = log.progress('Health')

    while wizard_health:
        prog.status(f'Player: {player_health} | Wizard {wizard_health}')

        if do_round(io, lcg.next()) is None:
            wizard_health -= 1
        else:
            player_health -= 1

    prog.success(f'Player: {player_health} | Wizard {wizard_health}')

Notice how we use 10 rounds to get the truncated LCG outputs and then make sure that the LCG parameters work. Otherwise, we start again.

Knapsack problem

When the wizard loses the game, he refuses to lose and encrypts the flag using AES. The key for this cipher is taken from the LCG doing the same amount of rounds as the player’s health points:

    def dontAcceptDefeat(self, playerHealth, flag):
        flag = flag.lstrip('HTB{').rstrip('}')
        flag_bits = bytes_to_bits(flag.encode())

        distruptionSpell = DisruptionSpell(len(flag_bits))
        scrollOfWorthiness = distruptionSpell.spawnScroll()
        disruptedFlag = distruptionSpell.disrupt(scrollOfWorthiness, flag_bits)

        for _ in range(playerHealth):
            self.spell = (self.armor * self.spell +
                          self.critChance) % self.magicka

        finalSpellIngredient = str(self.spell >> (self.magicka.bit_length() -
                                                  self.stamina)).encode()
        finalSpellIngredient = hashlib.md5(finalSpellIngredient).digest()
        finalSpell = AES.new(finalSpellIngredient, AES.MODE_CBC)
        disruptedFlag = finalSpell.encrypt(
            pad("You're a wizard Harry, ".encode() + disruptedFlag.encode(),
                AES.block_size)).hex()

        return disruptedFlag, scrollOfWorthiness

Since we have already cracked the LCG, we can find that key easily:

    for _ in range(player_health - 1):
        lcg.next()

    key = md5(str(lcg.next()).encode()).digest()
    cipher = AES.new(key, AES.MODE_CBC)

The wizard uses AES to encrypt this message: You're a wizard Harry, <enc_flag>. The mode of operation is AES CBC, with an unknown IV. However, this is not a problem, since only the first block will not decrypt correctly. The rest of the blocks will be correct:

    try:
        message = unpad(cipher.decrypt(enc_message), AES.block_size)
    except ValueError:
        log.warning('Padding error. Trying again...')
        main()

    log.info(f'Encrypted message: {message}')

    enc_flag = int(message.split(b'Harry, ')[1].decode(), 16)

We care about the number at <enc_flag>, which is the result of a knapsack encryption:

    def disrupt(self, scrollOfWorthiness, flag_bits):
        disruptedFlag = 0

        for i in range(len(flag_bits)):
            if int(flag_bits[i]) != 0: disruptedFlag += scrollOfWorthiness[i]

        return long_to_bytes(disruptedFlag).hex()

Particularly, it uses a Merkle-Hellman knapsack cryptosystem. Basically, it takes the object to be encrypted in binary format, multiplies each bit by the corresponding index of the public key and sums all the intermediate results (which are 32 numbers). Let be a sequence of and such that , where is the plaintext number to be encrypted. Then, the encrypted number is

Where is the public key configured by the server.

Before sending the AES-encrypted message, we are given the knapsack’s public key and the length of the flag in bits:

            disruptedFlag, scrollOfWorthiness = encryptionWizard.dontAcceptDefeat(
                playerHealth, FLAG)
            scrollOfWorthinessSize = len(scrollOfWorthiness)

            sendMessage(s, f"\n {str(scrollOfWorthinessSize)}\n")

            for i in scrollOfWorthiness:
                sendMessage(s, f"{str(i)}\n")

            sendMessage(s, f"{disruptedFlag}\n")

We will take all the parameters with this piece of code using a little trick:

    length = int(io.recvline().decode())
    log.info(f'Flag length: {length // 8}')
    public_key = []

    for i in range(length):
        if i % 8:
            public_key.append(int(io.recvline().decode()))
        else:
            io.recvline()

    enc_message = bytes.fromhex(io.recvline().decode())
    io.close()

Since the encrypted object is the flag, all characters are valid ASCII codes (less than 0x7f). Hence, the bits at index multiple of 8 will always be 0 (that’s why we omit adding those public key indices to the list).

At this point, we will solve the knapsack problem using a lattice-based attack with LLL (for more information on this technique, take a look at Infinite Knapsack):

def knapsack(a_i: List[int], b: int) -> int:
    M = matrix(ZZ, len(a_i) + 1, len(a_i) + 1)

    for i, a in enumerate(a_i):
        M[i, i] = 1
        M[i, -1] = a

    M[-1, -1] = -b

    B = M.LLL()

    for u_i in B.rows():
        if all(u in {0, 1} for u in u_i[:-1]) and b == sum(a * u for a, u in zip(a_i, u_i)):
            return u_i[:-1]


def bin2dec(b: List[int]) -> int:
    return int(''.join(map(str, b)), 2)

And once we get all the bits, we need to add the leading 0 that we skipped before:

    if (r := knapsack(public_key, enc_flag)):
        flag = [bin2dec([0, *r[i : i + 7]]) for i in range(0, len(r), 7)]
        log.success('HTB{' + ''.join(map(chr, flag)) + '}')
    else:
        log.warning('Knapsack failed. Trying again...')
        main()

Flag

Now we can join all parts and hope that the attack is successful:

$ python3 solve.py 139.59.184.45:30535
[+] Opening connection to 139.59.184.45 on port 30535: Done
[+] LCG cracked
[+] Health: Player: 74 | Wizard 0
[*] Flag length: 36
[*] Closed connection to 139.59.184.45 port 30535
[!] Padding error. Trying again...
[+] Opening connection to 139.59.184.45 on port 30535: Done
[+] LCG cracked
[+] Health: Player: 59 | Wizard 0
[*] Flag length: 36
[*] Closed connection to 139.59.184.45 port 30535
[*] Encrypted message: b'\xe9\xcb=\x81+&\x1c\x7f\x17\rS\x84\xd2\xec\x90\xbdHarry, 531241055385a8abb32946e08f3b84a8f891fe86d22d03d540cd0028b6ad738f3b802d05dc5eff2c6ddcb71bfdfa5216af'
[!] Knapsack failed. Trying again...
[+] Opening connection to 139.59.184.45 on port 30535: Done
[+] LCG cracked
[+] Health: Player: 74 | Wizard 0
[*] Flag length: 36
[*] Closed connection to 139.59.184.45 port 30535
[*] Encrypted message: b'\x07\x98}\x9c*\x1e\x99u\x0f\x07\x8ak\xbe\xa8\xc00Harry, 1600d8f64cd991497e4f47d4a4ab48abf25b04c0fa20be5a5da40ad956b4be17d51b023aabbea7d20ea4a12b73ecbc176f91'
[!] Knapsack failed. Trying again...
[+] Opening connection to 139.59.184.45 on port 30535: Done
[!] LCG failed. Trying again...
[*] Closed connection to 139.59.184.45 port 30535
[+] Opening connection to 139.59.184.45 on port 30535: Done
[+] LCG cracked
[+] Health: Player: 72 | Wizard 0
[*] Flag length: 36
[*] Closed connection to 139.59.184.45 port 30535
[*] Encrypted message: b':(B\x98\xd7\xa8|\xa8,\xb8\x14z\xfe\x07q\x9aHarry, 02a4c39eb0e2eea5e01fc259e630e06377275e81801cc21d8b5b3ab1b35e403eceeb0676a7dd5d9c0a4d7c9bff648beccbd4'
[+] HTB{2_14771c3_ch4113n935_837732_7h4n_0n3}

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