CSAW CTF Quals 2019

This was my first year competing in CSAW CTF after spending the last four playing HSF and RED in high school. I played with zero cost abstractions, and we placed 9th overall.

Brillouin

This challenge is about the Boneh-Lynn-Shacham (BLS) signature scheme. The cool thing about BLS is that it supports threshold signatures: you can generate n keypairs such that only t out of n are required to construct a valid signature. We call t the threshold number. In BLS, all n verifying keys are combined to form an aggregate verifying key. Any party can sign a message, and t individual signatures can be combined to form an aggregate signature.

The server first generates 3 keypairs with a threshold of 2. To obtain the flag, we must provide an aggregate signature for the string "this stuff". The server will sign the string "ham" using the first key, and refuses to sign with the second. Fortunately, it will sign anything with the third key. But since we can only obtain one individual signature for "this stuff", this task seems impossible.

At this point, I started searching for well-known attacks against the BLS scheme. It didn’t take long to find this page, which describes a “rogue public-key attack”. The idea is as follows. Let’s say Alice, Bob, and Carol each have their own keypairs. It turns out that Alice can forge a garbage verifying key which, when combined with Bob and Carol’s verifying keys, aggregate to Alice’s verifying key. Therefore, Alice can pretend that Bob and Carol have signed a message by providing an “aggregate signature,” which is in fact her own.

Is the attack relevant to this challenge? The server asks for three public keys p0, p1, and p2. It only asks for two signatures s0 and s1, since this is the threshold. Although it checks that p0 and p1 belong to vks, there is no such check for p2. In other words, we can introduce a rogue public key!

Now let’s show how to perform the attack. Suppose p0 and p1 are two of the actual verifying keys. First, we generate our own keypair.

sk, vk = [key[0] for key in ttp_keygen(params, 1, 1)]

Next, we forge a verifying key p2 such that p0, p1, and p2 aggregate to vk. The aggregate_vk function is defined in bls/scheme.py. Notice that the aggregate key is a linear combination of the individual keys, and the weights are computed by lagrange_basis. Rewriting this mathematically, we must satisfy the following equality:

vk == 3*p0 + 16..46*p1 + p2

Solving for p2, we get:

p2 == vk - 3*p0 - 16..46*p1
   == aggregate_vk(params, [-p0, -p1, vk], threshold=True)

The aggregate signature is generated by our private key.

sig = sign(params, sk, "this stuff")

Finally, we forge individual signatures s0 and s1 which aggregate to sig. The aggregate_sigma function is defined in bls/scheme.py. Similar to before, we must satisfy the following equality:

sig == 2*s0 - s1

A full proof of concept is given below.

from brillouin import *

G, o, g1, g2, e = params = setup()

s = Threshold()
p0 = s.vks[0]
p1 = s.vks[1]

sk, vk = [key[0] for key in ttp_keygen(params, 1, 1)]

p2 = aggregate_vk(params, [-p0, -p1, vk], threshold=True)

sig = sign(params, sk, "this stuff")

s0 = -sig
s1 = -3*sig

assert verify(params,
  aggregate_vk(params, [p0, p1, p2], threshold=True),
  aggregate_sigma(params, [s0, s1], threshold=True),
  "this stuff",
)