Openssl bump #5634

Bump to 1.0.1k and cope with its more strict DER checks.

ACK: code reviewed, and fixes unit test errors running on OSX with OpenSSL 1.0.1k

untested ACK

tested ACK

@sipa afaik the iterator isn't guaranteed to be a pointer to the element there. Added an early return instead, you ok with that?

Tested ACK. (tests and a invalidate/reconsider loop back to 338221. Reindexed without checkpoints from 0 to 198k (still in progress))

Also +1 Tested ACK from an anonymous tester on IRC.

ut ACK

Tested ACK. As mentioned by Gavin, verified this fixes the unit tests on OSX when building with 1.0.1k

Un

tested ack, invalidated to 322000 reconsidered upto 327086 (still running)

tested ACK, -checkpoints=0 reindexes on testnet and mainnet.

This patch serves no purpose other than providing a "hack" around a flaw in the Bitcoin core. Previously OpenSSL did not look for invalid DER encoded data with possible trailing garbage but in the latest version it does. The actual problem is that Bitcoin accepts invalid DER encoded signatures and this is completely unrelated to OpenSSL. Now you are taking the invalid-DER encoded data and DER encoding it before calling ECDSA_verify. Because of this the same operation will be performed twice for every signature verification wasting CPU cycles. You MUST always DER encode your signature before passing it off to OpenSSL and this is nothing new. So this being "low" on OpenSSL's list is correct from my expert opinion as it is only performing validation and Bitcoin is passing invalid data.

ECDSA_verify:

int ECDSA_verify(int type, const unsigned char *dgst, int dgst_len,
    const unsigned char *sigbuf, int sig_len, EC_KEY *eckey)
{
ECDSA_SIG *s;
const unsigned char *p = sigbuf;
unsigned char *der = NULL;
int derlen = -1;
int ret=-1;

s = ECDSA_SIG_new();
if (s == NULL) return(ret);
if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL) goto err;
/* Ensure signature uses DER and doesn't have trailing garbage */
derlen = i2d_ECDSA_SIG(s, &der);
if (derlen != sig_len || memcmp(sigbuf, der, derlen))
    goto err;
ret=ECDSA_do_verify(dgst, dgst_len, s, eckey);
err:
if (derlen > 0)
    {
    OPENSSL_cleanse(der, derlen);
    OPENSSL_free(der);
    }
ECDSA_SIG_free(s);
return(ret);
}

@john-connor It is quite relevant in consensus systems, which must maintain bug-for-bug compatibility. It is impossible to rewind history, and un-accept signatures that have been previously accepted.

@jgarzik The bug is in Bitcoin, not OpenSSL. This patch does not fix the bug. It is a hack.

@jgarzik I know the blockchain is permanently flawed because of this bug but gavin and everybody else is blaming OpenSSL it seems. Accept the fact that Bitcoin core has a major flaw in that it does not DER encode signatures. This is something that could become fatal to Bitcoin in the future if OpenSSL were to further enforce it's fully understood rules. Why not fix the problem and hard fork instead of hacking the code?

@john-connor "Trailing garbage" is technically incorrect. What OpenSSL's ECDSA_verify previously supported was a very broad subset of BER. For example, encoding R and S with leading zeros. This is substantive, non-backwards compatible, arguably somewhat under-disclosed (seems that you were also unaware of the actual change, in that you refer to it as "trailing garbage"), breaking API change from the existing and widely known behavior. Signatures come from the outside world (Bitcoin Core itself has never generated anything but strictly minimal encodings), and the decoding functions are OpenSSL internal. As a result previously accepted encodings (and not just 'trailing garbage') will be rejected.

