Skip to content

Instantly share code, notes, and snippets.

@toby-bro

toby-bro/FCSC23-writeup-au_boolot.md

Created February 21, 2026 00:07
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save toby-bro/f73515c7adff9c084b1ebc63a2c9c7b8 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save toby-bro/f73515c7adff9c084b1ebc63a2c9c7b8 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
FCSC23-writeup-au_boolot.md

 Au boolot

Link to the challenge

Understanding the problem

We have an oracle to the output of a logic circuit only composed of XORs. The circuit takes in input a 128 bit value, and returns a 256 bit output value.

We can send upto 130 different input values to the oracle before he asks us to guess the output of another value.

As we the circuit is only composed of XORs, if we

  • send two different inputs $i_1, i_2$
  • get their outputs $f(i_1) = o_1, f(i_2) = o_2$
  • XOR the two inputs $i_1 \oplus i_2$
  • send the XORed inputs to the oracle

we expect to get $f(i_1 \oplus i_2) = o_1 \oplus o_2$ (the XOR of the previous outputs).

===== Welcome to auBOOLot: Beat the Circuit! ======
[+] Please wait a bit during circuit generation ...
[+] Secret circuit generated! (25935 XOR gates)
Please provide a 128-bit binary input to evaluate:
>>> 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
Your output is 0001110000110100000010011101011101111101010100000100000001000111110111000111110110001111000011111010110101101100010100100000101110111100110000000101110100000001000000111101110010100100010111011011001010011100011100111010011100011000101001010100001111010111
Please provide a 128-bit binary input to evaluate:
>>> 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010
Your output is 0001110011010111011100111000100010001001111010110011111101110000000111111101011111100000001101010000110101101101001000110010110001000011101001101001000100000011011011100101001111110101111111100111111100001100111000010110011101101111111111110111101011101001
Please provide a 128-bit binary input to evaluate:
>>> 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
Your output is 0111111100000111011110011010101111011111111100110111011101011000111101011011010011010101111101010000010011001110011000011000101111011001001000100111110100001001011010001000010001010010001001100110111000000101001010001101001001000100001111100010010101101001

If we look at the first three bits we already see there is a problem we have three leading zeroes on the first and second, and only one on the third.

This is because the circuit does not only take our input, it is probably also linked to 0/1 values at some stages. Here is a simple example of a circuit taking two input values i0 and i1, and also using fixed constant inputs 0 and 1.

Depth 1          Depth 2          Depth 3

i0 ───────┐
          ├──[ XOR ]──────┐
 1 ───────┘               │
                          ├──[ AND ]──────┐
i1 ───────┐               │               │
          ├──[ XOR ]──────┘               │
 0 ───────┘                               ├──[ XOR ]─── OUT
                                          │
i0 ───────────────────────────────────────┘

This gives us a circuit does not simulate a perfectly linear function.

We can say that the circuit is applying the function $f : i \mapsto A \cdot i \oplus B$

In our previous example we had

$$\begin{align*} f(i_1) \oplus f(i_2) &= \left(A \cdot i_1 \oplus B \right) \oplus \left( A \cdot i_2 \oplus B \right) \\ &= A \cdot \left( i_1 \oplus i_2 \right) \\ &\neq A \cdot \left( i_1 \oplus i_2 \right) \oplus B = f(i_1 \oplus i_2) \end{align*}$$

So if we want to be able to predict the output (in our case) we must also know the output of the circuit when all inputs are 0, this gives us the offset ($B$) of the function that the circuit is applying.

So we simply need to update our previous "protocol"

  • send the 0 input $i_0$
  • get it's output $o_0 = B$
  • send two different inputs $i_1, i_2$
  • get their outputs $f(i_1) = o_1, f(i_2) = o_2$
  • XOR the two inputs $i_1 \oplus i_2$
  • send the XORed inputs to the oracle

We should now have $f(i_1 \oplus i_2) = f(i_1) \oplus f(i_2) \oplus B$

