HM74
7 minutos de lectura
Se nos proporciona este código de descripción de hardware en Verilog:
module encoder(
input [3:0] data_in,
output [6:0] ham_out
);
wire p0, p1, p2;
assign p0 = data_in[3] ^ data_in[2] ^ data_in[0];
assign p1 = data_in[3] ^ data_in[1] ^ data_in[0];
assign p2 = data_in[2] ^ data_in[1] ^ data_in[0];
assign ham_out = { p0, p1, data_in[3], p2, data_in[2], data_in[1], data_in[0] };
endmodule
module main;
wire[3:0] data_in = 5;
wire[6:0] ham_out;
encoder en(data_in, ham_out);
initial begin
#10;
$display("%b", ham_out);
end
endmodule
También tenemos una instancia remota para conectarnos:
$ nc 165.232.100.46 31734
Captured: 1001100011100101010011001000110100111110110001111011001111001101110000010011110111011000011101110101001011111111000111010101111000010110010000001111011100110011011101000100001110111100011111000011000001100000000100110100010110010111000011010011011111111100110110100111001010010000110011010110011100011011100101011000011001000111010001111000101110100110000110100100110011111110110001111101101110000111100001010011000001000100101011111111001111001011110010110011001010010001100001001010110111111001110100000010011110000101001110000111111111100010101100100111010111011111100110010111110011000100100111111000000011000110010011011100001000011100001001001111111111010111011100001000011100110111001101010001110010010101011111110001101001001101010110110001100110010100101111101110000100001111010010111111111000111100111000000111011111100001110000111000110101011011101011010011010010111111111110110110011001011001111100110011110011011001011001100100011110010101
Captured: 1011000111100001101011001110100110110010100011110011000111001100110011110011010111011101110001100101001011111111000111101011011001011010101000111011101100110001011011000110001110101000111011000010100001100100011100010011010110001110000011010010110101010100110111100100011100010011110011010100011000010110110101011111011001110111010010111000011110100011110110101011010010011111111000111000100010010110100100010111101001010011101111101111101011000011100001110111001000010001011001011000111011100011110000110001111111100010010110001111000110101010001100110010111111000101000111001111100011000100101111111111100111001100110011001101001010111101001100001010011101110010010110001000010100110001100101010110111010011111011000110001000111001100000110100000110110011110111111011100000110101011010010111111011110001100110001001011110111100101110100111100101101011011001110100111010010111110110100110010010011001100110100100001110011001111011100000110011111000101
Captured: 1011100101000101001011001100100100001011000001101010001111001101010000010011110111111101100101010001001011111111000110010011111000011110100101010111001100100010011110000101101110010110011111001000101001000000001101010101010110000110100111111011110111111101110111110100001100010111110011011010111101011110100100011111011001000111111000100100011010100011010100000100010010111111110101111011100110000110010000010011100001010100101110101111101101101011001000110011001111111001111101001011011111100001110010110001011111000010000010000111000111101010100000110100000111111111101111010111110111010100101111111100011111010111110011011100010001001101011101011100011110110001001100001010011100000011001101010101110101010101000100110010100011111000010010100001100110010111101111110100000010000111110110111111111000011101110001001010111111100001100000111100110001011001000101100000010011101111011100110100110011011110111011100001110011000000011000100100011011000100
Captured: 0011101111001001001110001100101110001001100001111111001100001000110000110011001101011100100100110101011011000111001111000011111100001010100100011111001000110011011100000110111111111100011111000011100001100000001110110111010100000011111011110011111111111000010110100111011100011010010011001010011000011110100100011111011001000101110100101000011110000110001110100100010110111111110001111011101011100111000000100111101001010100101111111111010001000101101111110011011101110001011011011011111111100001110000100000010111000100000111101111000010101000101110010011000111000100000001000110111011000100111111000110000110011111010001001100001000011101011101001111101110000010011100000000101100100010010101001100110010011101111100110001111110101100010110110001100110000100000101111100000110001101010010111111001100010101110001001011111101100011110100111100111001001011000101010011010010101110111101100010001111000100111111101011110011000101011001100110111111111101
Captured: 1001100111000001001011101101000010101010100101111010001111001101100000111001010111110001110001110001011011110110000111100010011000111011110100111111000111110011011111011000100111111100011011000011001011110000001100110111010111011111000001011111111111111100110100000111101011011110111010111010011000011111100001011111011001000111110001110110011110100000001100110101010010111011111010111101100110000110000001000111100011010100101101111101101111001110000101110001001101111001111010000011111110100001110000110000101011010010010110101011100011001011101110100100101110011101001011000111110011001100001111110010100011101110011011011100011010111100000101001011111111110011111110000010010000100101001101010101110011000001001100110001011111101100010111010001001110101110101111110100000101000111010010110111111000011110110011101001101010100011110000111100100001011011001101111011110000111111111111010110011111001100110100100001100011000000011001100100111111010111
Captured: 0000110111101011000011001100100110001010100001111011001011001101111000100010000101011100110101010001001011111111110111010110111000111110100100011111001100110110011101001000111111111110001010010011101001110000001100111101010110001111000000010010111111011000110110100111001100010110010001110010011000011011100100011010011000000111111100101000001001100110000110100101010000111111100001101001001100000101000010000111101001101110111111110011001100001011100011110010101100100001111001001011111111101001110000110000111111000010000110001111001100101010000100110110100111011101010011001111110001000100100111111110001010010110110001001101101000011100001110001111111110100010010101001010011000111011110101110101110011010000111100110011100111001101110100100001100110010100101111111110010110111110110010111111111000011100011100001011101011110001010000111101110001010011100101000011000111111011111100110110000000101100110010100011110011001000011001100100011101010101
Además, esta es la descripción del reto:
As you venture further into the depths of the tomb, your communication with your team becomes increasingly disrupted by noise. Despite their attempts to encode the data packets, the errors persist and prove to be a formidable obstacle. Fortunately, you have the exact Verilog module used in both ends of the communication. Will you be able to discover a solution to overcome the communication disruptions and proceed with your mission?
Comprendiendo el reto
Podemos suponer que la instancia remota está ejecutando un dispositivo hardware (probablemente una FPGA) con la descripción de Verilog anterior. Además, podemos deducir que el dispositivo siempre está tratando de enviarnos la flag en formato binario. Sin embargo, debido a un canal ruidoso, tenemos algunos errores al recibir y decodificar la información.
Por lo tanto, debemos encontrar una manera de corregir los errores y recuperar la información.
Análisis de la descripción de hardware
El archivo de Verilog implementa un codificador que dados 4 bits de información, emite 7 bits:
$$ \mathrm{en}\left(\begin{bmatrix} d_4 \\ d_3 \\ d_2 \\ d_1 \end{bmatrix}\right) = \begin{bmatrix} p_1 \\ p_2 \\ d_4 \\ p_3 \\ d_3 \\ d_2 \\ d_1 \end{bmatrix} = \begin{bmatrix} d_1 \oplus d_3 \oplus d_4 \\ d_1 \oplus d_2 \oplus d_4 \\ d_4 \\ d_1 \oplus d_2 \oplus d_3 \\ d_3 \\ d_2 \\ d_1 \end{bmatrix} $$
Este tipo de codificación se conoce como código de Hamming. En particular, esta implementación es Hamming(7, 4) (es por eso que el nombre del reto es “HM74”). Estos códigos de Hamming permiten que los receptores detecten errores de uno o dos bits, o corregir errores en un bit.
Planteamiento inicial
Al principio, no usamos la propiedades de los códigos de Hamming y toda la teoría detrás y utilizamos un enfoque estadístico. La cuestión es que el conjunto de fragmentos válidos de 7 bits es limitado (en realidad, solo 16 son válidos, ya que solo hay 16 entradas posibles). Entonces, lo que hicimos es encontrar una tabla de verdad y ver si algún trozo de 7 bits era igual a uno de los valores en la tabla de verdad:
$ python3 -q
>>> def en(d4, d3, d2, d1):
... p1 = d1 ^ d3 ^ d4
... p2 = d1 ^ d2 ^ d4
... p3 = d1 ^ d2 ^ d3
... return ''.join(map(str, [p1, p2, d4, p3, d3, d2, d1]))
...
>>> from itertools import product
>>>
>>> for d4, d3, d2, d1 in product(*[range(2)] * 4):
... print(f'{d4}{d3}{d2}{d1} -> {en(d4, d3, d2, d1)}')
...
0000 -> 0000000
0001 -> 1101001
0010 -> 0101010
0011 -> 1000011
0100 -> 1001100
0101 -> 0100101
0110 -> 1100110
0111 -> 0001111
1000 -> 1110000
1001 -> 0011001
1010 -> 1011010
1011 -> 0110011
1100 -> 0111100
1101 -> 1010101
1110 -> 0010110
1111 -> 1111111
>>>
>>> for d4, d3, d2, d1 in product(*[range(2)] * 4):
... print(f'{en(d4, d3, d2, d1)} -> {d4}{d3}{d2}{d1}')
...
0000000 -> 0000
1101001 -> 0001
0101010 -> 0010
1000011 -> 0011
1001100 -> 0100
0100101 -> 0101
1100110 -> 0110
0001111 -> 0111
1110000 -> 1000
0011001 -> 1001
1011010 -> 1010
0110011 -> 1011
0111100 -> 1100
1010101 -> 1101
0010110 -> 1110
1111111 -> 1111
En este punto, podemos crear un script en Python que reciba muestras de la instancia remota e imprima la entrada de 4 bits coincidente cuando aparece un fragmento de 7 bits en la tabla de verdad anterior:
#!/usr/bin/env python3
from collections import Counter
from pwn import log, remote, sys
truth_table = {
'0000000': '0000',
'1101001': '0001',
'0101010': '0010',
'1000011': '0011',
'1001100': '0100',
'0100101': '0101',
'1100110': '0110',
'0001111': '0111',
'1110000': '1000',
'0011001': '1001',
'1011010': '1010',
'0110011': '1011',
'0111100': '1100',
'1010101': '1101',
'0010110': '1110',
'1111111': '1111',
}
host, port = sys.argv[1].split(':')
io = remote(host, port)
def get_chunks():
io.recvuntil(b'Captured: ')
data = io.recvline().strip().decode()
return [data[i : i + 7] for i in range(0, len(data), 7)]
flag = ''
binary_flag = ''
io.info('Collecting samples...')
samples = [get_chunks() for _ in range(50)]
prog = log.progress('Flag')
while '}' not in flag:
characters = Counter()
for chunks in samples:
chunk = chunks[len(binary_flag) // 4]
if chunk in truth_table:
characters[truth_table.get(chunk)] += 1
if len(characters):
binary_flag += characters.most_common()[0][0]
else:
io.info('Collecting more samples...')
samples = [get_chunks() for _ in range(50)]
if len(binary_flag) % 8 == 0:
flag = bytes.fromhex(hex(int(binary_flag, 2))[2:]).decode()
prog.status(flag)
prog.success(flag)
Flag
Si ejecutamos el script conseguiremos la flag:
$ python3 solve.py 165.232.100.46:31734
[+] Opening connection to 165.232.100.46 on port 31734: Done
[*] Collecting samples...
[+] Flag: HTB{hmm_w1th_s0m3_ana1ys15_y0u_c4n_3x7ract_7h3_h4mmin9_7_4_3nc_fl49}
[*] Closed connection to 165.232.100.46 port 31734
El script completo se puede encontrar aquí: solve.py.
Vía intencionada
La vía intencionada de resolver este reto es aplicar las propiedades de los códigos de Hamming para detectar y corregir errores. Hay mucha teoría y álgebra detrás de estos códigos (más información en Wikipedia).
Por ejemplo, tomaremos el primer fragmento de 7 bits recibido en la salida anterior: 1001100. Ahora definiremos la matriz de verificación de paridad $H$ para este código de Hamming:
$$ H = \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} $$
Ahora necesitamos multiplicar esta matriz por el fragmento de 7 bits como vector columna (módulo $2$):
$$ \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 2 \\ 0 \\ 2 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} $$
Como resultado, podemos estar seguros de que 1001100 fue transmitido correctamente, de hecho, 0100 -> 1001100.
Veamos este trozo: 1011100 (de la tercera salida):
$$ \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} $$
Como 110 en orden inverso es 011, que es 3 en decimal, el bit en la posición 3 necesita ser invertido. Entonces tenemos:
$$ \begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 0 \\ \color{yellow}{0} \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} $$
Entonces, hemos corregido un error y la información correcta que se transmitió es 1001100, y de nuevo, 0100 -> 1001100.
Este método solo es exitoso si solo hay 1 error por palabra de código. Aunque Hamming(7, 4) puede detectar hasta 2 errores, no hay manera de diferenciar entre palabras de código con 1 error o con 2 errores, por lo que usar el método de corrección puede dar resultados incorrectos. Por lo tanto, el enfoque probabilístico funciona mejor esta vez.