Bitcoin Forum

Since at least 80% of the Bitcoin network is now protected against this attack, I've been given permission to disclose it:


The Merkle hash implementation that Bitcoin uses to calculate the Merkle root in a block header is flawed in that one can easily construct multiple lists of hashes that map to the same Merkle root. For example, merkle_hash([a, b, c]) and merkle_hash([a, b, c, c]) yield the same result. This is because, at every iteration, the Merkle hash function pads its intermediate list of hashes with the last hash if the list is of odd length, in order to make it of even length.

And so, the Merkle root function can be effectively preimaged by changing the input so that one of the intermediate lists is of even length with the last two elements equal (where originally it was of odd length with a last element equal to the earlier mentioned two). As was later noted, this extends to any input length that is not a power of two: merkle_hash([a, b, c, d, e, f]) == merkle_hash([a, b, c, d, e, f, e, f]). Note that to maintain the same root hash, the only flexibility that exists is duplication of elements.

As a result, two blocks can easily be created that have the same block hash, though one can be valid and the other invalid, by duplicating one or more of the transactions in a way that maintains the Merkle root hash. Duplicating any transaction will make the block invalid, since the block double spends a certain past transaction output.

An unpatched Bitcoin installation can be permanently wedged at its current highest block using this and the fact that Bitcoin caches orphan blocks in a disk-backed database. To do so, the attacker must send it a valid block (that will eventually make it into the blockchain) made invalid by duplicating one of the transactions in a way that preserves the Merkle root. The attacker doesn't even need to mine their own block - instead, they can listen for a block, then mutate it in this way, and pass it on to their peers.

Once the victim receives this invalid block, they will cache it on disk, attempt to process it, and reject it as invalid. Re-requesting
the block will not be even attempted since Bitcoin believes that it already has the block, since it has one with the same hash. Bitcoin eventually displays the "WARNING: Displayed transactions may not be correct!  You may need to upgrade, or other nodes may need to upgrade." warning when the blockchain extends further beyond the received invalid block.

The problem was fixed by Gavin Andresen in Bitcoin commit be8651d [1] by rejecting blocks with duplicate transactions in CheckBlock, preventing them from being cached at all.


Cheers,
Forrest Voight
http://forre.st/

[1]: https://github.com/bitcoin/bitcoin/commit/be8651dde7b59e50e8c443da71c706667803d06d

Nice find. Does this have any additional consequences other than the potential denial of service? I guess not based on your description.

Nice find.
About the only serious bug i ever found was in sudo for local root on linux.

Zooko Wilcox-O'Hearn also deserves recognition; he warned us that the method Bitcoin uses to compute the Merkle tree was possibly insecure (although at the time we couldn't see how to turn it into an exploit).

This was a nasty bug; if Forrest hadn't found it and responsibly reported it, an attacker probably could have stopped most of the nodes on the network before we got patched code out. It is bugs like this that make me think that having several different implementations of the Bitcoin protocol is a good idea.

Nice catch.

From the mining perspective, the unpatched install might not be simply wedged: it will also follow a competing smaller blockchain. An attacker could have used this exploit against a number of large miners (say about 40% or so) and exchanges to pull off any number of double-spend attacks until the miners noticed they had been forked and fixed their bitcoind. That is, the attacker could easily hijack as much of the miners has he wanted for his own purposes including phony 6+ confirmation transactions. On a more subtle level, the attacker could target certain blocks they wanted orphans by performing this attack on a majority of miners with the "tip" block he wanted orphaned.

This vulnerability is also the reason why Eloipool (the software behind Eligius, EclipseMC, TripleMining, and other pools) has attempted to produce blocks with only transaction counts that are powers of two; such blocks cannot be used for an attack even against vulnerable clients.

Very nice work, indeed!

wow, Luke-jr this thing sounds highly nasty. Again, bravo to the dev team for their diligent work!

Very nice find, forrestv. Your security reviews keep impressing me.

here here! Sweet bug and nice work fixing it guys.

It is exactly this kind of teamwork and honest effort that makes us so confident in the future of Bitcoin.  Keep up the great work!

Unfortunately independent implementations might not help here. At least in bitcoinj, it's using exactly the same code to calculate the merkle root. I might go back and try to simplify it at some point.

