dusk-network/bls12_381-bls

Implementation of BLS signatures using the BLS12-381 curve

Implementation of BLS signatures using the BLS12-381 curve.

This implementation currently only supports rogue-key attack resistant batching, and does not support distinct message verification.

Benchmarks

Machine specs

The benchmarks were ran on a 2020 13.3" MacBook Pro.

CPU:

$ lscpu
Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz

RAM:

16 GB 3733 MHz LPDDR4X

Results

test benches::bench_aggregate_pk    ... bench:   1,654,552 ns/iter (+/- 107,025)
test benches::bench_aggregate_sig   ... bench:      36,893 ns/iter (+/- 3,399)
test benches::bench_sign            ... bench:   1,480,169 ns/iter (+/- 106,151)
test benches::bench_sign_vulnerable ... bench:   1,024,052 ns/iter (+/- 111,395)
test benches::bench_verify          ... bench:   4,740,114 ns/iter (+/- 336,036)

bls12_381-bls's Issues

Fix Hash to scalar incomplete

Summary

From the audit report point BLS01:

The h() function in hash.rs hashes to a subgroup element by truncating
a 64-byte BLAKE2B hash to BlsScalar::SIZE=32 bytes, then clearing the
top 2 bytes to obtain a value less than 2²⁵⁴:

/// Hash an arbitrary slice of bytes into a [`BlsScalar`]
fn h(msg: &[u8]) -> BlsScalar {
    let mut digest: [u8; BlsScalar::SIZE] = Blake2b::digest(msg).into();

    // Truncate the contract id to fit bls
    digest[31] &= 0x3f;

    let hash: Option<BlsScalar> = BlsScalar::from_bytes(&digest).into();
    hash.unwrap_or_default()
}

However with such an implementation, certain subgroup elements cannot be
reached: as the subgroup size
0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001 is
approx. 2^254.857.

It means that certain points will never be reached by h0(), and
certain scalars will never be reached by h1() (approx.
2^253.7.

This appears to us not to be exploitable, but it would be safer to
implement the standard hash_to_field() function, as defined in the
Hashing to Ellpitic
Curve
RFC and implemented in
zkcrypto/bls12_381.

Possible Solution

We can use our BlsScalar::hash_to_scalar(msg) here.

Missing check in public key aggregation

Summary

From audit finding BLS-04:

For the same reasons as in BLS-03 (#7), the public key aggregation function
omits the identity check, though will do the subgroup check when
instantiated with from_bytes():

    pub fn aggregate(&mut self, pks: &[PublicKey]) {
        #[cfg(feature = "parallel")]
        let iter = pks.par_iter();

        #[cfg(not(feature = "parallel"))]
        let iter = pks.iter();

        let sum: G2Projective = iter
            .map(|pk| dusk_bls12_381::G2Projective::from(pk.pk_t()))
            .sum();
        (self.0).0 = ((self.0).0 + sum).into();
    }

Likewise, is_valid() may be used, or just is_identity().

Note that the signature aggregation does not require an identity check.

Missing check in signature verification

Summary

From audit finding BLS-03:

Secure verification of BLS signatures requires several checks, as
described in the reference IETF Internet Draft
(section 2.7):

result = CoreVerify(PK, message, signature)

Inputs:
- PK, a public key in the format output by SkToPk.
- message, an octet string.
- signature, an octet string in the format output by CoreSign.

Outputs:
- result, either VALID or INVALID.

Procedure:
1. R = signature_to_point(signature)
2. If R is INVALID, return INVALID
3. If signature_subgroup_check(R) is INVALID, return INVALID
4. If KeyValidate(PK) is INVALID, return INVALID
5. xP = pubkey_to_point(PK)
6. Q = hash_to_point(message)
7. C1 = pairing(Q, xP)
8. C2 = pairing(R, P)
9. If C1 == C2, return VALID, else return INVALID

where KeyValidate() checks that a public key is a curve point in the
subgroup and is not the identity element.

However, the implementation in keys/public.rs does not do all these
required checks:

impl PublicKey {
    /// Verify a [`Signature`] by comparing the results of the two pairing
    /// operations: e(sig, g_2) == e(Hₒ(m), pk).
    pub fn verify(&self, sig: &Signature, msg: &[u8]) -> Result<(), Error> {
        let h0m = h0(msg);
        let p1 = dusk_bls12_381::pairing(&sig.0, &G2Affine::generator());
        let p2 = dusk_bls12_381::pairing(&h0m, &self.0);

        if p1.eq(&p2) {
            Ok(())
        } else {
            Err(Error::InvalidSignature)
        }
    }

Specifically, the public key may be checked to be on the curve and in
the subgroup when instantiated with from_bytes() or from a secret key,
however these do not guarantee that the point is not the identity. To
check the public key, the is_valid() defined in keys/public.rs may be
used.

The signature, as a point, would be checked to be valid (on the curve,
in the subgroup) when instantiated via the from_bytes() method of the
underlying library.

To verify that an invalid public key is accepted in signature generation
and verification, we can run the following test:

fn pktest() {

    let rng = &mut StdRng::seed_from_u64(0xbeef);
    let msg = random_message(rng);
    let sk = SecretKey::from(BlsScalar::zero());
    let pk = PublicKey::from(&sk);
    let sig = sk.sign_vulnerable(&msg);

    assert!(pk.verify(&sig, &msg).is_ok());
    assert!(pk.is_valid())
}

The first assert will pass, only the second will fail:

thread 'pktest' panicked at tests/signature.rs:24:5:
assertion failed: pk.is_valid()

Secret velues not erased

Summary

From the audit point BLS-02:

Secret values allocated to memory are not securely erased after going
out of scope. There is no perfect solution to consistently address that
issue, but the zeroize crate
is probably the best option out there. It's relatively easy to
integrate, by assigning the Zeroize trait, and is no_std like the
library.