Rare case when Schnorr's signature can't be verified

[StackOverflowExcept1on]

this case occurs with probability $\approx \frac{1}{ 2^{128} }$
ecrecover(e, v, r, s) accepts any e, 27/28 for v and r, s in [1, Secp256k1.N), where N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

suppose public key has pubKey.x >= N and in that case ecrecover will return address(0). so the protocol can't verify the signature. which means you lose control of the smart contract.

scribe/src/libs/LibSchnorr.sol

Lines 81 to 82 in 7d2106a

	// Set r = Pₓ
	uint r = pubKey.x;

r, s range:

• https://github.com/ethereum/go-ethereum/blob/06883c16861fc034e1471c4f911cd309612b1f7f/core/vm/contracts.go#L255
• https://github.com/ethereum/go-ethereum/blob/06883c16861fc034e1471c4f911cd309612b1f7f/crypto/crypto.go#L271

fix: if (!(pubKey.isOnCurve() && pubKey.x < LibSecp256k1.Q())) {

also need to reject pubKey.x >= Secp256k1.N for group public key on backend and at constructor?

scribe/src/libs/LibSchnorr.sol

Lines 36 to 38 in 7d2106a

	if (!pubKey.isOnCurve()) {
	return false;
	}

[pmerkleplant]

Thank you very much for raising the issue, this is an incredible finding!

Context

While the issue in essence is valid, ie there exist valid public keys with x >= N whose Schnorr signatures are not verifiable with LibSchnorr, it is important to note that this does not lead to "losing control of the smart contract". The poke will just not be accepted, leading to an at most delayed oracle update. The auth functionality is not impaired by this in any way. Further, the issue does not lead to a possibility of invalid pokes being accepted.

I agree that the probability of such a public key to occur is roughly $\frac{1}{2^{128}}$. Note that secp256k1's security in general is 128 bit due to birthday paradox and baby-step giant-step algorithm. Therefore, we determine this issue to be of negligible practical relevance.

Fix

I disagree with the recommended fix though. Instead of disallowing a valid subset of public keys to participate I would rather want to fix LibSchnorr itself by performing the necessary modulo operation on the x coordinate, ie:

- // Set r = Pₓ
- uint r = pubKey.x;
+ // Set r = Pₓ mod Q
+ uint r = pubKey.x % LibSecp256k1.Q();

Note that ecrecover internally will use r = Pₓ inside (mod Q) operations and, as modulo operations respect addition, its fine to reduce r = Pₓ beforehand.

This also nicely showcases that, indeed, the fundamental issue lies in the unintuitive constrains when (ab)using ecrecover for ecmul operations.

Next Steps

While we will prepare a new release candidate, it is important to note that we cannot release a new version without conducting external security reviews.