# Trouble With Pairs Writeup

### InCTF 2021 - crypto 925 - 14 solves

> We are testing a new Optimised Signature scheme for Authentication in our
> Voting System.  
> This might lead us to reduce the time taken for Election Process.  
> nc crypto.challenge.bi0s.in 1337 [Handout.zip](Handout.zip)

#### Analysis

Given cryptosystem implements [BLS Signature
Scheme](https://datatracker.ietf.org/doc/html/draft-boneh-bls-signature-00).
BLS has interesting
[properties](https://en.wikipedia.org/wiki/BLS_digital_signature#Properties):
Signature Aggregation. It means: Multiple signatures generated under multiple
public keys for multiple messages can be aggregated into a single signature.
[Diagram in Detail](https://www.cryptologie.net/article/472/what-is-the-bls-
signature-scheme/).

To get the real flag, I must get values of `flag` and `fake_flag` and xor
them. To reach those two control flow, I must provide signatures to server.

Luckily 46 signature pairs are given, included at [signer.py](signer.py).
Signatures are generated by following logic:  
```python  
for i in data:  
d = {}  
d['Name'] = i['Name']  
d['Vote'] = i['Vote']  
d['Count'] = i['Count']  
d['PK'] = i['PK'].hex()  
d['Sign'] = bls.Sign(i['PrivKey'],i['Vote'].encode()).hex()  
result.append(d)  
```  
Messages which are signed are only related with `i["Vote"]`, which values are
`"R"` or `"D"`. In order to get the flag, I must forge new signatures based on
given signatures.

#### Exploit: Get `bytexor(flag, fake_flag)`

I must satisfy three conditions: `challenge.Verify_aggregate()`,
`challenge.Get_Majority() == "R"`, `challenge.Verify_individual()`. I cannot
control `count` because It is saved at server side. The only data which I can
control is type of `vote`: `"R"` or `"D"`. Can I forge signatures which are
from `"D"`, to signatures which messages are `"R"`? Yes I can.

Provided messages are [first hashed](https://github.com/pcw109550/write-
up/blob/594bd578dc98c21562985849374fb4ed206d733d/2021/InCTF/Trouble_With_Pairs/BLS.py#L49)
using `sha256`. Let `s0` be the original signature which signed message `"D"`.
Let `m0 = hash(b"D", sha256)`, `m1 = hash(b"R", sha256)` which are all scalar.
My goal is to obtain valid signature `s1` which signed off `"R"`. `s0` is
derived as below. Let `PK` be private key(scalar) needed for signing, and `G2`
be generater point.

Derive `s0`:  
```python  
message_point_m0 = m0 * G2  
s0 = SK * message_point_m0  
= SK * m0 * G2  
```

Derive `s1` from `s0`:  
```python  
message_point_m1 = m1 * G2  
s1 = SK * message_point_m1  
= SK * m1 * G2  
= m1 * inverse(m0) * SK * m0 * G2  
= m1 * inverse(m0) * s0  
```

I know `m1`, `m0`, and `s0`. I can calculate `inverse(m0)` because I know the
order: `curve_order` of `bls12_381` curve used for signing. Import from
`py_ecc.optimized_bls12_381`.

Final method for signature forgery:  
```python  
def forgery(prev_sign_raw):  
s0 = signature_to_G2(bytes.fromhex(prev_sign_raw))  
m1 = hash(b"R", sha256)  
m0 = hash(b"D", sha256)  
s1 = G2_to_signature(multiply(s0, (m1 * inverse(m0, curve_order)) %
curve_order)).hex()  
return s1  
```  
It is quite simple because `py_ecc` library provides all the wrapper functions
and constants.

By forging all the signatures to make them signed off for `"R"`, I get the
first `bytexor(flag, fake_flag)`. One thing to be careful is that you must
provide at least single signature for `"D"`, or server will fail while running
`bls.Aggregate`.

I get first flag(hex format):  
```  
0b0753071d4c2a7d2000055907315546000800450075585d6c1a6e2b115931393f5c534d480e4400  
```

#### Exploit: Get `fake_flag`

Same idea with strategy of gaining the first flag, except at this time
`challenge.Verify_individual()` must fail. I still need to forge signatures to
make `"R"` be majority. In this case, the logic checks every single signatures
after aggregating. It will use individual's private key `PK` for verification.

To make this happen while `challenge.Verify_aggregate()` is True, I can simply
swap signatures which are signed to same messages.
`challenge.Verify_aggregate()` will success because it does not care about the
order of signatures which were aggregated. `bls.Verify` will fail for swapped
signatures because it will check the validity of signature using wrong private
key `PK`.

Swap first and third signatures which both signed `"R"`.  
```python  
if get_fake_flag:  
data[0]['Name'], data[2]['Name'] = data[2]['Name'], data[0]['Name']  
```

I get second flag:

```  
bi0s{7h1s_0n3_1s_n07_7h3_r1gh7_fl4g. :)}  
```

#### Exploit: Get real flag

XOR(`flag = strxor(flag_xor, fake_flag).decode()`) to get profit. I get flag:

```  
inctf{BLS_574nd5_f0r_B0n3h_Lynn_Sh4ch4m}  
```

exploit driver code: [solve.py](solve.py)

recovered serverside secret: [sercet.py](secret.py)

server driver code: [server.py](server.py)

exposed signatures: [data.py](data.py)

sign logic: [signer.py](signer.py)

BLS logic: [BLS.py](BLS.py)

Original writeup (https://github.com/pcw109550/write-
up/tree/master/2021/InCTF/Trouble_With_Pairs).