Do we know this wasn't independently discovered by some more malintentioned person? From what I gather from the OP, it was never a silent bug (at least on the client side), right?

The only real benefit of independent implementations here is that it means more people have actually looked at and understood the way Bitcoin works. For instance, if you think about it forrestv had to look at the details of the merkle root calculation in order to implement p2pool. (For that matter, I'm the only person who even admitted to having worked out the vulnerability from the patch for it, and that was largely a due to having developed code for poolserver work generation before.)

I think a clever attacker could've carried out an attack that wasn't any more noisy than double-spending through rewriting history using any other method.

I've seen that "WARNING" message a couple weeks ago in my client. After redownloading the blockchain (maybe multiple times), it vanished.

Thanks Zooko for finding/reporting and thanks to all devs, not only for handling this very well, but also for all your other work!

Regarding implementation monoculture: How varied should the landscape be? Is it a good goal to try to have no single implementation be responsible for more than half the hashing resources?

Great work Forrest and the dev team!
Best regards, Sergio.

Does this mean that an attacker could trick a bitcoin client into thinking that two deposits of say 100BTC were made(thinking that 200BTc were deposited to an address), only to have one of them invalidated and removed some time later?

Right now, it only means an attacker can make your (unpatched) node get stuck.

Back when only a low percentage of clients had upgraded, it might have been used to assist with a 51% attack, by knocking out some legitimate mining power.

Heh... it's not just bitcoin that is decentralised. The brains behind it are decentralised as well. That's what's so cool about it.

You mean "hair hair".

Impressive find, and as always, Zooko had something to do with it :-)

Excellent work everyone! Now that people are upgrading, is there is a system in place to detect if someone tries this attack on the network? In other words, even though many old attacks won't work, do devs/testers actively scan the network to detect bogus packets which attempt to implement these exploits. Sort of having a Bitcoin IDS :D

For example, perhaps an advanced version of something like this: http://blockchain.info/strange-transactions

I do wonder if there was an attacker in the wild trying this, there are various stalled out Bitcoin reports in different threads where new users getting the blockchain had to wipe the datadir and start again....

I checked github and this issue was worked around (fixed) 4 month ago: https://github.com/bitcoin/bitcoin/commit/be8651dde7b59e50e8c443da71c706667803d06d

The corresponding issue https://github.com/bitcoin/bitcoin/issues/1167 doesn't mention the merkle root calculation vulnerability, probably on purpose.

It's hard to imagine someone stumbling upon this issue or this fix and suspecting and finding the problem with the merkle root calculation.

The info might have slipped out some other way (maybe it was even pretty common knowledge amongst the devs) or maybe someone found this on his own seperately.

I still think it's likely (gut feeling) that the problems people reported were actually caused by someone trying to exploit this (I also had these troubles). On the other hand, there's probably many other possible explanations.

A lot of stuck nodes were investigated over the last year, and as far as  I know they all turned out to be harddisk corruption.

I'm aware of at least two people who were trying to figure it out on their own (with no information); one managed to suspect something to do with the merkle tree calculation (after giving up and resuming a number of times), but that was the closest he got before it was disclosed.

Cool, thanks for finding and acting on it, in the right way :)

forestv - how did you find this? Was it by accident or inspired?

First, some background:
P2Pool could theoretically use the normal merged mining standard to store the reference to its own data in the coinbase. However, the standard is flawed in several ways and requires that you have the entire coinbase transaction to validate it. P2Pool uses something similar of my invention - it stores a merkle root at the end of the coinbase transaction by integrating it into a fake txout. Then, you can prove that the merkle root is in the coinbase transaction using only O(1) data by sending the SHA256 midstate of all the data preceding the merkle root. I'd like to write up a specification for this at some point, because I believe that O(1) MM proofs are pretty useful.

I was thinking about the consequences of someone including multiple different merged mining references (something that is prevented in the original MM implementation by the chain id stuff) under one root when I realized that the merkle root function Bitcoin uses isn't nearly one-to-one. From there, I noticed that you could duplicate transactions while maintaining the block hash, wondered how Bitcoin would react to that, and remembered that Bitcoin stores unvalidated orphan blocks...

Here's the original proof of concept code, untouched since April 29/30: http://u.forre.st/u/gkwobmns/poc.zip You have to run the programs using "trial" - they were P2Pool testcases that I grabbed and reused.