Distinguish ECDSA malleability?

[gmaxwell]

Libsecp256k1 implements a variant of ECDSA used by the Bitcoin system (and many other things now) which eliminates malleability by requiring s to be in the lower half of its range. Callers that need compatible (but vulnerable...) behaviour are instructed by the documentation to call a provided normalize function on signatures before validating them.

Someone opened an issue reporting that secp256k1 ecdsa sha256 test case 218 fails. I confirmed that this failure is due exclusively to this restriction.

You can expect other secp256k1 implementations to implement similar things as this behaviour is required for consensus consistency with Bitcoin, so it might be useful to avoid gratuitously triggering this incompatibility, and flag tests that necessarily do so (e.g. because they are intentionally trying to use high S values).

Thanks for the interesting work. Although we have very extensive testing already, I think a diverse test cases created by a different set of minds will be a valuable addition to our testing arsenal.

You may be interested in a different test strategy, implemented by our "exhaustive" tests based on the observation the virtually all code in an ECC library is independent of b in the curve equation (usually only point decompression/validation depends on it). We use this fact to allow a test harness to build an alternative version of the library that operates using a different curve equation on a small sgroup (e.g. of size 43) where we can do things like exhaustively test group operations. We've shown this test to be effective at detecting some real but otherwise incredibly hard to detect bugs, such as cases of incorrectly handled group law incompleteness. As a result it might be interesting to publish vectors for these easily tested degenerate groups.

[bleichen]

Is there an RFC or other documentation defining the requirements?

I.e., instead of trying to mix schemes, I'd rather generate separate test vectors for
"Bitcoin-ECDSA". If the signatures are DER encoded then I'd also expect that
all BER alternatives must be rejected.

Almost all of the libraries that I'm testing use special case code for the main
curves. Hence test vectors with special cases need to be included for all the curves.
In a lot of cases, I generate such test vectors by starting with the
edge case point addition and then compute corresponding keys and signatures.
I'll look into adding test with degenerate curves for other cases.

[real-or-random]

There are two restrictions enforced by libsecp256k1:

• The S value is between 0x1 and 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0, inclusive. See https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1.h#L458
• The signature is exactly DER-encoded. See BIP66 for well-documented C++ code for convenience.

edit: Maybe "Bitcoin-ECDSA" isn't the best name for it, because this is a tricky story. There is a discrepancy between what signatures are allowed in the Bitcoin blockchain, what signatures will be relayed in the P2P network by different implementations of Bitcoin and what signatures will be produced by those different implementations. (All due to historical reasons because OpenSSL was not strict about the things mentioned above). I'd suggest calling it "libsecp256k1-ECDSA" or something.

[bleichen]

Thanks for the pointers. I'm generating a separate file with test vectors for "Bitcoin-ECDSA". This makes it easier to specify how an implementation should behave. Another reason is that replacing s by n-s can destroy edge-case test vectors, especially stuff that tries to trigger edge case addition chains.

…

On Wed, Apr 17, 2019 at 10:40 PM Tim Ruffing ***@***.***> wrote: There are two restrictions enforced by libsecp256k1: - The S value is between 0x1 and 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0, inclusive. See https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1.h#L458 - The signature is exactly DER-encoded. See BIP66 <https://github.com/bitcoin/bips/blob/master/bip-0066.mediawiki> for well-documented C++ code for convenience. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#70 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AGGH7XSOXBN52FR75KANVATPQ6DMZANCNFSM4HFQAV6A> .

[real-or-random]

Two minor notes:

Funnily, #65 reports that wycheproof helped to discover a signature malleability due to high S values in EdDSA.

I had edited my previous comment to add a paragraph about naming. I assume you missed that paragraph (because you replied via email.)

[gmaxwell]

No objection to calling it whatever you like, but you should be aware that the considerations extent outside Bitcoin, e.g. OpenSSL certificate blacklisting is vulnerable due to this malleability (I can take a valid ECDSA using certificate and make another one which is also valid but has a different hash). So it would be reasonable to expect totally bitcoin unrelated systems to adopt an equivalent countermeasure -- though potentially they might adopt a different tiebreaker, there are several options. We favoured this one because it was appeared the simplest for calling software to implement as a wrapper around a weaker signer/verifier.

[briansmith]

I can take a valid ECDSA using certificate and make another one which is also valid but has a different hash

There are multiple ways of doing that. Blacklisting certificates that way doesn't work in general, and doing that should be considered a bug with potentially serious security consequences.

[gmaxwell]

Maybe, but OpenSSL issued a CVE and a fix for evasion of hash based blacklisted based on using BER extensions in signatures: CVE-2014-8275. Use of ECDSA malleability appears to be an almost equally powerful way to exploit the same vulnerability, it's only weaker in that there are only two possible hashes.

[real-or-random]

Thanks for the pointers. I'm generating a separate file with test vectors for "Bitcoin-ECDSA". This makes it easier to specify how an implementation should behave.

Just a friendly reminder. Has there been progress on this?

[bleichen]

I have the test vectors, but I need some implementations to test against. I sometimes make mistakes, hence I don't want to publish anything without sanity checks.

…

On Mon, Oct 18, 2021 at 11:27 AM Tim Ruffing ***@***.***> wrote: Thanks for the pointers. I'm generating a separate file with test vectors for "Bitcoin-ECDSA". This makes it easier to specify how an implementation should behave. Just a friendly reminder. Has there been progress on this? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#70 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AGGH7XS6PCTNK2D4ER7HBYTUHPR77ANCNFSM4HFQAV6A> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[real-or-random]

Thanks, that's nice to hear! I think then libsecp256k1 would be the first thing to test against. Maybe bitcoin-core/secp256k1#609 helps as a starter.

Or I believe we could also help by providing an integration here. From what I understand, this repo targets Java but the test vectors were used also for C projects. How did other C libraries use the test vectors in practice?

[real-or-random]

Is there any update on this?

[real-or-random]

I believe this has been solved by fcee28b, thanks!