DiceCTF NIL-CIRC: Garbled Circuit Optimizations and Malicious OT Receiver

tl;dr: This blog will introduce the naive Yao’s garbled circuit and state-of-the-art gate optimizations in fancy-garbling library (implementation of BMR16). This blog also serves as a detailed writeup of DiceCTF 2025 NIL-CIRC.

The writeup of DiceCTF 2025 involves only section elementary-optimizations and section free-xor-offset-leak-attack. Readers familiar with the garbled circuit can skip to the final section. For those who are not familiar with free-XOR techniques, reading the section elementary-optimizations is enough to understand the final attack. For those who are interested in the half-gate technique of fancy-garbling library, reading section half-gate-technique is recommended. The solver can be found my ctf-writeups.

Garbled Circuit

Garbled circuit is a type of cryptographic protocol that enables secure computation between two untrusting parties. In this setup, the parties can jointly evaluate a function on their private inputs without the need for a trusted third party. In the garbled circuit protocol, the function to be evaluated is usually represented as a boolean circuit consisting of gates (such as AND, OR, and NOT). The protocol ensures that each party learns only the output of the function and nothing about the other party’s input. A necessary component in garbled circuit is the oblivious transfer (OT) protocol.

Oblivious Transfer

Alice has two secret strings $ S_0 $ and $S_1$. Bob chooses an private index $ i \in {0, 1} $. In oblivious transfer (OT), the selectable string $S_i$ is transmitted between the sender (Alice) and the receiver (Bob) in the following manner:

• Bob learns nothing about the unchosen string $ S_{1-i} $.
• Alice remains unaware of Bob’s choice $ i $.

It’s important to note that although Bob does not know the actual values of $ S_0 $ and $ S_1 $ beforehand, in practical applications, Bob typically has some encoded/side-channel information about these strings. This ensures that Bob can intelligently decide which message to retrieve rather than selecting blindly. For example, Alice usually sends the encrypted secret $c_0 = E(S_0), c_1 = E(S_1)$ in a sequential manner. This selective knowledge prevents Bob from making a random choice and allows for meaningful interaction in the protocol.

Oblivious transfer is a fundamental cryptographic primitive used in protocols such as secure multi-party computation (MPC), fair blind signature, and zero-knowledge proofs, enabling secure and private data exchange without compromising the privacy of either party.

Process of Garbled Circuit

We describe the general process of garbled circuit protocol between Alice (known as garbler) and Bob (known as evaluator) with their private input $a$ and $b$ respectively.

Alice and Bob agree on the pubic $f$ and its corresponding boolean circuit $\mathcal{F}$. Let the private input $a = (a_1, \ldots, a_{m})$ and $b = (b_1, \ldots, b_{n})$.

1. Circuit Garbling: Alice garbles the public boolean circuit $\mathcal{F}$, i.e., encrypting the truth table and wire labels. Denote the truth tables of the garbled circuit as $\mathcal{F}_{g}$. In this case, every input wire is encoded as two strings $w_0, w_1$ representing input bit $0,1$ respectively.
2. OT Phase: Alice sends wire labels corresponding to Bob’s private input $b$ through a batch of OT protocols. The other wire labels must kept secret to Bob.
3. Alice sends the garbled circuit $\mathcal{F}_{g}$ (truth tables of all gates) and wire labels corresponding to Alice’s private input to Bob. Note that the wire labels looks random and leaks nothing about $a$ to Bob.
4. Evaluation: Bob now has all input wire labels and garbled truth tables $\mathcal{F}_{g}$ and evaluate the circuit to obtain the final encrypted output.
5. Reveal Output: Since Bob does not know which bit semantic the final output wire label corresponds to, Alice and Bob exchange information to learn the plain output of the the pubic $f$.

The above protocol is too high-level and in the following, we elaborate on how to garble a boolean gate.

Now, we can see that with only the input wires and the garbled circuit $\mathcal{F}_{g}$ (truth tables of all gates), Bob can evaluate the circuit recursively and finally get the labels of output wires. After the evaluation, Bob obtains the output labels denoted as $X^{c}$ (assuming the circuit outputs only one bit), and Alice knows its mapping to the boolean value because the labels were initialized by her. Either Alice can share her information with Bob, or Bob can reveal the output to Alice, allowing one or both of them to learn the output.

A Demo of Garbled Circuit

In DiceCTF 2021, there is challenge garbled (writeup can be found here) about the naive implementation of Yao’s garbled circuit. I use the challenge codes to illustrate the steps of garbled circuit protocol. The demo codes can be found in my ctf-writeups.

