Utils: Improvements to ECDSA key-handling code

str4d commented at 6:43 am on June 23, 2017: contributor

Mostly trivial, but includes fixes to potential overflows in the ECDSA DER parsers.

Cherry-picked from Zcash PR https://github.com/zcash/zcash/pull/2335

in src/key.cpp:2 in d6c7ab9d27 outdated

0@@ -1,4 +1,5 @@
1 // Copyright (c) 2009-2016 The Bitcoin Core developers
2+// Copyright (c) 2017 The Zcash developers

jonasschnelli commented at 6:44 am on June 23, 2017:

I guess that’s not possible…

fanquake added the label Refactoring on Jun 23, 2017

in src/pubkey.cpp:78 in 6a42ccbb4f outdated

75             lenbyte--;
76         }
77-        if (lenbyte >= sizeof(size_t)) {
78+        static_assert(sizeof(size_t) >= 4, "size_t too small");
79+        if (lenbyte >= 4) {
80             return 0;

gmaxwell commented at 7:05 am on June 23, 2017:

This change breaks the intentional compatibility with OpenSSL behavior; it also makes the commit message inaccurately described.

It doesn’t matter for the Bitcoin system anymore because only strict DER matters there now, but this is otherwise an undisclosed consensus change (admittedly where OpenSSL creates inconsistency to begin with).

str4d commented at 7:58 am on June 23, 2017:

We made this change because the previous check was platform-dependent and therefore difficult to review for determinism (and also we don’t use the lax code at all, and have removed it). As far as being an undisclosed consensus change, it’s obviously not one that would end up affecting running consensus (because compilation would fail on the target machines this affects), but ACK that it would have been clearer in a separate commit. I can revert it for this PR if desired.

daira commented at 1:02 pm on June 23, 2017:

If lenbyte >= 4 here, then rlen calculated in the while loop just below will be >= 224 (because lenbyte at this point is the length of the representation of rlen after stripping leading zeros). So this function would in any case return 0 at line 90 if it does not return 0 here: the condition rlen > inputlen - pos would be true at line 90 since inputlen is at most the maximum block size, which is less than 224 bytes. @str4d’s reasoning is not quite correct; the above argument isn’t obvious and doesn’t hold just because of the static_assert. In any case there is no consensus change (it doesn’t matter whether we return 0 here or at line 90).

If this had actually made a difference, then there would have been a consensus incompatibility between 32-bit and 64-bit platforms, which would surely have been unintended. (I know that originally only 64-bit platforms were supported, but my understanding is that the current code is supposed to support both with no consensus differences.)

Edit: correct 232 to 224. (The most significant byte, which has weight at least 224 when lenbyte >= 4, must be at least 1.)

gmaxwell commented at 9:23 pm on June 23, 2017:

If this had actually made a difference, then there would have been a consensus incompatibility between 32-bit and 64-bit platforms, which would surely have been unintended.

It was intended to preserve exact compatibility with OpenSSL which has the same behavior. (particularly during a time when this behavior was embargoed both for us and OpenSSL)

And it very much made a different prior to BIP66, it doesn’t now– but this parsing function exists entirely for compatibility with OpenSSL and would not have been used if Bitcoin used BIP66 since day one.

daira commented at 9:04 pm on June 27, 2017:

It didn’t make any difference prior to BIP66, by the argument I gave above – fortunately, because it would have been possible to fork 32-bit nodes from 64-bit nodes otherwise.

It is basically never correct to have a platform-dependent consensus check. In this case, platform-dependent consensus code happened not to result in a difference in behaviour, essentially by luck. IMHO it’s a good idea to clean that up.

sipa commented at 11:10 pm on June 27, 2017:

@daira It is absolutely never correct to have platform-dependent consensus checks. However, Bitcoin used to indirectly have such a check through OpenSSL (fixed in CVE-2014-8275, see https://www.openssl.org/news/secadv/20150108.txt), and it was in fact possible to fork 32-bit nodes from 64-bit nodes. BIP66 was exactly intended to fix that problem (see https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-July/009697.html). The original code here just preserved the behaviour. No problem with removing the dependency now, though.

in src/pubkey.cpp:117 in 6a42ccbb4f outdated

114             lenbyte--;
115         }
116-        if (lenbyte >= sizeof(size_t)) {
117+        static_assert(sizeof(size_t) >= 4, "size_t too small");
118+        if (lenbyte >= 4) {
119             return 0;

gmaxwell commented at 7:05 am on June 23, 2017:

same here.

daira commented at 1:11 pm on June 23, 2017:

Same argument as above with rlen replaced by slen, and line 90 replaced by line 129.

in src/pubkey.cpp:51 in 6a42ccbb4f outdated

46@@ -46,7 +47,7 @@ static int ecdsa_signature_parse_der_lax(const secp256k1_context* ctx, secp256k1
47     lenbyte = input[pos++];
48     if (lenbyte & 0x80) {
49         lenbyte -= 0x80;
50-        if (pos + lenbyte > inputlen) {
51+        if (lenbyte > inputlen - pos) {
52             return 0;

gmaxwell commented at 7:15 am on June 23, 2017:

Help me understand how you believe there is a potential overflow here.

My meat based range analysis states: Pos always has value 2 here. Size_t lenbyte is 0-127 inclusive (after the subtraction takes it from a range of 128-255 inclusive). This means that the left side (which is all size_t) has a range of 2-129.

What am I missing? (As an aside, zcash really screwed up if there is any reason to use this lax parser in it; this code exists for compatibility with OpenSSL…)

gmaxwell commented at 7:17 am on June 23, 2017:

And likewise for the below.

str4d commented at 7:44 am on June 23, 2017:

See https://github.com/zcash/zcash/pull/2335#discussion_r114272216:

This is a different style to before but it’s still overflow-prone (for integer overflows this time).

So this change was included for consistency with the other changes, not necessarily because this specific instance suffers from overflow, but because that style of pointer comparison can be vulnerable, and it is better to have good style precedent. There’s no telling what future people might happen to do with that code snippet.

(As an aside, zcash really screwed up if there is any reason to use this lax parser in it; this code exists for compatibility with OpenSSL…)

In fact, we stripped out this code as unused and unnecessary in https://github.com/zcash/zcash/pull/2360, but for the purposes of upstreaming to Bitcoin Core where it was still present, we intentionally separated that change from these ones.

sipa commented at 11:22 pm on June 27, 2017: member

Thanks for upstreaming this!

utACK d6c7ab9d27a56f08d4072a352640d55d5e46f484

sipa commented at 8:59 pm on July 16, 2017: member

Needs rebase.

Fix potential overflows in ECDSA DER parsers a3603ac6f0

Add comments e181dbe748

Update Debian copyright list e4a10860a4

Specify ECDSA constant sizes as constants 17fa3913ef

Remove redundant `= 0` initialisations 48abe78e51

Ensure that ECDSA constant sizes are correctly-sized 1ce9f0a952

str4d force-pushed on Jul 17, 2017

str4d commented at 4:58 pm on July 17, 2017: contributor

Rebased on master to fix conflict (an adjacent line being changed).

in contrib/debian/copyright:18 in 1ce9f0a952 outdated

14@@ -15,6 +15,14 @@ Copyright: 2010-2011, Jonas Smedegaard <dr@jones.dk>
15            2011, Matt Corallo <matt@bluematt.me>
16 License: GPL-2+
17 
18+Files: src/secp256k1/build-aux/m4/ax_jni_include_dir.m4

TheBlueMatt commented at 3:37 pm on July 18, 2017:

These seem like rather unrelated changes? Can they go in a separate PR?

str4d commented at 4:21 pm on July 18, 2017:

They were related inasmuch as I was pulling in a collection of libsecp256k1 PRs from upstream, and this was a necessary libsecp256k1-related addition. From a Bitcoin PR perspective, I can split this out into a separate PR if desired.

TheBlueMatt commented at 3:54 pm on July 18, 2017: member

Looks like travis failed. I believe its unrelated, however.

in src/pubkey.h:20 in 1ce9f0a952 outdated

15@@ -15,10 +16,12 @@
16 
17 /**
18  * secp256k1:
19- * const unsigned int PRIVATE_KEY_SIZE = 279;
20- * const unsigned int PUBLIC_KEY_SIZE  = 65;
21- * const unsigned int SIGNATURE_SIZE   = 72;
22- *
23+ */
24+const unsigned int PUBLIC_KEY_SIZE             = 65;

theuni commented at 5:15 pm on July 18, 2017:

yikes, please don’t put these in the global namespace in a very public header file.

in src/key.h:22 in 1ce9f0a952 outdated

17@@ -17,17 +18,18 @@
18 
19 /**
20  * secp256k1:
21- * const unsigned int PRIVATE_KEY_SIZE = 279;
22- * const unsigned int PUBLIC_KEY_SIZE  = 65;
23- * const unsigned int SIGNATURE_SIZE   = 72;
24- *
25+ */
26+const unsigned int PRIVATE_KEY_SIZE            = 279;

theuni commented at 5:17 pm on July 18, 2017:

Same namespace issue here.

jnewbery commented at 5:17 pm on July 18, 2017: member

Looks like a spurious unrelated Travis failure.

laanwj commented at 1:29 pm on October 2, 2017: member

Needs comments by @cfields addressed, I agree putting constants such as PUBLIC_KEY_SIZE in the global namespace seems a bad idea, they should be scoped to some class.

Scope the ECDSA constant sizes to CPubKey / CKey classes 63179d0283

str4d commented at 1:44 pm on October 4, 2017: contributor

@laanwj addressed comments by @theuni.

laanwj commented at 4:18 pm on December 20, 2017: member

Thanks! utACK 63179d0

laanwj merged this on Dec 20, 2017

laanwj closed this on Dec 20, 2017

laanwj referenced this in commit 79399c8cd0 on Dec 20, 2017

str4d deleted the branch on Dec 20, 2017

classesjack referenced this in commit e758a6e437 on Dec 20, 2017

zkbot referenced this in commit db9f6f0485 on Jan 4, 2018

PastaPastaPasta referenced this in commit bd253fecfd on Feb 13, 2020

PastaPastaPasta referenced this in commit 904b5eebeb on Feb 27, 2020

PastaPastaPasta referenced this in commit 25de7e14b2 on Feb 27, 2020

PastaPastaPasta referenced this in commit dbbeb0aee4 on Feb 27, 2020

ckti referenced this in commit 65872e367b on Mar 28, 2021

gades referenced this in commit e8126395a9 on Jun 24, 2021

DrahtBot locked this on Sep 8, 2021

Utils: Improvements to ECDSA key-handling code #10657