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.