Bitcoin Forum
February 19, 2019, 08:16:08 PM *
News: Latest Bitcoin Core release: 0.17.1 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1] 2 »  All
  Print  
Author Topic: [Full Disclosure] CVE-2012-2459 (block merkle calculation exploit)  (Read 10299 times)
forrestv
Hero Member
*****
Offline Offline

Activity: 516
Merit: 514


View Profile
August 22, 2012, 02:29:49 AM
Merited by AGD (1)
 #1

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

1J1zegkNSbwX4smvTdoHSanUfwvXFeuV23
Your Bitcoin transactions
The Ultimate Bitcoin mixer
made truly anonymous.
with an advanced technology.
Mix coins
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1550607368
Hero Member
*
Offline Offline

Posts: 1550607368

View Profile Personal Message (Offline)

Ignore
1550607368
Reply with quote  #2

1550607368
Report to moderator
1550607368
Hero Member
*
Offline Offline

Posts: 1550607368

View Profile Personal Message (Offline)

Ignore
1550607368
Reply with quote  #2

1550607368
Report to moderator
1550607368
Hero Member
*
Offline Offline

Posts: 1550607368

View Profile Personal Message (Offline)

Ignore
1550607368
Reply with quote  #2

1550607368
Report to moderator
galambo
Sr. Member
****
Offline Offline

Activity: 672
Merit: 252


View Profile
August 22, 2012, 02:40:22 AM
 #2

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

Activity: 1582
Merit: 1001


View Profile
August 22, 2012, 02:41:27 AM
 #3

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

  ▃▃▃▂▂▂▂▂▃▃▃▃                                      ▃▃▃▂▂▂▃▃▃                         
   ██████████████████                                        █████████████     ████                 
   ██████████████████                                        █████████████     ████                 
          ████                                               ████                                   
          ████   █████ █████ ████   █████    █████████       ████       ████   ████  ███████████   
          ████   ▀█████████▀ ████   ████    ████   ████      █████████  ████   ████   ████  █████   
          ████    ████▀ ▀▀▀  ████   ████   ████     ████     █████████  ████   ████   ████    ████ 
          ████    ████       ████   ████   █████████████     ████       ████   ████   ████    ████ 
          ████    ████       ███████████▄   ████             ████       ████   ████   ████   █████ 
          ████    ████       █████  ███████  ████  ████      █████      ████   ████   ███████████   
         ▄████▄   ████        ███     ███      ██████        █████      ████   ████   █████████     
                                                                                      ████         
                                                                                      ████         
                                                                             █▀▀   
Blockchain Fair Games
|
Truly one of a kind games:
MAGIC DICE   CHAIN'S CODE   PIRATE BAY
MINING FACTORY      RAPID TO THE MOON
|

400 BTC
★ PRIZE FUND ★
|

WEEKLY GIWEAWAYS
Join our community!
150% BONUS
First-time deposit
VISA  🔴🌕  50+coins

CERTIFIED RNG
100% TRANSPARENT
PROVABLY FAIR
Gavin Andresen
Legendary
*
Offline Offline

Activity: 1652
Merit: 1018


Chief Scientist


View Profile WWW
August 22, 2012, 02:42:21 AM
 #4

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.


How often do you get the chance to work on a potentially world-changing project?
Bitcoin Oz
Hero Member
*****
Offline Offline

Activity: 686
Merit: 500


Wat


View Profile WWW
August 22, 2012, 02:50:21 AM
 #5

Nice catch.

Luke-Jr
Legendary
*
Offline Offline

Activity: 2436
Merit: 1012



View Profile
August 22, 2012, 02:54:22 AM
 #6

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.

sadpandatech
Hero Member
*****
Offline Offline

Activity: 504
Merit: 500



View Profile
August 22, 2012, 02:57:12 AM
 #7

Very nice work, indeed!

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

If you're not excited by the idea of being an early adopter 'now', then you should come back in three or four years and either tell us "Told you it'd never work!" or join what should, by then, be a much more stable and easier-to-use system. - GA
It is being worked on by smart people. -DamienBlack
mrb
Legendary
*
Offline Offline

