search

RustCrypto / elliptic-curves

Collection of pure Rust elliptic curve implementations: NIST P-224, P-256, P-384, P-521, secp256k1, SM2
649 stars 178 forks source link

BIP-0340 Schnorr-compatible signature invalidly uses NonZeroScalar #925

Open kayabaNerve opened 1 year ago

kayabaNerve commented 1 year ago

BIP-0340's validator criteria doesn't require s is non-zero. While it does require R isn't identity, meaning s will be only be 0 for non-trivial cases, finding a valid signature with an s of 0 is reducible to the birthday problem AFAICT. Accordingly, it wouldn't have 2**128 complexity to find a valid signature such that s == 0, though I'm unsure how significantly reduced the complexity is.

The signature should match BIP-0340 and use Scalar, not NonZeroScalar.

This was commented on by the recent NCC Group audit, though they didn't follow up. (though I'm unsure why). Perhaps they didn't realize the likelihood of a BIP-0340 compliant signature which k256 would rejected was less than 2**128.

References:

https://github.com/RustCrypto/elliptic-curves/blob/e38513e7c519b5391199e62cfd233225638352c6/k256/src/schnorr.rs#L84-L91 https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki#verification

Edited to strikeout my misinformed thoughts. While this is the birthday problem, I don't believe an efficient algorithm for solving it exists given how the challenge is binding, meaning this would only break with 2**128 computational complexity AFAIK. Regardless, it's still a spec break...

tarcieri commented 1 year ago

The accessor(s) for s all return NonZeroScalar, so fixing this will require breaking changes.

We can do it as part of the next breaking release.