Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
randombit opened this issue Aug 12, 2024 · 5 comments
Open

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

randombit opened this issue Aug 12, 2024 · 5 comments

Comments

@randombit
Copy link
Contributor

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
Copy link
Member

@tarcieri
Copy link
Member

tarcieri commented Aug 17, 2024

@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
Copy link
Member

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

@randombit
Copy link
Contributor Author

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 tarcieri reopened this Sep 18, 2024
@tarcieri
Copy link
Member

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants