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.
Topic: [Full Disclosure] CVE-2012-2459 (block merkle calculation exploit) - page 2. (Read 10529 times)
August 21, 2012, 09:54:22 PM
August 21, 2012, 09:50:21 PM
Nice catch.
August 21, 2012, 09:42:21 PM
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.
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.
August 21, 2012, 09:41:27 PM
Nice find.
About the only serious bug i ever found was in sudo for local root on linux.
About the only serious bug i ever found was in sudo for local root on linux.
August 21, 2012, 09:40:22 PM
Nice find. Does this have any additional consequences other than the potential denial of service? I guess not based on your description.
August 21, 2012, 09:29:49 PM
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
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
Jump to: