AHS512
5 minutos de lectura
Se nos proporciona el código fuente en Python del servidor:
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()
Básicamente, el servidor utiliza una función de hash personalizada (ahs512) y nos piden encontrar una colisión con el hash que nos dan:
$ 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:
El mensaje original es este:
original_message = b"pumpkin_spice_latte!"
original_digest = ahs512(original_message).hexdigest()
Análisis de la función de hash
La función de hash personalizada crea una clave aleatoria así:
def generateKey(self):
while True:
key = randint(2, len(self.message) - 1)
if len(self.message) % key == 0:
break
return key
Básicamente, la clave es un número aleatorio entre 2 y la longitud del mensaje de entrada, que es un intervalo pequeño.
Al llamar al método hexdigest, el hash se calcula:
def hexdigest(self):
transposed = self.transpose(self.message)
rotated = self.rotate(transposed)
return sha512(bytes(rotated)).hexdigest()
Como se puede observar, al final de la función se calcula el hash SHA512, pero la entrada se transpone y rota.
Trasposición
Esta es la función 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)
Básicamente, mezcla los caracteres. Podemos verlo en el REPL de Python:
$ 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!'
Probablemente haya una manera de ordenar los caracteres del mensaje original y que transpose lo ordene como se ordenó el hash original. Sin embargo, yo resolví el reto de otra manera.
Rotación
Esta es la función rotate:
def rotate(self, message):
return [((b >> 4) | (b << 3)) & 0xff for b in message]
La función anterior realiza operaciones a nivel de bit en cada carácter del mensaje traspuesto. Por ejemplo, vamos a coger el carácter p, que es ASCII 0x70, o 0111 0000 en binario. La función rotate dará como resultado 0000 0111 | 1000 000 = 1000 0111.
Encontrando el fallo
El problema es que hay caracteres ASCII que darán el mismo resultado después de rotate. Vamos a usar letras en vez de bits. Digamos que nuestro carácter es ABCD EFGH en binario. Entonces, rotate hará 0000 ABCD | DEFG H000 = DEFG XBCD, donde aparece un nuevo valor X = A | H. Por tanto, si X es 1, tenemos tres posibilidades: A = H = 1, A = 0; H = 1 y A = 1; H = 0.
Por ejemplo, podemos coger el guion bajo _, que es 0x5f en hexadecimal, o 0101 1111 en binario. Como A = 0 y H = 1, sabemos que X = 1, por lo que podemos poner A = 1 y obtener el mismo resultado. Esto implica reemplazar cada _ por \xdf (en binario, 1101 1111).
Y esto es lo que vamos a hacer. Luego, enviaremos el mismo mensaje al servidor varias veces hasta que encontremos la flag. Recordemos que la clave es diferente en cada iteración, pero en un intervalo corto, por lo que aplicar fuerza bruta es asequible:
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
Si ejecutamos el script anterior, obtendremos la 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{5h4512_8u7_w17h_4_7w157_83f023_c4n_93n32473_c0111510n5}
El script completo se puede encontrar aquí: solve.py.