Tags: crypto bls
Rating:
# 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)
