[Security] Harden against seemingly valid BLS signature

[mratsim]

The following snippet will be parsed as a valid BLS signature but will be initialized as the infinity point:

import blscurve

let sigbytes = @[byte 217, 149, 255, 97, 73, 133, 236, 43, 248, 34, 30, 10, 15, 45, 82, 72, 243, 179, 53, 17, 27, 17, 248, 180, 7, 92, 200, 153, 11, 3, 111, 137, 124, 171, 29, 218, 191, 246, 148, 57, 160, 50, 232, 129, 81, 90, 72, 161, 110, 138, 243, 116, 0, 88, 125, 180, 67, 153, 194, 181, 117, 152, 166, 147, 13, 77, 15, 91, 33, 50, 140, 199, 150, 10, 15, 10, 209, 165, 38, 57, 56, 114, 175, 29, 49, 11, 11, 126, 55, 189, 170, 46, 218, 240, 189, 144]

var sig: Signature

let success = init(sig, sigbytes)

echo success
echo sig

see also: status-im/nim-blscurve#29

[cheatfate]

Because this signature is valid according to specification https://github.com/ethereum/eth2.0-specs/blob/dev/specs/bls_signature.md.

Because Signature is a G2 point, it follows this rule:

if b_flag1 == 1 then a_flag1 == x1 == x2 == 0 and (z1, z2) represents the point at infinity.

According to:

Respecting bit ordering, z is decomposed as (c_flag, b_flag, a_flag, x)

b_flag1 is 6th bit of the first byte in binary signature blob, in your current example first byte is 0xD9 (217) it has 1101_1001 representation. As we can see here 6th bit is set so this signature represents point at infinity.

[arnetheduck]

so.. what's the outcome here? how is it handled in libraries?

[mratsim]

It's an invalid encoding of an infinity point.

The issue is that a signature is represented as a (G1, G1) with G1 using 381 bits out of 48 bytes (384 bits) and some of the extra 3 bits are used as flags according to the Zcash serialization spec: https://github.com/zcash/librustzcash/tree/f55f094e/pairing/src/bls12_381#serialization
Note that the Zcash serialization spec is recommended in IETF (https://tools.ietf.org/id/draft-irtf-cfrg-pairing-friendly-curves-07.html#name-zcash-serialization-format-)

The Ethereum test generators has a 50% chance of setting this infinity bit to 1. But if it's set to 1, the rest of the bits should be set to 0.

The NBC fix is that this was raised with test data for the SSZ test vectors, for this suite we only need opaque blob, we never need to deserialize the signatures.

The crypto fix is to always reject invalid encoding of infinity points.

In BLST this is done by copying the input bytes, then checking if they were all zeros: https://github.com/supranational/blst/blob/27d3083e/src/e2.c#L300-L307

This is not done in Milagro

[mratsim]

See chapter 3.1, we need to fix Milagro https://raw.githubusercontent.com/cryptosubtlety/zero/main/0.pdf

Note: in terms of technical implications, we have all the validator pubkeys and they can't be zero so for individual signatures there is no issue.
For batching / aggregateVerify, we don't support batching in Milagro and in BLST we have blinding factors to avoid splitting zeros attacks.
For fastAggregateVerify, I'm still trying to understand the implications.

[cryptosubtlety]

I added a new section 5 "A plausible attack scenario at the protocol layer" and its partial PoC attack (https://eprint.iacr.org/2021/323.pdf.) . I hope that the section can at least give you hints or ideas to improve attack or defend yourself. Cheers.

[mratsim]

Closed by #121 in Milagro/Miracl (never an issue in BLST or on mainnet as BLST was default before Dec 1, 2020).

Dedicated test case scheduled in status-im/nim-blscurve#130