AHS512

5 minutes to read

We got the Python source code of the server:

from secret import FLAG
from hashlib import sha512
import socketserver
import signal
from random import randint

WELCOME = """
**************** Welcome to the Hash Game. ****************
*                                                         *
*    Hash functions are really spooky.                    *
*    In this game you will have to face your fears.       *
*    Can you find a colision in the updated sha512?       *
*                                                         *
***********************************************************
"""


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()


class ahs512():

    def __init__(self, message):
        self.message = message
        self.key = self.generateKey()

    def generateKey(self):
        while True:
            key = randint(2, len(self.message) - 1)
            if len(self.message) % key == 0:
                break

        return key

    def transpose(self, message):
        transposed = [0 for _ in message]

        columns = len(message) // self.key

        for i, char in enumerate(message):
            row = i // columns
            col = i % columns
            transposed[col * self.key + row] = char

        return bytes(transposed)

    def rotate(self, message):
        return [((b >> 4) | (b << 3)) & 0xff for b in message]

    def hexdigest(self):
        transposed = self.transpose(self.message)
        rotated = self.rotate(transposed)
        return sha512(bytes(rotated)).hexdigest()


def main(s):
    sendMessage(s, WELCOME)

    original_message = b"pumpkin_spice_latte!"
    original_digest = ahs512(original_message).hexdigest()
    sendMessage(
        s,
        f"\nFind a message that generate the same hash as this one: {original_digest}\n"  
    )

    while True:
        try:
            message = receiveMessage(s, "\nEnter your message: ")
            message = bytes.fromhex(message)

            digest = ahs512(message).hexdigest()

            if ((original_digest == digest) and (message != original_message)):
                sendMessage(s, f"\n{FLAG}\n")
            else:
                sendMessage(s, "\nConditions not satisfied!\n")

        except KeyboardInterrupt:
            sendMessage(s, "\n\nExiting")
            exit(1)

        except Exception as e:
            sendMessage(s, f"\nAn error occurred while processing data: {e}\n")


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

Basically, the server uses a custom hashing function (AHS512) and we are asked to find a collision with a given hash:

$ nc 134.122.106.203 32713

**************** Welcome to the Hash Game. ****************
*                                                         *
*    Hash functions are really spooky.                    *
*    In this game you will have to face your fears.       *
*    Can you find a colision in the updated sha512?       *
*                                                         *
***********************************************************

Find a message that generate the same hash as this one: 94650ece878870dd2e6a62addeabb803c6b5a49223d47c8e4b91073b0ffee8dd2b57eec03d8f616742792e4c7f5f671fa46f8eb97a4840a5ea03f2f2beeabc35  

Enter your message:

The original message is this one:

    original_message = b"pumpkin_spice_latte!"
    original_digest = ahs512(original_message).hexdigest()

Analyzing the hash function

The custom hash function creates a random key as follows:

    def generateKey(self):
        while True:
            key = randint(2, len(self.message) - 1)  
            if len(self.message) % key == 0:
                break

        return key

Basically, the key is a random number between 2 and the length of the input message, which is a short interval.

When calling the hexdigest method, the actual hash is computed:

    def hexdigest(self):
        transposed = self.transpose(self.message)  
        rotated = self.rotate(transposed)
        return sha512(bytes(rotated)).hexdigest()

As can be seen, at the very end the function computes the SHA512 hash, however the input was transposed and rotated before.

Transposition

This is transpose:

    def transpose(self, message):
        transposed = [0 for _ in message]

        columns = len(message) // self.key

        for i, char in enumerate(message):
            row = i // columns
            col = i % columns
            transposed[col * self.key + row] = char  

        return bytes(transposed)

Basically, it shuffles the characters. We can check it with the Python REPL:

$ python3 -q
>>> from server import ahs512
>>> original_message = b"pumpkin_spice_latte!"
>>> ahs512(original_message).transpose(original_message)  
b'piiaunctm_etps_ekpl!'
>>> ahs512(original_message).transpose(original_message)
b'piucmep_kliant_tsep!'
>>> ahs512(original_message).transpose(original_message)
b'piiaunctm_etps_ekpl!'
>>> ahs512(original_message).transpose(original_message)
b'piiaunctm_etps_ekpl!'
>>> ahs512(original_message).transpose(original_message)
b'pksetuip_tmnilep_ca!'
>>> ahs512(original_message).transpose(original_message)
b'piiaunctm_etps_ekpl!'
>>> ahs512(original_message).transpose(original_message)
b'piucmep_kliant_tsep!'
>>> ahs512(original_message).transpose(original_message)
b'pmknsielteupi_pc_at!'

Probably, there’s a way to sort the characters of the original message so that after transpose, they have the same ordering as the original message’s hash. However, I took another approach.

Rotation

This is rotate:

    def rotate(self, message):
        return [((b >> 4) | (b << 3)) & 0xff for b in message]

The above function performs some bit operations on each character of the transposed message. For instance, let’s take character p, which is ASCII 0x70, or 0111 0000 in binary. The rotate function will output 0000 0111 | 1000 000 = 1000 0111.

Finding the flaw

The thing here is that there are ASCII characters that get the same result after rotate. Let’s use letters instead of bits. Let’s say our character is ABCD EFGH in binary. Then, rotate will do 0000 ABCD | DEFG H000 = DEFG XBCD, where there’s a new value X = A | H. Therefore, if X is set to 1, then we have three possibilities: A = H = 1, A = 0; H = 1 and A = 1; H = 0.

For example, we can take the underscore _, which is 0x5f in hexadecimal, or 0101 1111 in binary. Since A = 0 and H = 1, we know that X = 1, so, we can set A = 1 and obtain the same result. That is, replace each _ by \xdf (in binary, 1101 1111).

So that’s what we are going to do. Then, we will send the same message to the server until we find the flag. Recall that the key is different for each iteration, although the interval is short, so we can do a bit of brute force:

def main():
    host, port = sys.argv[1].split(':')
    p = remote(host, int(port))

    p.recvuntil(b'Find a message that generate the same hash as this one: ')  
    target = p.recvline().strip().decode()
    original_message = b"pumpkin_spice_latte!"

    message = original_message.replace(b'_', b'\xdf')
    p.sendlineafter(b'Enter your message: ', message.hex().encode())
    p.recvline()
    answer = p.recvline()

    while b'Conditions not satisfied!' in answer:
        p.sendlineafter(b'Enter your message: ', message.hex().encode())
        p.recvline()
        answer = p.recvline(2)

    p.close()
    print(answer.decode().strip())

Flag

If we execute the above script, we will find the flag:

$ python3 solve.py 134.122.106.203:32713
[+] Opening connection to 134.122.106.203 on port 32713: Done  
[*] Closed connection to 134.122.106.203 port 32713
HTB{533_7h47_w45n'7_50_5c42y_4f732_411}

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