Activity: 1526
Merit: 1013


View Profile WWW
August 22, 2012, 05:38:25 AM
 #8

Very nice find, forrestv. Your security reviews keep impressing me.
BoardGameCoin
Sr. Member
****
Offline Offline

Activity: 283
Merit: 250



View Profile
August 22, 2012, 05:41:24 AM
 #9

having several different implementations of the Bitcoin protocol is a good idea.

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

I'm selling great Minion Games like The Manhattan Project, Kingdom of Solomon and Venture Forth at 4% off retail starting June 2012. PM me or go to my thread in the Marketplace if you're interested.

For Settlers/Dominion/Carcassone etc., I do email gift cards on Amazon for a 5% fee. PM if you're interested.
BitPay Business Solutions
Hero Member
*****
Offline Offline

Activity: 756
Merit: 500


View Profile WWW
August 22, 2012, 06:04:06 AM
 #10

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!

BitPay : The World Leader in Bitcoin Business Solutions

https://bitpay.com

Does your website accept bitcoins?
Mike Hearn
Legendary
*
Offline Offline

Activity: 1526
Merit: 1007


View Profile
August 22, 2012, 09:51:46 AM
 #11

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.
bg002h
Donator
Legendary
*
Offline Offline

Activity: 1428
Merit: 1005


I outlived my lifetime membership:)


View Profile WWW
August 22, 2012, 11:00:13 AM
 #12

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?

Hardforks aren't that hard.
1GCDzqmX2Cf513E8NeThNHxiYEivU1Chhe
makomk
Hero Member
*****
Offline Offline

Activity: 686
Merit: 500


View Profile
August 22, 2012, 12:53:17 PM
 #13

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

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

Quad XC6SLX150 Board: 860 MHash/s or so.
SIGS ABOUT BUTTERFLY LABS ARE PAID ADS
molecular
Donator
Legendary
*
Offline Offline

Activity: 2632
Merit: 1008



View Profile
August 22, 2012, 01:01:44 PM
 #14

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?

PGP key molecular F9B70769 fingerprint 9CDD C0D3 20F8 279F 6BE0  3F39 FC49 2362 F9B7 0769
Sergio_Demian_Lerner
Hero Member
*****
Offline Offline

Activity: 540
Merit: 512


View Profile WWW
August 22, 2012, 01:09:02 PM
 #15

Great work Forrest and the dev team!
Best regards, Sergio.
Nefario
Hero Member
*****
Offline Offline

Activity: 602
Merit: 502


GLBSE Support support@glbse.com


View Profile WWW
August 22, 2012, 01:13:02 PM
 #16

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?

PGP key id at pgp.mit.edu 0xA68F4B7C

To get help and support for GLBSE please email support@glbse.com
Pieter Wuille
Legendary
*
Offline Offline

Activity: 1050
Merit: 1006


View Profile WWW
August 22, 2012, 02:00:10 PM
 #17

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.

aka sipa, core dev team

Tips and donations: 1KwDYMJMS4xq3ZEWYfdBRwYG2fHwhZsipa
Piper67
Legendary
*
Offline Offline

Activity: 1106
Merit: 1001



View Profile
August 22, 2012, 02:09:54 PM
 #18

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.
capsqrl
Sr. Member
****
Offline Offline

Activity: 450
Merit: 250



View Profile
August 22, 2012, 04:50:28 PM
 #19

here here!
You mean "hair hair".

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

Norsk Bitcoin-bruker? Kom til /r/BitcoinNO på reddit!
keystroke
Hero Member
*****
Offline Offline

Activity: 875
Merit: 1005


advocate of a cryptographic attack on the globe


View Profile
August 22, 2012, 06:21:09 PM
 #20

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 Cheesy

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

"The difference between a castle and a prison is only a question of who holds the keys."
Pages: [1] 2 »  All
  Print  
 
Jump to:  

Bitcointalk.org is not available or authorized for sale. Do not believe any fake listings.
Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!