ictf voyager

20 Apr 2025

More details

In this challenge, we are tasked with inputting expr_1 and expr_2 strings. They have to be in the form set([i for i in "1234567890a+-*&|^ ()<>"]).

• For each initial from 0 to 15,
  • We set a = initial then encoded = eval(expr_1) & 127.
  • For each error from 0 to 7, we set a = (encoded ^ (1 << error)) & 127 and decoded = eval(expr_2) then check if decoded is equal to initial.
• The goal is to make decoded equal to initial then it’ll print the flag.

Some things we can observe is the inner loop is bruteforcing every possible single bit flip on the encoded value, and expr_2 must return the original 4 bit value of initial.

After much googling, this should be quite similar to (7, 4) Hanmming code, which encodes 4 data bits into 7 bits (4 data bits + 3 parity bits) and can correct single-bit errors. To give a brief summary of Hamming code, it’s basically used in networking to detect and correct single-bit errors in data transmission. How it works is that it adds parity bits at certain positions in the data stream, and these parity bits are calculated based on the values of the data bits. When a single-bit error occurs, the parity bits will not match up, allowing the receiver to identify and correct the error.

Goal

• Encode a 4-bit number (a, from 0–15) into a 7-bit Hamming code (expr_1).
• Decode a possibly single-bit-flipped 7-bit number (expr_2) back to the original 4-bit number.
• expr_1 and expr_2 can only contain characters like 1234567890a+-*&|^ ()<>

expr_1: Encoding function

(7, 4) Hamming encoding means we

• take 4 bits of real data a0, a1, a2, a3, and then mix them with 3 parity bits p1, p2, and p3 to form a 7-bit codeword.

The 7 bits d4d3d2p3d1p2p1 are then arranged as:

Position (from right)	1	2	3	4	5	6	7
bit	p1	p2	d1	p3	d2	d3	d4

to recall, d1, d2, and d3 are the data bits, while p1, p2, and p3 are the parity bits.

Let’s begin with the encoding.

So first, we gotta extract each bit of the input a. To do that, we have

a0 = a & 1 > 0 -> bit 0

a1 = (a & 2 > 0) -> bit 1

a2 = (a & 4 > 0)-> bit 2

a3 = (a & 8 > 0) -> bit 3

This is equivalent to our data bits.

• d1 = a0
• d2 = a1
• d3 = a2
• d4 = a3

Now back to getting the d4d3d2p3d1p2p1 (same order as the table above).

Bit Position	Bit Name	How it’s calculated
b0 (1’s place)	d4	a3
b1 (2’s place)	d3	a2
b2 (4’s place)	d2	a1
b3 (8’s place)	p3	a1 ^ a2 ^ a3
b4 (16’s place)	d1	a0
b5 (32’s place)	p2	a0 ^ a2 ^ a3
b6 (64’s place)	p1	a0 ^ a1 ^ a3

If you’re wondering how did we get p3, p2, and p1, it’s how Hamming code works. Parity bits are placed at positions that are powers of 2: 1, 2, and 4. That’s why p1 is at position 1, p2 is at position 2, and p3 is at position 4.

• p1 covers positions where bit 0 (least significant) is 1 → positions 1, 3, 5, 7. bits 1, 3, 5 are d1, d2, d4 which correspond to a0, a1, a3.

• p2 covers positions where bit 1 is 1 → positions 2, 3, 6, 7. bits 2, 3, 4 are d1, d3, d4 which correspond to a0, a2, a3.

• p3 covers positions where bit 2 is 1 → positions 4, 5, 6, 7. bits 4, 5, 6 are d2, d3, d4 which correspond to a1, a2, a3.

So we’re done with the hard part. expr_1 is just the bitwise OR of all the bits we calculated above. So we sum them up bitwise.

expr_1 is:

((a&8>0)*1) + ((a&4>0)*2) + ((a&2>0)*4) + (((a&2>0)^(a&4>0)^(a&8>0))*8) + ((a&1>0)*16) + (((a&1>0)^(a&4>0)^(a&8>0))*32) + (((a&1>0)^(a&2>0)^(a&8>0))*64)

expr_2: Decoding function

In error-correcting codes, the syndrome is a little “checksum” you compute from the received bits.

