HM74
7 minutes to read
We are given this Verilog hardware description code:
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
We also have an online instance to connect to:
$ nc 165.232.100.46 31734
Captured: 1001100011100101010011001000110100111110110001111011001111001101110000010011110111011000011101110101001011111111000111010101111000010110010000001111011100110011011101000100001110111100011111000011000001100000000100110100010110010111000011010011011111111100110110100111001010010000110011010110011100011011100101011000011001000111010001111000101110100110000110100100110011111110110001111101101110000111100001010011000001000100101011111111001111001011110010110011001010010001100001001010110111111001110100000010011110000101001110000111111111100010101100100111010111011111100110010111110011000100100111111000000011000110010011011100001000011100001001001111111111010111011100001000011100110111001101010001110010010101011111110001101001001101010110110001100110010100101111101110000100001111010010111111111000111100111000000111011111100001110000111000110101011011101011010011010010111111111110110110011001011001111100110011110011011001011001100100011110010101
Captured: 1011000111100001101011001110100110110010100011110011000111001100110011110011010111011101110001100101001011111111000111101011011001011010101000111011101100110001011011000110001110101000111011000010100001100100011100010011010110001110000011010010110101010100110111100100011100010011110011010100011000010110110101011111011001110111010010111000011110100011110110101011010010011111111000111000100010010110100100010111101001010011101111101111101011000011100001110111001000010001011001011000111011100011110000110001111111100010010110001111000110101010001100110010111111000101000111001111100011000100101111111111100111001100110011001101001010111101001100001010011101110010010110001000010100110001100101010110111010011111011000110001000111001100000110100000110110011110111111011100000110101011010010111111011110001100110001001011110111100101110100111100101101011011001110100111010010111110110100110010010011001100110100100001110011001111011100000110011111000101
Captured: 1011100101000101001011001100100100001011000001101010001111001101010000010011110111111101100101010001001011111111000110010011111000011110100101010111001100100010011110000101101110010110011111001000101001000000001101010101010110000110100111111011110111111101110111110100001100010111110011011010111101011110100100011111011001000111111000100100011010100011010100000100010010111111110101111011100110000110010000010011100001010100101110101111101101101011001000110011001111111001111101001011011111100001110010110001011111000010000010000111000111101010100000110100000111111111101111010111110111010100101111111100011111010111110011011100010001001101011101011100011110110001001100001010011100000011001101010101110101010101000100110010100011111000010010100001100110010111101111110100000010000111110110111111111000011101110001001010111111100001100000111100110001011001000101100000010011101111011100110100110011011110111011100001110011000000011000100100011011000100
Captured: 0011101111001001001110001100101110001001100001111111001100001000110000110011001101011100100100110101011011000111001111000011111100001010100100011111001000110011011100000110111111111100011111000011100001100000001110110111010100000011111011110011111111111000010110100111011100011010010011001010011000011110100100011111011001000101110100101000011110000110001110100100010110111111110001111011101011100111000000100111101001010100101111111111010001000101101111110011011101110001011011011011111111100001110000100000010111000100000111101111000010101000101110010011000111000100000001000110111011000100111111000110000110011111010001001100001000011101011101001111101110000010011100000000101100100010010101001100110010011101111100110001111110101100010110110001100110000100000101111100000110001101010010111111001100010101110001001011111101100011110100111100111001001011000101010011010010101110111101100010001111000100111111101011110011000101011001100110111111111101
Captured: 1001100111000001001011101101000010101010100101111010001111001101100000111001010111110001110001110001011011110110000111100010011000111011110100111111000111110011011111011000100111111100011011000011001011110000001100110111010111011111000001011111111111111100110100000111101011011110111010111010011000011111100001011111011001000111110001110110011110100000001100110101010010111011111010111101100110000110000001000111100011010100101101111101101111001110000101110001001101111001111010000011111110100001110000110000101011010010010110101011100011001011101110100100101110011101001011000111110011001100001111110010100011101110011011011100011010111100000101001011111111110011111110000010010000100101001101010101110011000001001100110001011111101100010111010001001110101110101111110100000101000111010010110111111000011110110011101001101010100011110000111100100001011011001101111011110000111111111111010110011111001100110100100001100011000000011001100100111111010111
Captured: 0000110111101011000011001100100110001010100001111011001011001101111000100010000101011100110101010001001011111111110111010110111000111110100100011111001100110110011101001000111111111110001010010011101001110000001100111101010110001111000000010010111111011000110110100111001100010110010001110010011000011011100100011010011000000111111100101000001001100110000110100101010000111111100001101001001100000101000010000111101001101110111111110011001100001011100011110010101100100001111001001011111111101001110000110000111111000010000110001111001100101010000100110110100111011101010011001111110001000100100111111110001010010110110001001101101000011100001110001111111110100010010101001010011000111011110101110101110011010000111100110011100111001101110100100001100110010100101111111110010110111110110010111111111000011100011100001011101011110001010000111101110001010011100101000011000111111011111100110110000000101100110010100011110011001000011001100100011101010101
Plus, this is the description of the challenge:
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?
Understanding the challenge
We can assume that the remote instance is running a hardware device (probably an FPGA) with the above Verilog description. Also, we can guess that the device is always trying to send us the flag in binary format. However, due to a noisy channel, we have some errors when receiving and decoding the information.
Therefore, we must find a way to correct the errors and recover the information.
Hardware description analysis
The Verilog file implements an encoder that given 4 bits of information, outputs 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} $$
This type of encoding is known as Hamming code. In particular, this implementation is Hamming(7, 4) (that’s why the name of the challenge is “HM74”). These Hamming codes allow receivers to detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors.
Initial approach
At first, we forgot about Hamming codes and all the theory behind and used a statistical approach. The thing is that the set of valid 7-bit chunks is limited (actually, only 16 are valid, since there are only 16 possible entries). So, what we did is find a truth table and see if any 7-bit chunk was equal to one of the values on the truth table:
$ 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
At this point, we can create a Python script that receives samples from the remote instance and prints the matching 4-bit input when a 7-bit chunk appears in the above truth table:
#!/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
If we run the script, we will get the 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
The full script can be found in here: solve.py.
Intended way
The intended way to solve this challenge is to apply properties of Hamming codes to detect and correct errors. There’s a lot of theory and algebra behind these codes (more information at Wikipedia).
For instance, we will take the first 7-bit chunk received in the above output: 1001100. Now we will define the parity check matrix $H$ for this Hamming code:
$$ 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} $$
Now we need to multply this matrix by the 7-bit chunk as column vector (modulo $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} $$
As a result, we can be sure that 1001100 was transmitted correctly, in fact, 0100 -> 1001100.
Let’s see this chunk: 1011100 (from the third output):
$$ \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} $$
Since 110 in reverse order is 011, which is 3 in decimal, the bit at position 3 needs to be flipped (this is intentionally made by design). So we have:
$$ \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} $$
So, we have corrected one error and the correct information that was transmitted is 1001100, and again, 0100 -> 1001100.
This method is only successful if there is only 1 error per codeword. Although Hamming(7, 4) can detect up to 2 errors, there is no way to differentiate between codewords with 1 error or 2 errors, so using the correction method might give wrong results. Therefore, the probabilistic approach works better this time.