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.
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
p2. It only asks for two signatures
s1, since this is the threshold. Although it checks that
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
p1 are two of the actual verifying keys. First, we generate our own keypair.
sk, vk = [key for key in ttp_keygen(params, 1, 1)]
Next, we forge a verifying key
p2 such that
p2 aggregate to
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
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
s1 which aggregate to
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 p1 = s.vks sk, vk = [key 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", )