Discussion:
[bitcoin-dev] Disclosure: consensus bug indirectly solved by BIP66
Pieter Wuille via bitcoin-dev
2015-07-28 14:27:18 UTC
Permalink
Hello all,

I'd like to disclose a vulnerability I discovered in September 2014,
which became unexploitable when BIP66's 95% threshold was reached
earlier this month.

## Short description:

A specially-crafted transaction could have forked the blockchain
between nodes:
* using OpenSSL on a 32-bit systems and on 64-bit Windows systems
* using OpenSSL on non-Windows 64-bit systems (Linux, OSX, ...)
* using some non-OpenSSL codebases for parsing signatures

## Upgrade instructions:

None. Transactions that could trigger this problem have become invalid
on the network since BIP66's deployment of version 3 blocks reached 95%
on July 4th, 2015.

## Long description:

The problem is related to the signature encoding rules.

Bitcoin's signatures are ASN.1 BER encoded. BER is a complex standard
that allows many different encodings for the same data. Since Bitcoin
Core 0.8, a standardness rule has been in effect that only allowed
subset of encodings (DER) for relay and mining, even though any BER
remained valid in the blockchain - at least in theory.

In practice, BER has many weird edge cases, and I have not found a
single cryptographic codebase that can parse all of them correctly.
This includes OpenSSL, Crypto++, BouncyCastle, btcec, and our own
libsecp256k1 library.

This on itself would not be a problem, as full nodes on the network
currently use OpenSSL. However, while researching what was needed to
make libsecp256k1 compatible with it, I discovered that OpenSSL is even
inconsistent with itself across different platforms.

One of the features of BER is the ability for internal structures to
have a length descriptor whose size itself is up to 126 bytes (see
X.690-0207 8.1.3.5). A 1 terabyte data structure would for example use
a 5-byte length descriptor. However, there is no requirement to use the
shortest possible descriptor, so even a 70-byte ECDSA signature could
use a 5-byte length descriptor and be valid. Unfortunately, OpenSSL
supports length descriptors only as long as their size is at most that
of a C 'long int', a type whose size depends on the platform (Windows
and 32-bit Linux/OSX have a 4-byte long int, 64-bit Linux/OSX have an
8-byte long int). See
https://github.com/openssl/openssl/blob/bfa34f551c2d38e826deb44a269cb0f720f9f63b/crypto/asn1/asn1_lib.c#L178.
Some non-OpenSSL based signature validation
systems don't support such length descriptors at all, resulting in an
extra forking risk on top for them if used for blockchain validation.

This effectively means that a block chain containing a transaction with
a valid signature using such a 5-byte length descriptor would be
accepted by some systems and not by others, resulting in a fork if it
were mined into a block.

## Timeline:

* 2013-Feb-19: Bitcoin Core 0.8.0 was released, which made non-DER
signatures non-standard. No release since then would relay or mine
transactions that could trigger the vulnerability. However, such a
transaction was still valid inside blocks.

* 2014-Feb-10: I proposed BIP62 to deal with transaction malleability.
The BIP62 draft includes a rule that would make version 2 transactions
with non-DER signatures invalid.

* 2014-Jul-18: In order to make Bitcoin's signature encoding rules not
depend on OpenSSL's specific parser, I modified the BIP62 proposal to
have its strict DER signatures requirement also apply to version 1
transactions. No non-DER signatures were being mined into blocks
anymore at the time, so this was assumed to not have any impact. See
https://github.com/bitcoin/bips/pull/90 and
http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2014-July/006299.html.
Unknown at the time, but if deployed this would have solved the
vulnerability.

* 2014-Sep-01: While analysing OpenSSL's source code for BER parsing, I
discovered the architecture dependency listed above and the associated
vulnerability. The best means to fix it at the time was by getting
BIP62 adopted.

* 2014-Sep-07, 2014-Oct-17, 2014-Oct-26, 2014-Dec-06, 2015-Jan-09:
Several proposed changes to BIP62. See
https://github.com/bitcoin/bips/pulls?utf8=%E2%9C%93&q=is%3Apr+is%3Aclosed+bip62.

* 2015-Jan-10: OpenSSL releases versions 1.0.0p and 1.0.1k, with a fix
for CVE-2014-8275. The fix introduced a restriction on ECDSA signatures
to be strict DER, which would have solved all problems related to
signature encodings, except Bitcoin's consensus-critical nature
requires bug-for-bug compatibility between nodes. Worse, it seemed that
there was again a small (1%) number of blocks being created with
non-DER signatures in it, resulting in actual forks. The only immediate
solution that did not introduce more risk for forks was parsing and
re-encoding signatures using OpenSSL itself before verification to
bypass the restriction, making the problem persist. See
http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-January/007097.html.

* 2015-Jan-21: The new attention to signature encoding might have
revealed the vulnerability, and the presence of miners not enforcing
strict DER might have made the vulnerability actually exploitable.
BIP62 was still a moving target, so we wanted a faster means to solve
this. Therefore, a new BIP was proposed with just the strict DER
requirement, numbered BIP66. This would both allow non-OpenSSL
verification, and solve the vulnerability, without needing to fix the
less urgent malleability problem that BIP62 wanted to address. See
http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-January/007156.html.

* 2015-Feb-17: Bitcoin Core 0.10.0 was released, with support for
BIP66. See
http://lists.linuxfoundation.org/pipermail/bitcoin-dev/2015-February/007480.html.

* 2015-Jul-04: BIP66's 95% threshold was reached, enabling a consensus
rule for strict DER signatures in the blockchain. This solved the
vulnerability, and opens the door to using non-OpenSSL signature
verification in the near future.

- --
Pieter Wuille
Adam Back via bitcoin-dev
2015-07-29 13:46:46 UTC
Permalink
I believe the idea is to replace openSSL with
https://github.com/bitcoin/secp256k1 that Pieter and Greg spent quite
some time rigorously testing and have at this point better confidence
in than *SSL libraries.

I think the lessons learned from it as concluded by Pieter and Greg
are that openSSL and derivatives are not focussed on consensus
consistency, such that even if actively maintained and security
reviewed, their own bug fixes can break bitcoin.

Adam

On 29 July 2015 at 06:41, Mike Hearn via bitcoin-dev
This solved the vulnerability, and opens the door to using non-OpenSSL
signature verification in the near future.
Great work!
It also means the remaining usages of OpenSSL can be safely replaced with
something like LibreSSL or (perhaps better) BoringSSL.
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Mike Hearn via bitcoin-dev
2015-07-29 13:48:16 UTC
Permalink
Post by Adam Back via bitcoin-dev
I believe the idea is to replace openSSL with
https://github.com/bitcoin/secp256k1
Yes, I know. I said "other uses". For example RPC SSL and BIP 70.
Loading...