While this may not matter for most applications, a switch to be more conservative is not something that can be done in an uncoordinated way for a consensus system without resulting in an opening for funds loss. This is just the state of things, and not a question of "flaw" or blame. My description (http://sourceforge.net/p/bitcoin/mailman/message/33221963/) of the matter is just a statement of the facts about it.

The flaw was that Bitcoin relied on non-consensus-safe code (OpenSSL) for consensus. If OpenSSL does not want to guarantee consensus-compatible behaviour for invalid signatures, that's fine for them, but it breaks Bitcoin. The plan has been to close this issue in Bitcoin for a long time, and it would have been nice if OpenSSL took care breaking compatibility everywhere in a mere bugfix release. Note that a hardfork (or even a softfork) to fix this is not something we can do overnight, as we do not have any kind of authoritative control the protocol: making a change requires the consensus of every Bitcoin user, and coordination of that is a time consuming process that generally takes months.

Note that with Bitcoin (and I imagine most scenarios you'd be verifying a signature!), signatures are from an external source, so you can't say "just encode them right"... any signature-checking code really should assume the signature is untrusted data and possibly an attempt to perform a remote exploit.

Also note that Bitcoin Core has itself generated only DER-compatible signatures for a long time.

@gmaxwell Right, Bitcoin has a flaw in that it does not and never did perform DER encoding of it's signatures and had it done so we would not be having this discussion.

@luke-jr Wrong, OpenSSL is fine and it's output would not change to have an effect on consensus in the Bitcoin system. Bitcoin is broke in this context. You can shift blame to OpenSSL if you wish.

never did perform DER encoding

I'm afraid your statements don't really make a lot of sense. Signatures emitted by Bitcoin core are correctly DER encoded. OpenSSL provides a verify function which takes a string of bytes with an already encoded signature from the outside world. This is its documented behavior, and it's how OpenSSL itself uses it. I would be surprised if you were able to find a single prior user of that function which pre-parsed to verify or re-encoded the inputs before handing them to OpenSSL.

As previously mentioned, we have had work in progress previously to reduce the systems dependence on OpenSSL's behavior here. But such changes must be coordinated.

@gmaxwell Wrong, Bitcoin has failed to ensure it DER encodes the signature properly since day one. OpenSSL did not break anything but instead brought this to light. Now as a hack you are DER encoding the data so OpenSSL won't reject it when you send it to the library which is what should have always been done. Instead bitcoin passing a raw sha256 hash that may or may not be DER encoded. What makes you assume that the hashes are in fact DER encoded? :)

@john-connor That is like saying "HTTP failed to ensure..." Bitcoin is a protocol. Many different softwares generate signatures. Bitcoin used OpenSSL to validate those signatures generated by $manywares. That validation just changed without notice.

@jgarzik The validation did not change. It just became more strict. The fact that non-DER data is being passed into OpenSSL is Bitcoin's bug. This hack-around is wasting CPU cycles and should be fixed properly after a certain block # way in the future with an organized hard fork. This will make sure that Bitcoin doesn't break again in the future for similar reasons.

@john-connor More strict validation can definitely be a breaking change with security implications. The most obvious is DoS attacks, but in a system where a signature can be a right to something valuable it can result in monetary loss as well: http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg06686.html

In any case, in the future Bitcoin will likely move from OpenSSL to using libsecp256k1 library written by Pieter Wuille - a long-time Bitcoin Core developer - which is better suited to our unique needs.

Instead bitcoin passing a raw sha256 hash that may or may not be DER encoded. What makes you assume that the hashes are in fact DER encoded? :)

You appear to be quite mistaken at what the code in question is actually doing; signatures != hashes.

Where in code does Bitcoin core perform DER encoding of the signature properly?

https://github.com/bitcoin/bitcoin/blob/master/src/secp256k1/src/ecdsa_impl.h#L90 (In the current tree)

The problem with Bitcoin core is that secp256k1_ecdsa_sign_compact does NOT DER encode the output nor is it encoded into DER format at any point thereafter. This is why it became broken with the improved integrity checking that the latest OpenSSL brought. So "compact signatures" have always operated in a broken manner because of this flaw in the Bitcoin core. This bug does not have any relations to "network consensus" like Gavin has stated. All cryptographic signatures that leave the wire or a stored to disk MUST always be encoded in some manner using DER or otherwise to maintain compatibility and platform neutrality. It should be fixed properly to ensure the security of the system IMHO as this is a flaw in the sign and verify feature of Bitcoin core.

@john-connor No, thats incorrect. sign_compact signatures are not used inside the Bitcoin network or blockchain, and are not verified (and cannot be verified) by OpenSSL's ECDSA_verify.

Compact signatures encode different data, and are fundamentally incompatible with that encoding. They're also completely unrelated to this (as mentioned, not used on the Bitcoin network), and nothing related to them was broken by the update to OpenSSL.

So please explain why signature verification is failing? What is wrong with them? You claim they are "properly DER encoded" so if that is true then what you claim happened couldn't have happened.

Something is strange here.

@john-connor There is nothing sloppy about it. I'm afraid you're operating outside of your expertise here. I'd generally be happy to educate you (or anyone else), but your continued antagonism is tiring. In this case; You're complaining about not using DER encoding for data which cannot be DER encoded and is never passed to a function that expects DER encoding.

So please explain why signature verification is failing?

Because while Bitcoin core generates and has always generated strictly encoded valid DER for transactions, third party implementations such as Armory, Blockchain.info, and MTGOX (among many others) previously generated signatures with excessive padding (e.g. additional leading zeros inside R and S instead of the shortest possible encoding). From time to time old (or new) instances of this continue to crop up. In the past the establish software, based on OpenSSL, accepted these signatures since OpenSSL provided no method to distinguish these signatures from a non-excessively padded signature and it happily decoded them. The updated OpenSSL decodes and reencodes the signatures and the result is a shorter encoding, which it rejects.

Because Bitcoin is a consensus system all participants must agree on if a particular string of bytes is valid signature or not, or the blockchain can diverge as a result of their disagreement.

can't happen

This simple concept of what can and cannot happen based on what Bitcoin Core would send is too narrow for working in a public network, especially under adversarial conditions. Any sequence of bits that can be sent, probably will be sent, especially if they trigger interesting behavior.

The Bitcoin core SHOULD remove this "padding" when it deserializes the data so the problem is immediately eliminated and does not make it into "the machinery". Any TLV network protocol is immune to this. My assumption is that if you try to fix the problem then you'd have to hard fork the network. Now the Bitcoin blockchain remains polluted with invalid signatures that can never be verified without this "hack-around". Satoshi Nakamoto didn't understand networking too well nor the concepts of platform neutrality back then so I understand how this has happened, thanks.

The Bitcoin core SHOULD remove this "padding" when it deserializes the data

The deseralization is inside OpenSSL's ECDSA_verify, the padding in question is actually inside the DER signature after the length fields (its part of the numbers themselves). As your own comments above indicate, no one would expect to need to decode, then reencode (doing so would be arguably a bad practice), especially for data passed into a function when it's express purpose was to take data from the outside world. And, as I pointed out above you're not likely to find any user in the world who did this.

It certainly would have been preferable to not depend on the construction and behavior of OpenSSL's deseralizer, but without reading the OpenSSL code carefully you'd never know how much hidden behavior it has, none of this has to do with portability platform neutrality though; it's a question of consensus consistency.

As far as fixes. We have more tools at our disposal than just hard forks.

My final words on this: http://vanillacoin.net/forums/viewtopic.php?pid=1967#p1967

Your claims there continue to be confused and incorrect. Notice above that I pointed out "In the past the establish software"-- subsequently Bitcoin Core implemented default local node policy to not relay incorrectly encoded signatures (by testing the transactions with it's own strict DER decoder, https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L89) as the first step in a process to eliminate them. This widely announced change delayed transactions for software which continued to produce them.

Do not mistake your own ignorance about the technology or the history for any dishonesty on my part. But please feel free to discontinue posting on our repository if you're unwilling to conduct yourself in a professional manner.

I may be misreading the OpenSSL documentation, however doesn't d2i_ECDSA_SIG always create a new ECDSA_SIG? So, given it's passed a reference to the pointer, the one allocated at https://github.com/bitcoin/bitcoin/pull/5634/files#diff-62cfc3439aea7461011d2394accbf82bR125 is in fact lost, if I'm reading this correctly?

@rnicoll

The documentation does say that.... but openssl itself seems to be calling ECDSA_SIG_new() before d2i_ECDSA_SIG.

Possibly there's a memory leak in openssl itself here.

@rnicoll Objectively, the current version does not leak (I tested with valgrind.) OpenSSL itself allocates first, so preserving its own behavior seemed to be conservative. The code in question appears to check the nullness of the pointer and allocates only if null, meaning the documentation is actually dangerously incorrect (since if you believed the documentation you may send uninitialized memory in there and have it fail to allocate).

Thanks for noticing th documentation disagreed, previously I'd just valgrinded and checked the code.

@gmaxwell Great, thanks for checking.

d2i_ECDSA_SIG does indeed segfault if passed an uninitialized pointer.

https://gist.github.com/pstratem/7d31cf5f35d78640247f

Would there be a new point release or a patch for 0.9.3? This cannot be cleanly applied to 0.9.3 as-is (ecwrapper.cpp is missing), and I thought it would be better to ask anyway to avoid blindly patching critical piece of software.

Try checking out and/or cherry-picking from the v0.9.4 tag, it has the same changes.

I'll just checkout v0.9.4 then. Thanks!