# circuit_map.json
{
 "inputs" : [1, 2, 3, 4],
 "out" : [9],
 "gates" : [
     {"id" : 5, "type" : "AND", "in" : [1, 2]},
     {"id" : 6, "type" : "AND", "in" : [3, 4]},
     {"id" : 7, "type" : "AND", "in" : [5, 6]},
     {"id" : 9, "type" : "XOR", "in" : [7, 4]}
 ]
}

keys = {
1: (15233817, 1315943), 
2: (15274501, 5158879), 
3: (7431802, 16682547), 
4: (11945610, 6753699), 
5: (13849459, 4637545), 
6: (10453495, 2479542), 
7: (2068375, 13039971), 
9: (7508273, 12723289)}

G_Table = {
5: [(6829921, 11451673), (1515696, 6333149), (15107502, 8186257), (5872557, 12241756)], 
6: [(13415489, 4332242), (5144037, 9578022), (15201634, 13202380), (10357348, 15158424)], 
7: [(1587462, 6581034), (8356378, 2216472), (11762280, 3875959), (5982650, 7776773)], 
9: [(5728291, 11896856), (12052243, 1282564), (10228672, 10487067), (6137078, 8217550)]}

def encrypt(data, key1, key2):
    encrypted = encrypt_data(data, key1)
    encrypted = encrypt_data(encrypted, key2)
    return encrypted

def garble_label(key0, key1, key2):
    """
    key0, key1 = two input labels of a, b
    key2 = output label of c
    """
    gl = encrypt(key2, key0, key1)
    validation = encrypt(0, key0, key1)
    return (gl, validation)

from block_cipher import decrypt
from yao_circuit import GarbledGate as Ggate
import json

# garbled truth tables
G_Table = {
    5: [(6829921, 11451673), (1515696, 6333149), (15107502, 8186257), (5872557, 12241756)], 
    6: [(13415489, 4332242), (5144037, 9578022), (15201634, 13202380), (10357348, 15158424)], 
    7: [(1587462, 6581034), (8356378, 2216472), (11762280, 3875959), (5982650, 7776773)], 
    9: [(5728291, 11896856), (12052243, 1282564), (10228672, 10487067), (6137078, 8217550)]
    }

# Bob gets the wires
# alice_input = (keys[1][1],keys[2][0])
# bob_input = (keys[3][1],keys[4][1])
alice_input = (1315943 ,15274501)
bob_input = (16682547, 6753699)

# load circuit
circuit_filename = "circuit_map.json"
with open(circuit_filename) as json_file:
    circuit = json.load(json_file)

# evaluate the truth_table given the two input labels
def validate_the_circuit(geta_table, key0, key1):
    for g in geta_table:
        gl, v = g
        label = decrypt(gl, key0, key1)
        validation = decrypt(v, key0, key1)

        if validation == 0:
            return label
        
labels_dict = {}
user_input = {1: alice_input[0], 2: alice_input[1], 3: bob_input[0], 4: bob_input[1]}
gates = circuit["gates"]
wires = set()
for gate in gates:
    wires.add(gate["id"])
    wires.update(set(gate["in"]))
for wireidx in wires:
    # the index of keys[wireidx] 1 and 0 means TRUE and FALSE in garbled circuit
    if wireidx in user_input:
        labels_dict[wireidx] = user_input[wireidx]
    else:
        labels_dict[wireidx] = -1

while True:
    for gate in gates:
        out_id = gate["id"]
        input = gate["in"]
        
        if labels_dict[input[0]] == -1 or labels_dict[input[1]] == -1:
            continue
        else:
            garbled_table = G_Table[out_id]
            key0 = labels_dict[input[0]]
            key1 = labels_dict[input[1]]
            labels_dict[out_id] = validate_the_circuit(garbled_table, key0, key1)
    target = circuit["out"][0]
    if labels_dict[target] != -1:
        print("The target label is: ", labels_dict[target])
        break

Elementary Optimizations

In Yao’s garbled circuit, every fan-in-k gate needs $2^k$ ciphertexts to encrypt the truth table. Besides, the encrypted truth table must be shuffled and the evaluator is expected to try $2^{k-1}$ item decryptions to find the correct output wire label. Therefore, the early implementations of garbled circuits were extremely slow. With the emergence of numerous optimization techniques, garbled circuits have now reached practical application standards.

Half-Gate Technique

