Topic: [Full Disclosure] CVE-2012-2459 (block merkle calculation exploit) (Read 10529 times)

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.

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

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

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.

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.

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....

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

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

You mean "hair hair".

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

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.

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.

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?

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

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?

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.

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?

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.

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!

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

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

Very nice work, indeed!

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