# brillouin
500 points, Crypto
## Descriptionbrillouin is an exciting new b l o c c c h a i n authentication provider. you can tell how decentralized it is because the signatures are so small! nc crypto.chal.csaw.io 1004
Author: (@japesinator, @trailofbits)
Files: [brillouin.py](brillouin.py)
## Solution
Basic inspection of the file reveals that BLS Signature Scheme is used to sign and verify here. Googling here and there revealthat it makes use of a function `e` called bilinear pairing function. It works on a pair of points on some elliptic curve and returns a point on some other curve. It has a property that - 
```e(x + y, z) = e(x, z) * e(y, z)```
We don't need to know the actual structure of the function, just this property is enough.
In BLS scheme, secret key `sk` is some integer and public key is the point `sk * g` where `g` is the generator of the curve.
We sign a message `m` by first hashing this message to some point using a hash function `H` and then multiplying it with our secret key `sk`:
`signature = sk * hash(m)`
We verify a message by comparing the values `e(g, signature)` and `e(pk, hash(m))`, the signature is valid if both of them evaluate to the same point.
```if e(g, signature) == e(pk, hash(m)):    print("signature is valid")```
Why is this correct? Because for a valid signature:
`e(g, signature) = e(g, sk * hash(m)) = e(g, hash(m)) * e(g, hash(m)) * e(g, hash(m)) ....` (`sk` times)  ` = e(g * sk, hash(m)) = e(pk, hash(m))`
In BLS signature scheme we also have a concept called aggregation which is basically a linear operation over the public keys/ signatures. Coefficients are determined by the `lagrange_basis` function ([defination](https://github.com/asonnino/bls/blob/master/bls/utils.py#L13)). Aggregation is used in multiparty signature schemes,details of which I would be skipping, but you may read over [here]()
Now for the challenge, lets collect what all we have; We have three public keys `pA`, `pB` and `pC`. We can get message "ham"signed by `pA`, `pB` is good for nothing and `pC` is the most useful - we can get any of our message signed. End goal - we need to give them three public keys `p1`, `p2` and `p3` and two signatures `s1` and `s2` such that aggregation of `s1` and `s2`is a valid signature of the public key obtained by aggregation of `p1`, `p2` and `p3` for the message "this stuff".
There are some constraints too - `s1` and `s2` cannot be same ([here](brillouin.py#L65)), `p1` and `p2` must be one of the `pA`, `pB` and `pC`, though they can be same ([here](brillouin.py#L51)). _We have no limitations for `p2`_. This is our catch. We use`lagrange_basis` function to calculate the coefficients, referring the code from [here](https://github.com/asonnino/bls/blob/master/bls/scheme.py#L69)
```pythonfrom bls.scheme import setup
def lagrange_basis(t, o, i, x=0):	numerator, denominator = 1, 1	for j in range(1,t+1):		if j != i:			numerator = (numerator * (x - j)) % o			denominator = (denominator * (i - j)) % o 	return (numerator * denominator.mod_inverse(o)) % o
params = setup()(G, o, g1, g2, e) = params# for 2 signaturesl = [lagrange_basis(2, o, i, 0) for i in range(1,3)]print l# for 3 public keysl = [lagrange_basis(3, o, i, 0) for i in range(1,4)]```Output comes out to be - ```[2, 16798108731015832284940804142231733909759579603404752749028378864165570215948][3, 16798108731015832284940804142231733909759579603404752749028378864165570215946, 1]```
It is important to see that the difference between the two large numbers is 2. Let us call them `L` and `L-2`.
So we now have to plug such values of `s1`, `s2`, `p1`, `p2` and `p3`such that:
```e(g, 2*s1 + L*s2) == e(3*p1 + (L-2)*p2 + p3, hash("this stuff"))```Now suppose I sign the message "this stuff" with my key and pass that in `s2` and get the sign of `pC` on the same message, I will get two signs of the required message. Let's create a dummy public + secret key pair `sk0 = 3` and `p0 = 3*g` and sign "this stuff" with it and get `s0`. Lets call the sign from `pC` - `sC`. So,
```e(pC, hash("this stuff")) = e(g, sC)e(p0, hash("this stuff")) = e(g, s0)```
Now what we do is also called Rogue Public Key attack, but lets not use these terms here. Rather a simple explaination - If I put `p1 = pC`, `p2 = pC` and `p3 =  2*p0 - pC`:
```       e( 3*p1 + (L-2)*p2 + p3, hash("this stuff"))    =  e( (L+1)*pC + 2*p0 - pC, hash("this stuff"))    =  e( L*pC + 2*p0, hash("this stuff"))    =  e( pC, hash("this stuff") ) * e( pC, hash("this stuff") ) .... * e( p0, hash("this stuff") ) * e( p0, hash("this stuff") )    =  e( g, sC ) * e( g, sC ) .... * e( g, s0 ) * e( g, s0 )    =  e( g, 2*s0 + L*sC ) ``` Voila! 
I can pass `s0` and `sC` as the signatures! And you get the flag on running the script:
```flag{we_must_close_the_dh_gap}
```