BIP-0340 Schnorr-compatible signature invalidly uses NonZeroScalar

[kayabaNerve]

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:

elliptic-curves/k256/src/schnorr.rs

Lines 84 to 91 in e38513e

	/// Taproot Schnorr signature as defined in [BIP340].
	///
	/// [BIP340]: https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki
	#[derive(Copy, Clone)]
	pub struct Signature {
	r: FieldElement,
	s: NonZeroScalar,
	}

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]

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.