CSAW CTF Quals 2019

September 16, 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

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",
)