# CSAW CTF Quals 2019

September 16, 2019This 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",
)
```