• If syndrome = 0, then no error.
• If syndrome ≠ 0, the syndrome points to the position (which bit is wrong).

For Hamming(7, 4), the syndrome is calculated as follows:

• s1 = p1 ^ d1 ^ d2 ^ d4
• s2 = p2 ^ d1 ^ d3 ^ d4
• s3 = p3 ^ d2 ^ d3 ^ d4

s = s1 + s2 * 2 + s3 * 4

if s = 0, that means no error, while if s = 1, that means bit 1 is wrong, and so on.

So expr_2 needs to

1. Compute syndrome
2. Flip the wrong bit if s is not 0 (s gives us the position of the bit that is wrong)
3. Rebuild the original 4-bit number from the corrected 7-bit codeword. So that decoded is equal to initial.

We know the codeword is in the form of b6b5b4b3b2b1b0 (p1p2d1p3d2d3d4), sth like this:

Name	Expression	Bit Position (from the left)
p1r	b6	6
p2r	b5	5
d1r	b4	4
p3r	b3	3
d2r	b2	2
d3r	b1	1
d4r	b0	0

*Note: I put r because later we have c for corrected, r is just the original bits.

So s is calculated as:

s = ((b(3) ^ b(2) ^ b(1) ^ b(0)) * 4
   + (b(5) ^ b(4) ^ b(1) ^ b(0)) * 2
   + (b(6) ^ b(4) ^ b(2) ^ b(0)) * 1)

where b(i) is the bit at position i of the received codeword.

If s is not 0, we need to flip the bit at position s. This is done through:

• d1c = d1r ⊕ (s==3) -> checking the bit at position 3
• d2c = d2r ⊕ (s==5) -> checking the bit at position 5
• d3c = d3r ⊕ (s==6) -> checking the bit at position 6
• d4c = d4r ⊕ (s==7) -> checking the bit at position 7

But we have one last problem, we can’t use == in our expression 🗿. So we need to convert the == using some chained comparison trick (creds to 🤖 for the amazing suggestion!).

The chained comparison trick is a neat little trick, where you can use bitwise operations to check if a number is equal to another number without using the == operator.

• s == 3 ↔ (2 < s < 4)
• s == 5 ↔ (4 < s < 6)
• s == 6 ↔ (5 < s < 7)
• s == 7 ↔ (6 < s < 8)

Why it works? Because in Python, chained comparisons are evaluated from left to right. So if s is 3, then 2 < s < 4 will be True, and the rest will be False.

So expr_2 is:

(
    ((b(0) ^ (6 < s < 8)) * 8) +
    ((b(1) ^ (5 < s < 7)) * 4) +
    ((b(2) ^ (4 < s < 6)) * 2) +
    ((b(4) ^ (2 < s < 4)) * 1)
)

If you would like to expand and sub back all the variables and similar to expr_1, we need to shift back each bit to the correct position with 2, 4, 8, 16, 32, … We’ll get expr_2 as

(
    ( ((a&1>0) ^ (6<(((a&8>0)^(a&4>0)^(a&2>0)^(a&1>0))*4 + ((a&32>0)^(a&16>0)^(a&2>0)^(a&1>0))*2 + ((a&64>0)^(a&16>0)^(a&4>0)^(a&1>0))*1)<8)) *8 )
  + ( ((a&2>0) ^ (5<(((a&8>0)^(a&4>0)^(a&2>0)^(a&1>0))*4 + ((a&32>0)^(a&16>0)^(a&2>0)^(a&1>0))*2 + ((a&64>0)^(a&16>0)^(a&4>0)^(a&1>0))*1)<7)) *4 )
  + ( ((a&4>0) ^ (4<(((a&8>0)^(a&4>0)^(a&2>0)^(a&1>0))*4 + ((a&32>0)^(a&16>0)^(a&2>0)^(a&1>0))*2 + ((a&64>0)^(a&16>0)^(a&4>0)^(a&1>0))*1)<6)) *2 )
  + ( ((a&16>0) ^ (2<(((a&8>0)^(a&4>0)^(a&2>0)^(a&1>0))*4 + ((a&32>0)^(a&16>0)^(a&2>0)^(a&1>0))*2 + ((a&64>0)^(a&16>0)^(a&4>0)^(a&1>0))*1)<4)) *1 )
)