k256 Schnorr / BIP340 doesn't handle the y odd case

[randombit]

For both signature generation and verification, k256 doesn't seem to handle the case where the y coordinate of the public key is odd. I guess it is implicitly assuming that the user handles this, but this doesn't match how BIP340 describes the operation.

• When signing BIP340 specifies that the secret key is negated, if the y coordinate of G*sk would otherwise be odd. k256 doesn't do this, leading it to produce incorrect signatures for half of all secret keys.

• BIP340 defines verification as taking pk the 32-byte encoding of just the x coordinate. It then verifies on the assumption that the y coordinate is the even one. However k256 seems to assume/require that the public key is a point with both x and y coordinates, and y is even; then k256::schnorr::VerifyingKey::try_from rejects points with odd y. My understanding is that in such a case, the verification key does exist/is well formed; it just is the negation of the input point.

Both issues can be worked around by checking in advance if an odd y would occur and inverting the private or public key before use.

[tarcieri]

It did in my original implementation. It must've regressed at some point: https://github.com/RustCrypto/elliptic-curves/pull/482/files#diff-7ee5e04f685838d30d3bb56a9c532ffc01948c79f1c7a7faecc989186d803ee1R94-R98

[tarcieri]

@randombit on the SigningKey side of things, this logic should be handling it, eagerly inverting SigningKey in this case: https://github.com/RustCrypto/elliptic-curves/blob/a1fabfb/k256/src/schnorr/signing.rs#L124-L130

Are you encountering a codepath where this isn't happening, or do you want a lazy inversion instead of an eager one?

There are definitely test vectors in our suite which break if I remove that logic.

However k256 seems to assume/require that the public key is a point with both x and y coordinates

VerifyingKey::from_bytes uses AffinePoint::decompact which operates only on the x coordinate.

I guess that should be modified to try decompressing both odd and even y and going with whatever solution is valid.

[tarcieri]

@randombit can you provide a reproduction of where you think it's being mishandled?

[randombit]

I think the main thing that caught me up here is that k256::schnorr::VerifyingKey::try_from(AffinePoint) doesn't work if y is odd, and I didn't notice from_bytes. So I flipped the y of my public key points to make things work for verification. Then I checked signature generation and did not see any flip of the secret key happening there, missing that it happened during the type conversion instead. But it seems (outside from k256::schnorr::VerifyingKey::try_from rejecting points with odd y, which still doesn't seem right to me) everything is being correctly handled. Sorry for the noise.

[tarcieri]

outside from k256::schnorr::VerifyingKey::try_from rejecting points with odd y, which still doesn't seem right to me

It could be changed to auto-invert