[Full Disclosure] CVE-2012-2459 (block merkle calculation exploit)

[deepceleron]

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

[molecular]

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.

[Luke-Jr]

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.

[Jouke]

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

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

[nibor]

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

[forrestv]

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.