Counterfeiting via Merkle Tree Exploits within Virtual Currencies Employing the CryptoNote Protocol

Counterfeiting via Merkle Tree Exploits within Virtual Currencies Employing the CryptoNote Protocol

Free Download // Login or Register
Currency
Monero
Counterfeiting via Merkle Tree Exploits within Virtual Currencies Employing the CryptoNote Protocol
Monero Research Lab Papers
MRL-0002:

Abstract
On 4 September 2014, an unusual and novel attack was executed against the Monero cryptocurrency network. This attack partitioned the network into two distinct subsets which refused to accept the legitimacy of the other subset. This had myriad effects, not all of which are yet known. The attacker had a short window of time during which a sort of counterfeiting could occur, for example. This research bulletin describes deficiencies in the CryptoNote reference code allowing for this attack, describes the solution initially put forth by Rafal Freeman from Tigusoft.pl and subsequently by the CryptoNote team, describes the current fix in the Monero code base, and elaborates upon exactly what the offending block did to the network. This research bulletin has not undergone peer review, and reflects only the results of internal investigation.

Introduction
On 4 September 2014, a novel attack was executed against the Monero cryptocur- rency network, leading to a never-before-seen phenomenon in the network. The attacker must have had extensive knowledge of the Monero code, had good knowl- edge of Merkle Trees, and basic knowledge of cryptographic hash functions.

The Monero code was forked from the Bytecoin reference code in April 2014 before the CryptoNote reference code was released. The Bytecoin code appeared to be somewhat obfuscated and poorly commented, so any given segment of code must necessarily be considered with skepticism. Hence, any attacker with an extensive knowledge of the Monero code also, presumably, has an extensive knowledge of the Bytecoin and CryptoNote reference codes.

A Merkle Tree is a data structure in which every non-leaf node in the tree gains a label, and the label is the hash of the child nodes. That is to say, to build a Merkle Tree, we take some blocks of data (transactions), and we hash them. Then we hash those, two at a time. Then we hash those, two at a time. And we repeat this process until we are done. You can think of a Merkle Tree as a football bracket of cryptographic hashes. A natural question arises: what if we do not have a nice, even, power-of-two, divisible number of transactions? This is where the exploit came in, as we will see later.

CryptoNote currencies, and indeed, most cryptocurrencies, use Merkle Trees to construct the hash of a block of transactions (which is subsequently packed into the header of the block). The attacker noticed that a mis-implementation of a commonly used power-of-two rounding algorithm could be exploited while computing the hash of a block in order to generate two distinct blocks with the same hash. This should be all but impossible, of course, as collisions of cryptographic hash functions are rare. When discussing the rarity of these collisions, comparisons like “how many fundamental particles exist in the universe?” start to pop up, and usually those numbers are not big enough to describe collision rarity. In general, hash collisions typically imply mis-implementation rather than a failure of the hash functions, presuming we are using a good hash function.

To the authors’ best knowledge, this attack has only occurred once. Although Monero was the target, any coin utilizing CryptoNote reference code from before 4 September 2014 suffered the mis-implementations allowing for such exploitation, with two exceptions. Fantomcoin and Moneta Verde apparently fixed the relevant exploit in secret several months ago. Again, only to the authors’ best knowledge, all popular CryptoNote currencies have implemented the changes described by R. Freeman and the CryptoNote team, although we have not performed an extensive code review. The purpose of this document is to describe the section of code that allowed this attack and to elaborate on the attack’s effects.
Top