[bitcoin-dev] Vulnerability relating to 64-byte transactions in Bitcoin Core 0.13 branch

[Suhas Daftuar <sdaftuar@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 3764 bytes --]

Hi,

I'm writing to report a consensus vulnerability affecting Bitcoin Core
versions
0.13.0, 0.13.1, and 0.13.2.  These software versions reached end-of-life on
2018-08-01.

The issue surrounds a fundamental design flaw in Bitcoin's Merkle tree
construction.  Last year, the vulnerability (CVE-2017-12842) around 64-byte
transactions being used to trick light clients into thinking that a
transaction
was committed in a block was discussed on this mailing list
(
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-June/016091.html
).
There is a related attack resulting from the ambiguity around 64-byte
transactions which could be used to cause a vulnerable full-node
implementation
to fall out of consensus.

The attack on light clients discussed previously was centered on the idea of
claiming the Merkle tree has one more level in it than it actually has, to
prove that a candidate transaction is in the chain by having its hash match
one
side of a 64-byte transaction. The vulnerability I am describing here
involves
going the other direction: find a row of interior nodes in the Merkle tree
that successfully deserialize as transactions, in order to make a block
appear
to be invalid. (This is of a similar character to the attack described by
Sergio Demian Lerner on
https://bitslog.wordpress.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/
,
in the section titled "An (expensive) attack to partition Bitcoin".)

It has long been recognized that malleating a block's transactions in a way
that produces the same Merkle root could be used to cause a node to fall
out of
consensus, because of the logic in Bitcoin Core to cache the invalidity of
blocks (ie to avoid re-validation of known-invalid ones, which would
otherwise
make the software vulnerable to DoS). Malleation by "going up" the Merkle
tree,
and claiming that some interior row is in fact the set of (64-byte)
transactions in a block, could be used to cause the Bitcoin Core 0.13
branch to
incorrectly mark as invalid a block that in fact has a valid set of
transactions. Moreover, this requires very little work to accomplish -- less
than 22 bits of work in all.

I have attached a writeup that I put together for my own memory and notes
which
goes into more detail (along with a summary of other Merkle tree issues,
including the duplicate transactions issue from CVE-2012-2459 and the SPV
issue); please see sections 3.1 and 4.1 for a discussion.  The bug in 0.13
was
introduced as an unintended side-effect of a change I authored
(https://github.com/bitcoin/bitcoin/pull/7225).  Once I learned of this
category of Merkle malleation issues, I realized that the change
inadvertently
introduced a vulnerability to this issue that did not previously exist (in
any
prior version of the software, as far as I can tell).  A bug fix that
effectively reverted the change (
https://github.com/bitcoin/bitcoin/pull/9765)
was made just before the 0.14 version of Bitcoin Core was released, and no
later versions of the software are affected.

Also, I have scanned the blockchain looking for instances where the first
two
hashes in any row of the Merkle tree would deserialize validly as a 64-byte
transaction, and I have found zero such instances.  So in particular there
are
no blocks on Bitcoin's main chain (as of this writing) that could be used to
attack an 0.13 node.

I thought it best to withhold disclosure of this vulnerability before a
mitigation was in place for the related SPV-issue (which I assumed would
become
obvious with this disclosure); once that became public last summer and a
mitigation deployed (by making 64-byte transactions nonstandard), that
concern
was eliminated.

Thanks to Johnson Lau and Greg Maxwell for originally alerting me to this
issue.

[-- Attachment #1.2: Type: text/html, Size: 4838 bytes --]

[-- Attachment #2: BitcoinMerkle.pdf --]
[-- Type: application/pdf, Size: 200880 bytes --]