Tsayaki
6 minutos de lectura
Se nos proporciona el código fuente del servidor en Python:
from tea import Cipher as TEA
from secret import IV, FLAG
import os
ROUNDS = 10
def show_menu():
print("""
============================================================================================
|| I made this decryption oracle in which I let users choose their own decryption keys. ||
|| I think that it's secure as the tea cipher doesn't produce collisions (?) ... Right? ||
|| If you manage to prove me wrong 10 times, you get a special gift. ||
============================================================================================
""")
def run():
show_menu()
server_message = os.urandom(20)
print(f'Here is my special message: {server_message.hex()}')
used_keys = []
ciphertexts = []
for i in range(ROUNDS):
print(f'Round {i+1}/10')
try:
ct = bytes.fromhex(input('Enter your target ciphertext (in hex) : '))
assert ct not in ciphertexts
for j in range(4):
key = bytes.fromhex(input(f'[{i+1}/{j+1}] Enter your encryption key (in hex) : '))
assert len(key) == 16 and key not in used_keys
used_keys.append(key)
cipher = TEA(key, IV)
enc = cipher.encrypt(server_message)
if enc != ct:
print(f'Hmm ... close enough, but {enc.hex()} does not look like {ct.hex()} at all! Bye...')
exit()
except:
print('Nope.')
exit()
ciphertexts.append(ct)
print(f'Wait, really? {FLAG}')
if __name__ == '__main__':
run()
Este reto es una especie de la segunda parte de Iced TEA, porque el servidor también usa Tiny Encryption Algorithm (TEA).
Análisis del código fuente
El servidor nos da un texto claro y nos pide un texto cifrado y cuatro claves de cifrado distintas de manera que las cuatro cifren el texto claro y den como resultado el texto cifrado que pusimos:
$$ \mathrm{key}_1 \ne \mathrm{key}_2 \ne \mathrm{key}_3 \ne \mathrm{key}_4 $$
$$ \mathrm{TEA}(\mathrm{key}_1)(\mathrm{pt}) = \mathrm{ct} $$
$$ \mathrm{TEA}(\mathrm{key}_2)(\mathrm{pt}) = \mathrm{ct} $$
$$ \mathrm{TEA}(\mathrm{key}_3)(\mathrm{pt}) = \mathrm{ct} $$
$$ \mathrm{TEA}(\mathrm{key}_4)(\mathrm{pt}) = \mathrm{ct} $$
Claves equivalentes
Después de buscar un poco, descubrimos que TEA tiene un total de 4 claves equivalentes (más información en crypto.stackexchange.com). Se puede encontrar una explicación más formal en la Sección 2.5 de este artículo.
La clave está en el algoritmo de key schedule (tomado de Iced TEA):
def encrypt_block(self, msg):
m0 = b2l(msg[:4])
m1 = b2l(msg[4:])
K = self.KEY
msk = (1 << (self.BLOCK_SIZE//2)) - 1
s = 0
for i in range(32):
s += self.DELTA
m0 += ((m1 << 4) + K[0]) ^ (m1 + s) ^ ((m1 >> 5) + K[1])
m0 &= msk
m1 += ((m0 << 4) + K[2]) ^ (m0 + s) ^ ((m0 >> 5) + K[3])
m1 &= msk
m = ((m0 << (self.BLOCK_SIZE//2)) + m1) & ((1 << self.BLOCK_SIZE) - 1) # m = m0 || m1
return l2b(m)
En el TEA, la clave está formada por 16 bytes, que se divide en 4 claves de 4 bytes cada una (K[0], K[1], K[2] y K[3]).
En cada una de las 32 rondas del bucle for anterior, hay operaciones XOR que involucran K[0] y K[1] en una instrucción, y luego K[2] y K[3] en otra instrucción.
Debido a las propiedades de XOR y los números involucrados, podemos complementar los bits más significativos de K[0] y K[1] y lograr el mismo resultado, porque $0 \oplus 0 = 1 \oplus 1 = 0$. Lo mismo sucede con K[2] y K[3].
Podemos probarlo de la siguiente manera (usando la solución de Iced TEA):
$ python3 -q
>>> from os import urandom
>>> from tea import Cipher as TEA
>>>
>>> pt = urandom(16)
>>>
>>> key1 = int('0' + '0' * 31 + '0' + '0' * 31 + '0' + '0' * 31 + '0' + '0' * 31, 2).to_bytes(16, 'big')
>>> key2 = int('0' + '0' * 31 + '0' + '0' * 31 + '1' + '0' * 31 + '1' + '0' * 31, 2).to_bytes(16, 'big')
>>> key3 = int('1' + '0' * 31 + '1' + '0' * 31 + '0' + '0' * 31 + '0' + '0' * 31, 2).to_bytes(16, 'big')
>>> key4 = int('1' + '0' * 31 + '1' + '0' * 31 + '1' + '0' * 31 + '1' + '0' * 31, 2).to_bytes(16, 'big')
>>>
>>> TEA(key1).encrypt(pt) == TEA(key2).encrypt(pt) == TEA(key3).encrypt(pt) == TEA(key4).encrypt(pt)
True
Entonces, en lugar de usar un relleno de 31 bits a cero, podemos usar bits aleatorios, de modo que no se repita ninguna clave.
Implementación
En Python, podemos usar el siguiente código:
io = get_process()
rounds = io.progress('Round')
io.recvuntil(b'Here is my special message: ')
server_message = bytes.fromhex(io.recvline().decode())
for r in range(10):
rounds.status(f'{r + 1} / 10')
randoms = [''.join(choices('01', k=31)), ''.join(choices('01', k=31)), ''.join(choices('01', k=31)), ''.join(choices('01', k=31))]
key = int('0' + '0'.join(randoms), 2).to_bytes(16, 'big')
ct = TEA(key, IV).encrypt(server_message)
io.sendlineafter(b'Enter your target ciphertext (in hex) : ', ct.hex().encode())
for a, b, c, d in [[0, 0, 0, 0], [0, 0, 1, 1], [1, 1, 0, 0], [1, 1, 1, 1]]:
key = int(str(a) + randoms[0] + str(b) + randoms[1] + str(c) + randoms[2] + str(d) + randoms[3], 2).to_bytes(16, 'big')
io.sendlineafter(b'Enter your encryption key (in hex) : ', key.hex().encode())
rounds.success('10 / 10')
io.success(io.recvline().decode())
Sin embargo, todavía nos falta el IV. El servidor usa TEA en el modo CBC, pero el IV es fijo (se importa desde un módulo secret).
Esto es fácil de resolver, porque cuando nos conectamos al servidor y enviamos un texto cifrado incorrecto, el servidor mostrará cuál debía ser el texto de cifrado correcto:
print(f'Hmm ... close enough, but {enc.hex()} does not look like {ct.hex()} at all! Bye...')
Dado que proporcionamos la clave, simplemente ciframos el texto claro dado con un IV a cero y luego intentamos descifrar el texto cifrado usando modo CBC:
Como el servidor cifra con un IV fijo, el primer bloque de texto claro será diferente del que el servidor nos dio inicialmente (porque el IV a cero es incorrecto). Para obtener el IV correcto, solo necesitamos hacer el XOR con el bloque de texto claro descifrado y el bloque de texto claro dado:
io = get_process()
io.recvuntil(b'Here is my special message: ')
server_message = bytes.fromhex(io.recvline().decode())
key = b'asdf' * 4
IV = b'\0' * 8
io.sendlineafter(b'Enter your target ciphertext (in hex) : ', b'00' * 20)
io.sendlineafter(b'Enter your encryption key (in hex) : ', key.hex().encode())
io.recvuntil(b'Hmm ... close enough, but ')
ct = bytes.fromhex(io.recvuntil(b' ', drop=True).decode())
IV = xor(server_message[:8], TEA(key, IV).decrypt(ct)[:8])
io.close()
Flag
Entonces, si ejecutamos el script, obtendremos la flag:
$ python3 solve.py 94.237.58.188:51318
[+] Opening connection to 94.237.58.188 on port 51318: Done
[*] Closed connection to 94.237.58.188 port 51318
[+] Opening connection to 94.237.58.188 on port 51318: Done
[+] Round: 10 / 10
[+] Wait, really? HTB{y0u_b3tt3r_n0t_us3_t34_f0r_h4sh1ng}
[*] Closed connection to 94.237.58.188 port 51318
El script completo se puede encontrar aquí: solve.py.