ångstromCTF 2023

This year I wrote two challenges as a guest author for ångstromCTF. I was an organizer up until 2019, and it’s crazy to see that we’re in our eighth year, with a completely new team, still running this thing. Really excited to hit number ten :)

As always, you can find my solution code at github.com/defund/ctf.

snap circuits

Once you read through the code, the premise of this challenge is fairly simple: we specify a boolean circuit, and the server garbles it. The input wires encode the flag, and we aren’t allowed to specify any output wires. Of course, if you aren’t familiar with garbled circuits, none of this will make sense. In that case, I would suggest checking out Joseph’s DiceCTF 2021 writeup and section 3.1 of Pragmatic MPC.

The point of garbled circuits, and MPC in general, is that we shouldn’t learn anything except the circuit’s output. Since we don’t get any output in this challenge, we theoretically learn nothing. But this is a CTF challenge, so perhaps the implementation is vulnerable.

To make things easier, I linked some reference code in the challenge description. In particular, point_and_permute.py matches the challenge’s code, with one key difference. In point_and_permute.py, the stream cipher is initialized like so:

key = idx.to_bytes(8, 'big') + b''.join([l.key for l in labels])
self.shake = SHAKE128.new(key)

In contrast, the challenge’s code is missing idx:

key = b''.join([l.key for l in labels])
self.shake = SHAKE128.new(key)

The point of idx is to ensure that each gate’s cipher is initialized differently. As we’ll see, this is crucial for avoiding issues similar to one-time pad reuse.

Suppose we are trying to leak the value of some wire a. Let’s garble an AND gate where the input wires are both a. The garbler will generate a new wire c and output the following table (to keep things simple, let’s ignore the shuffling caused by point-and-permute):

H(a.zero, a.zero) ⊕ c.zero
H(a.zero, a.zero) ⊕ c.zero
H(a.zero, a.zero) ⊕ c.zero
H(a.one,  a.one ) ⊕ c.one

If we garble the same AND gate again, the garbler will generate a new wire d and output the following table:

H(a.zero, a.zero) ⊕ d.zero
H(a.zero, a.zero) ⊕ d.zero
H(a.zero, a.zero) ⊕ d.zero
H(a.one,  a.one ) ⊕ d.one

Now the issue should be clear: the keystreams are identical across tables! If we XOR the tables together, we’re left with the following:

c.zero ⊕ d.zero
c.zero ⊕ d.zero
c.zero ⊕ d.zero
c.one  ⊕ d.one

Notice that three rows are identical, and if our label for wire a points to one of them, we know it represents zero. Otherwise, it represents one. By repeating this attack for each input wire, we get the flag.

tau as a service

This challenge is based on the powers-of-tau setup, which publishes the values G, τG, [τ^2]G, [τ^3]G, ..., [τ^D]G for some scalar τ. Powers-of-tau setups are used in many protocols, where it is crucial that the “toxic waste” τ is kept hidden from participants. In practice, there are two ways to accomplish this: rely on a trusted third party, or perform a decentralized MPC computation. In our case, we have a server which evaluates [τ^d]G for arbitrary d on demand. Our goal is to recover τ, which also happens to be the flag.

At a high level, the solution is a variant of Cheon’s attack. You’re free to read the paper, but the idea is simple enough that I’ll explain everything.

Our attack will leverage the extra information provided by the powers-of-tau setup. We can view τ^d as an element of (Z/nZ)*, where n is the BLS curve’s order. Here’s the interesting thing: the order of (Z/nZ)*, i.e. n-1, is smooth! The reason for this is not important here, but it’s related to the curve’s use in pairing-based cryptography.

With this in mind, consider an arbitrary generator (Z/nZ)*; concretely, let’s take 7. Our goal will be to solve the discrete logarithm of τ relative to 7, or in other words find x such that 7^x = τ. This may seem unintuitive, since we don’t even know τ. But we do know τG, which serves as a “hash” for τ. So for our first attempt, let’s guess every possible value of x from 0 to n-2, and check whether [7^x]G is equal to the hash.

It shouldn’t be a surprise that this brute force approach is too inefficient. Instead, we’ll solve the discrete logarithm in smaller subgroups, analogous to the Pohlig-Hellman algorithm. For some prime factor p of n-1, let d = (n-1)/p. The idea is to query the server for [τ^d]G, then solve the discrete logarithm of τ^d with respect to 7^d. This only requires p guesses, and the result is x modulo p.

In fact, it turns out that we can fully emulate the Pohlig-Hellman algorithm. In particular, whenever the algorithm multiplies group elements a and b, we will instead multiply the hash aG by b (note that b must be a constant). The largest prime is 28 bits, so we can recover the logarithm in roughly 2¹⁴ steps.