The half-gate technique ZRE15 is a powerful optimization that allows the use of only two ciphertexts per AND, OR, NOR, NAND gate, while being compatible with free-XOR, which results in two ciphertexts per AND/OR gate and 0 per XOR gate. Later in CRYPTO’21, Mike Rosulek and Lawrence Roy RR21 improved the half-gate technique, allowing 1.5 ciphertexts per AND gate and 0 per XOR gate. This section involves only techniques introduced in ZRE15.

Half-Gate Decomposition

The half-gate technique allows two ciphertexts per AND gate which is compatible of free-XOR. Denote $(A, A \oplus \Delta)$ and $(B, B \oplus \Delta)$ as the input wire labels to an AND gate, and $(C, C \oplus \Delta)$ as the output wire labels, where $A, B, C$ each encodes ‘false’ (bit 0) of $a, b, c$. Let $\mathcal{H}(\cdot)$ be a random oracle. The half-gate technique split the AND gate $c = a \land b$ as follows:

• Case $a = 0$: AND gate degenerate to a unary gate that always outputs false.
• Case $a = 1$: AND gate degenerate to a unary identity gate that always outputs its input.

Now, note that the AND gate can be split into two half gate:

Suppose the generator chooses a uniformly random bit $r$ and the bit $r$ is known to the generator. In practical case, the generator will choose $r$ to be the color bit of the false wire label on wire $b$ which reveals the value of $r \oplus b$ to the evaluator because for wire $W_i^b$, its color bit is exactly $r \oplus b$. In the following, we consider two half AND gates where exactly one input is known to either the garbler or evaluator.

Now, two halves make a whole ADD gate. We denote $C_{G}, C_{E}$ as the generator’s and evaluator’s half gates, respectively. Intuitively, we can XOR the two ciphertexts of half gates to obtain the ciphertexts of the original AND gate.

Two Halves = One Whole

Let the AND gate’s input labels be $W_a^{0}, W_a^{1}, W_b^{0}, W_b^{1}$ and output labels $W_{c}^0, W_{c}^1$. Let $W_{G_c}, W_{G_e}$ be the output labels of generator’s and evaluator’s half-gates. The global offset value for free-XOR is $\Delta$, i.e., $W_{i}^{0} \oplus W_{i}^{1} = \Delta$ for all $i$. Denote the color bits of $W_a^{0}, W_a^{1}$ as $p_a$ and $p_b$ respectively.

Finally, the generator sends $T_{G_c}, T_{G_e}$ to the evaluator. Denote the boolean value of wire $a, b$ as $x_{a}, x_{b}$ and let $p_a$ be $0$ for simplicity (ignore the first permutation). The evaluator evaluate the two half gates to get $W_{G_c}, W_{E_c}$ based on the color bits of $W_a^{x_a}, W_b^{x_b}$ as follows:

Use the free-XOR to get the final output label as

This shows our scheme evaluates the ADD gate correctly with only two ciphertexts using free-XOR. This half-gates can generalize to any gate whose truth table contains an odd number of ones (e.g. AND, NAND, OR, NOR, etc.). All such gates can be expressed as the form of

for constants $\alpha_a, \alpha_b, \alpha_c$. The generic half gates can be described as follows:

Typo: In generator’s half-gate, the value $p_b$ is known to generator.

Free-XOR Offset Leak

When free-XOR is implemented in garbled circuit, it should be careful that an malicious OT receiver may destroy the security and privacy of garbled circuit. In standard OT protocol, although it’s impossible (when implemented and used correctly) for the receiver to obtain two messages $x_0, x_1$ simultaneously, a dishonest receiver may carefully construct the input so that the value of some function $f(x_0, x_1)$ is leaked (e.g., we can easily recover the value of $f(x_0, x_1) = x_0 \pm x_1 \mod N$ in the RSA OT protocol). In free-XOR, the two messages to be transmitted in OT protocol) are $W_i^0, W_i^{1}$ where $\Delta = W_i^0 \oplus W_i^{1}$ holds for all $i$. Therefore, if we can recover $f(W_i^0, W_i^{1}) = W_i^0 \oplus W_i^{1} = \Delta$, we can actually recover all labels in the circuit.

In challenge NIL-CIRC, the Chou-Orlandi OT protocol is implemented in fancy-garbling library. We can recover the server’s private key as follows:

• Run the Chou-Orlandi OT protocol with an malicious receiver. This can leak the global offset $\Delta$ of free-XOR which allows us to recover all the wire label pairs in the garbled circuit.
• Use the unbalanced AND gate to recover the bit semantics of wire label pairs.
• Construct linear equations to recover the private key bits based on the bit semantics of wire labels.

Chou-Orlandi OT protocol

The Chou-Orlandi OT protocol eprint/2015/267 is claimed to be UC-secure in the random oracle model under dynamic corruptions.

This is a perfect phase to run a malicious OT receiver attack to recover the global offset $\Delta$ of free-XOR. The idea to make:

When receiving any input wire label $W_i^{b}$, the malicious receiver can recover:

For all other OT protocols, the malicious receiver runs honestly. With $\Delta$ and free-XOR, the attacker can recover both labels for each wire.

Recovering Private Inputs

No matter what optimizations are applied, the real truth table remains the same to keep the functionality. Therefore, we can distinguish the bit semantics represented by the wire labels from an unbalanced truth table. For a balanced gate such as XOR, we cannot decide the bit semantics of wire labels from a shuffled truth table. Take the AND gate as an example. Let the input wires be $W_{a}^{x}, W_{a}^{y}$ and $W_{b}^{u}, W_{b}^{v}$. Given the garbled circuit, we can evaluate the AND gate four times using input pairs:

and will only obtain two output labels $W_c^{0}, W_c^{1}$. We can determine that the output label occurring thrice is the label $W_c^0$ representing ‘false’ semantics and the other occurring once is the label $W_c^1$ representing ‘true’ semantics. Supposing the two labels $W_a^x, W_b^{v}$ outputs the $W_c^{1}$, we then know $W_a^1 = W_a^x$ and $W_b^1 = W_b^v$, respectively.

If we have the garbled circuit and all the input label pairs $(W_i^0, W_{i}^1)$ with their bit semantics unknown, we then evaluate the whole gates using arbitrary input $(x_1, \ldots, x_n)$. When it comes to an AND gate, we have two input labels $W_0, W_1$. Using free-XOR, we reconstruct the four input wire labels as $(W_{0}, W_{0} \oplus \Delta)$ and $(W_{1}, W_{1} \oplus \Delta)$ and evaluate the table four times to determine the bit semantics of $W_0, W_1$. Meanwhile, since the circuit is public, we know the algebraic expression (polynomial) of wires related to $W_0$ and $W_1$ and build an equation of original inputs $(x_1, \cdots, x_n)$. Collect enough equations and solves for $(x_1, \ldots, x_n)$ corresponding to our evaluated labels. Recall that we use one OT (e.g. input $0$) to recover the offset $\Delta$, all the wires related to input 0 will be ignored during evaluation. We can redefine a leaky_and evaluation in fancy-garbling:

impl<C: AbstractChannel> CustomAND for Evaluator<C, WireMod2> {
    // returns (output_label, A_bit, B_bit, success) where A_bit, B_bit are the bit semantics of A, B. 
    // `success` indicates whether the leak sucesses.
    fn leaky_and(&mut self, A: &Self::Item, B: &Self::Item, delta: &Self::Item) -> Result<(Self::Item, bool, bool, bool), Self::Error> {
        let gate0 = self.channel.read_block()?;
        let gate1 = self.channel.read_block()?;
        let A_inv = A.plus(delta);
        let B_inv = B.plus(delta);
        let inputs = [
            (A, B),
            (A, &B_inv),
            (&A_inv, B),
            (&A_inv, &B_inv),
        ];
        
        let outs = inputs.iter().map(|(a, b)| {
            let res = self.evaluate_and_gate(a, b, &gate0, &gate1);
            self.current_gate -= 1;
            res
        }).collect::<Vec<_>>();
        self.current_gate += 1;

        if outs[0] == outs[1] && outs[0] == outs[2] {
            return Ok((outs[0], false, false, true));
        } else if outs[0] == outs[1] && outs[0] == outs[3] {
            return Ok((outs[0], false, true, true));
        } else if outs[0] == outs[2] && outs[0] == outs[3] {
            return Ok((outs[0], true, false, true));
        } else if outs[1] == outs[2] && outs[1] == outs[3] {
            return Ok((outs[0], true, true, true));
        }
        // If we get here, we have a wrong label or a wrong gate, or a wrong delta
        return Ok((outs[0], false, false, false));
    }
}

Then we export all known bits of the wires into a file and solve linear equations to recover key bits in sagemath. In my local test, we can recover 124 key bits and brute force 4 bits to decrypt the flag. Exploiting codes can be found in my ctf-writeups.