===== Welcome to auBOOLot: Beat the Circuit! ======
[+] Please wait a bit during circuit generation ...
[+] Secret circuit generated! (35237 XOR gates)
Please provide a 128-bit binary input to evaluate:
>>> 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
Your output is 0000011110010100110010000000001010111101101001101000001100010100001111110100110000111101101010101101001011010000110001101100101000110000101100010011011101010010100100001111111111011011000100011110011000000011001010101010111101111101110011111001000000011000
Please provide a 128-bit binary input to evaluate:
>>> 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
Your output is 0000100011101010000110001010110011011111001111111111000111011110111000110101011000101100110100011000101010101110010001100001000001010100101011000101001001110110001100010011010110011111011110100100111000110000010000011111100010111110100111001111011111111000
Please provide a 128-bit binary input to evaluate:
>>> 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010
Your output is 0000110110011100111011001010010010110011111001000111101100101111101000000000110001011110111010100101010110010010110001101010100101110100110110000010110011100011011100011111001111010101111101001011011100010011100101110110111100000101010011101111101100110010
Please provide a 128-bit binary input to evaluate:
>>> 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000011
Your output is 0000001011100010001111000000101011010001011111010000100111100101011111000001011001001111100100010000110111101100010001100111001100010000110001010100100111000111110100000011100110010001100111110001111100100000111111000011100011000110000111011001110011010010
Please provide a 128-bit binary input to evaluate:

And now the verification

>>> o0 = int('0000011110010100110010000000001010111101101001101000001100010100001111110100110000111101101010101101001011010000110001101100101000110000101100010011011101010010100100001111111111011011000100011110011000000011001010101010111101111101110011111001000000011000', 2)
>>> o1 = int('0000100011101010000110001010110011011111001111111111000111011110111000110101011000101100110100011000101010101110010001100001000001010100101011000101001001110110001100010011010110011111011110100100111000110000010000011111100010111110100111001111011111111000', 2)
>>> o2 = int('0000110110011100111011001010010010110011111001000111101100101111101000000000110001011110111010100101010110010010110001101010100101110100110110000010110011100011011100011111001111010101111101001011011100010011100101110110111100000101010011101111101100110010', 2)
>>> o3 = int('0000001011100010001111000000101011010001011111010000100111100101011111000001011001001111100100010000110111101100010001100111001100010000110001010100100111000111110100000011100110010001100111110001111100100000111111000011100011000110000111011001110011010010', 2)
>>> o1 ^ o2 ^ o0 == o3
True

Solving the problem

To solve the problem we are going to send each of the 00000...001000...0000 values with one 1 and only 0 otherwise. This way whatever the input the server send us back we can select the necessary inputs needed to reconstruct it by XORing them together. The answer to the problem will be the XOR of their outputs (with the $B$ value ?).

Now the problem we saw, of the $B$ value disappearing only happens if we are xoring an even number of values. If the number of ones in the requested input is odd then the $B$ will not disappear from our above formula.

In practice it is easier to always XOR $B$ to each of the output values we XOR together and then add one final $B$.

So if we take an example on 4 bits it would look like:

  • we ask the server for the outputs of 0001, 0010, 0100, 1000, 0000, we get $o_1, o_2, o_3, o_4, B$.
  • if the server asks us the output for 0011, then we will send him back : $(o_1 \oplus B) \oplus (o_2 \oplus B) \oplus B$
  • if the server asks us the output for 1011, then we will send him back : $(o_4 \oplus B) \oplus (o_1 \oplus B) \oplus (o_2 \oplus B) \oplus B$

The final script does just that

from typing import Generator

from pwn import remote


def next_input() -> Generator[str, None, None]:
    yield '0' * 128
    for i in range(129):
        yield '0' * ((128 - i - 1) % 128) + '1' + '0' * (i % 128)


p = remote('127.0.0.1', 4000)
i = 0

io_pairs = {}

for inp in next_input():
    print(f'===Iteration {i}===')
    p.recvuntil(b'>>> ').decode()
    print(f'Input: {inp}')
    p.sendline(inp.encode())
    p.recvuntil(b'Your output is').decode()
    outp = p.recvline().decode().strip()
    print(f'Output: {outp}')
    io_pairs[int(inp, 2)] = int(outp, 2)
    i += 1

p.recvuntil(b'Now provide the output of:').decode()
p.recvline()
test_input = p.recvline().decode().strip()
print(f'Test input: {test_input}')

output = io_pairs[0]
for i in range(128):
    if test_input[-i - 1] == '1':
        output ^= io_pairs[1 << i] ^ io_pairs[0]

print(f'Binary output: {bin(output)[2:].zfill(256)}')
p.sendline(bin(output)[2:].zfill(256).encode())
print(p.recvall().decode())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment