# 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

The challenge gives the source of a socket server. The first thing I noticed were the imports, most of which I didn’t have.

```
from base64 import b64encode, b64decode
from bls.scheme import *
from bplib.bp import G1Elem, G2Elem
from petlib.bn import Bn
```

The `bls`

module implements the Boney-Lynn-Shacham (BLS) signature scheme, which I’ll describe later. It also uses the `bplib`

and `petlib`

libraries for the scheme’s underlying elliptic curve and bilinear pairing operations. I had trouble installing `bplib`

, so I ended up working on my teammate’s computer with screen share.

It isn’t necessary to delve into the BLS signature scheme’s inner cryptography, but I want to note the scheme’s threshold property. One can construct `n`

pairs of signing (private) and verifying (public) keys such that `t`

are required to construct a valid signature; `t`

is the threshold number for `n`

parties.

The server first generates 3 key pairs with a threshold of 2: `sks`

is a tuple of the signing keys, and `vks`

is the corresponding tuple of verifying keys.

```
def __init__(self):
self.params = setup()
(sks, vks) = ttp_keygen(self.params, 2, 3)
self.sks = sks
self.vks = vks
pvks = list(map(pretty_point, vks))
print(
"hi welcome to chili's\nauthorized admins and keys:\nAbraham\n{}\nBernice\n{}\nChester\n{}".format(
pvks[0], pvks[1], pvks[2]
)
)
```

In the BLS scheme, 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.

To obtain the flag, we must provide an aggregate signature for the string `"this stuff"`

. The server provides some help: with the third key pair, it will sign any string we provide. However, it will only sign the string `"ham"`

with the first, and won’t sign anything with the second. Since we can only obtain one individual signature for `"this stuff"`

, the challenge seems impossible.

At this point, I started searching online for attacks against the BLS scheme. It didn’t take long to find a web page written by Boneh himself describing a ‘rogue public-key attack’.

The idea is that an attacker Alice first constructs her own key pair. She then forges a verifying key, which when combined with others, aggregates to Alice’s original verifying key. The aggregate signing key is simply her original signing key as well. Now, Alice can pretend that other parties have agreed to sign a string by providing an aggregate signature.

Is the attack relevant in this scenario? In the server’s flag exchange, it asks for two signatures `s0,s1`

and their corresponding verifying keys `p0,p1`

. It then asks for the final unused verifying key `p2`

.

```
def getflag(self):
print(
"gonna have to see some credentials, you know at least two admins gotta sign off on this stuff:"
)
(s0, p0) = self.getsignature(
"first signature, please\n",
"and who is this from (the public key, if you please)?\n",
)
(s1, p1) = self.getsignature(
"OK, and the second?\n", "who gave you this one (again, by public key)?\n"
)
assert s0 != s1
p2 = G2Elem.from_bytes(
b64decode(
str(
raw_input(
"who didn't sign? We need their public key to run everything\n"
)
)
),
self.params[0],
)
if verify(
self.params,
aggregate_vk(self.params, [p0, p1, p2], threshold=True),
aggregate_sigma(self.params, [s0, s1], threshold=True),
"this stuff",
):
with open("flag.txt") as f:
print(f.read())
else:
print("lol nice try")
```

For `s0,s1`

and `p0,p1`

, the server uses `getsignature`

. This function asserts that the verifying key is within its generated set, so we can’t introduce a forged one here.

```
def getsignature(self, ask, who):
ask_s = b64decode(str(raw_input(ask)))
s = G1Elem.from_bytes(ask_s, self.params[0])
ask_p = b64decode(str(raw_input(who)))
p = G2Elem.from_bytes(ask_p, self.params[0])
assert p in self.vks
return (s, p)
```

However, the server does not repeat this assertion for `p2`

, which is directly received in `getflag`

. I could send a forged verifying key here and pretend that the parties of `p0,p1`

have signed `"this stuff"`

!

To test my idea, I simulated the server locally. `p0,p1`

are the two honest verifying keys I used. I also generated my own keypair with `n=1`

and `t=1`

, since the verifying key represents an aggregate.

```
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)]
```

Next, I wanted to forge `p2`

such that it, along with `p0,p1`

aggregated to `vk`

.

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

The source for `aggregate_vk`

is in `bls/scheme.py`

. The aggregate is a linear combination of the verifying keys, with the weights computed by `lagrange_basis`

.

```
def aggregate_vk(params, vk, threshold=True):
"""
Aggregate the verification keys.
Parameters:
- `params`: public parameters generated by `setup`
- `vk` [G2Elem]: array containing the verification key of each authority
- `threshold` (bool): optional, whether to use threshold cryptography or not
Returns:
- `aggr_vk` (G2Elem): aggregated verification key
"""
(G, o, g1, g2, e) = params
t = len(vk)
# evaluate all lagrange basis polynomial li(0)
l = [lagrange_basis(t, o, i, 0) for i in range(1,t+1)] if threshold else [1 for _ in range(t)]
# aggregate keys
aggr_vk = ec_sum([l[i]*vk[i] for i in range(t)])
return aggr_vk
```

`lagrange_basis`

for an array of length 3 is always the same value, since `o`

is a constant public parameter.

```
[3, 16 ... 46, 1] # second element is large
```

Reformulating my assertion, which I then used to forge `p2`

.

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

Next, I created the aggregate signature `sig`

. I also wanted to forge signatures `s0,s1`

such that they aggregated back to it.

```
sig = sign(params, sk, "this stuff")
assert sig == aggregate_sigma(params, [s0, s1], threshold=True)
```

The source for `aggregate_sigma`

is virtually identical to `aggregate_vk`

and can be found in `bls/scheme.py`

. I computed `lagrange_basis`

again, this time for an array of length 2. The second element turned out to be `o-1`

; since `o`

is the group’s order, I treated it as `-1`

.

```
[2, -1]
```

Reformulating my assertion, which I then used to forge `s0,s1`

. Since the server requires `s0,s1`

to be distinct, I couldn’t set both to `sig`

.

```
assert sig == 2*s0 - s1
s0 = -sig
s1 = -3*sig
```

With that, I had all the values I needed. Solution code that simulates the server locally 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",
)
```