`secp256k1_ecdsa_signature_parse_der` mangles overflowing R/s values rather than rejecting them #1981

This issue is more minor than it might sound from the title. (Maybe it's even "not a bug" but I want to check.)

Consider the signature 304402206b5c3b1c86748dcf328b9f3a65e10085afcf5d1af5b40970d8ce3a9355e06b5b0220cdbdc23e6d3618e47056fccc60c5f73d1a542186705197e5791e97f0e6582a3201 from transaction 70f7c15c6f62139cc41afa858894650344eda9975b46656d893ee59df8914a3d. This is a badly-encoded signature because there is an overflowing s value, but the parse_der_lax function that Core uses accepts it, and in fact it validates and the transaction passes.

However, our secp256k1_ecdsa_signature_parse_der "parses" the signature as one where the s value is 0, which then fails validation. (See secp256k1_der_parse_integer where on overflow we zero out the return value, then return success.) This means that a user trying to call parse_der then "falling back" to parse_der_lax will reject the signature. More generally, the API provides no way for users to determine whether a signature that fails to validate failed because it's actually a bad sig,,or becasue it violates the BIP66 rules.

Maybe this is a non-goal of the API (or maybe it's a goal but nobody wants to touch consensus code to fix it), but it feels weird to me that the existing parser sometimes "parses" a signature into something that doesn't resemble the original signature. At the very least we should document this.

See https://git.rust-bitcoin.org/rust-bitcoin/rust-secp256k1/issues/1010 (or don't, because that issue is pretty sloppy).

This is a badly-encoded signature because there is an overflowing s value

The number is properly DER-encoded. It just happens to be out of bounds. But being in bounds is a requirement from ECDSA spec, not from the DER spec.

Maybe this is a non-goal of the API (or maybe it's a goal but nobody wants to touch consensus code to fix it), but it feels weird to me that the existing parser sometimes "parses" a signature into something that doesn't resemble the original signature. At the very least we should document this.

What's wrong with the current docs?

https://github.com/bitcoin-core/secp256k1/blob/307035b302eb7e9b5325638a377e64e6b29c41a3/include/secp256k1.h#L555-L562

The way I see it is this API guarantee makes a lot of sense. It keeps parsing and signature verification properly separated. What I'd ideally except from a parsing function is that it accepts any properly encoded signature. secp256k1_ecdsa_signature_parse_der does precisely this. DER can encode arbitrarily large integers, so it's entirely reasonable for secp256k1_ecdsa_signature_parse_der to accept arbitrarily large integers. Whether they're out of range (or what this even means) is a separate issue and belongs to signature verification.

The fact that the out-of-range values are internally set to 0 is an implementation detail. An API caller can't observe this.

This means that a user trying to call parse_der then "falling back" to parse_der_lax will reject the signature.

I think if we want to do anything here, then the docs of parse_der_lax could be improved. The behavior is documented but I agree that the implications, in particular when compared to parse_der, are not obvious:

https://github.com/bitcoin-core/secp256k1/blob/307035b302eb7e9b5325638a377e64e6b29c41a3/contrib/lax_der_parsing.h#L32-L35

(But see also #758)

More generally, the API provides no way for users to determine whether a signature that fails to validate failed because it's actually a bad sig,,or becasue it violates the BIP66 rules.

If I'm not mistaken the API precisely offers this way. BIP66 mandates strict DER encoding, precisely what secp256k1_ecdsa_signature_parse_der gives you.

As a side note, our Schnorr signature API avoids this separation issue entirely by just having a single function that does both parsing and verification. And that's most convenient and safest API: A (well-designed) caller should only care about whether a given signature is valid or invalid. Why it's invalid shouldn't matter, and indicating it to the caller only pushes more complexity in terms of reasoning and error handling to the caller.

However, Bitcoin violates this design rule when it comes to ECDSA, so we need to offer two separate functions. Quoting BIP 66:

[...] if the signature does not pass the IsValidSignatureEncoding check below, the entire script evaluates to false immediately. If the signature is valid DER, but does not pass ECDSA verification, opcode execution continues as it used to [...]

This is documented, though not clearly enough for the fallback case. include/secp256k1.h says parse_der "will accept any valid DER encoded signature, even if the encoded numbers are out of range", and that verification with such a signature then always fails. The s here is not an overflow: its top bit is set with no 0x00 pad, so it is valid DER for a negative integer. parse_der treats it like an s >= n and returns 1 with s = 0. That was the design when the parser was rewritten in 3bb9c44: "the data has to be exact DER, though the values inside don't need to be valid".

What the header does not say is that a negative R or s counts as out of range, and that a caller who tries parse_der first never reaches the lax fallback for such a signature. One sentence saying both would cover your case. Returning 0 for a negative integer would also allow the fallback, but it changes that documented behaviour.

For comparison, the strict parsers I tried (btcec ParseDERSignature, python-ecdsa, cryptography, bitcoinjs-lib's bip66) reject this signature. The lax ones (Core's ecdsa_signature_parse_der_lax, btcec ParseSignature) read s as unsigned, and it verifies. I can share the harness if useful.

More generally, the API provides no way for users to determine whether a signature that fails to validate failed because it's actually a bad sig,,or becasue it violates the BIP66 rules.

Let me add this: If you want to check whether a signature would have been valid before activation of BIP66, then I think you need to run the appropriate OpenSSL version. https://github.com/bitcoin-core/secp256k1/blob/master/contrib/lax_der_parsing.h#L44-L48 clearly says that ecdsa_signature_parse_der_lax isn't meant to mimick OpenSSL. It just accepts all the encoding violations that happen to be actually present on the pre-BIP66 chain.

Okay, great, thanks! I think we will copy the API docs from parse_der here onto rust-bitcoin's from_der and also add an explicit note that you can't do "try from_der then from_der_lax".