BIP-0340 Schnorr-compatible signature invalidly uses NonZeroScalar

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...

Start at k256/src/schnorr.rs around lines 84–91 and compare the validator with the BIP-0340 verification criteria. Confirm how the current NonZeroScalar handling differs from the specification, and consider the work complete when valid BIP-0340 signatures with s equal to zero are not rejected.