Monero network exploit post-mortem

General discussion of CryptoNote based currencies and issues.

Monero network exploit post-mortem

Postby Werner_Albert » Mon Sep 08, 2014 11:41 pm

CryptoNote and the CryptoNote community invest a lot of time and energy to create reliable, innovative, and user-friendly, state-of-the-art code. Unfortunately, attempts to discredit or attack innovative technologies are inevitable.


Summary

One of the CryptoNote-based coins, Monero, has been affected by malicious activity on September 4th 2014 in which the Merkle root calculation vulnerability was successfully exploited. Even though the corrupt block that has led to the network split was found on height 202612, it required certain targeted measures prior to and after its creation for the exploit to be successful. Details of the damage caused to the Monero network by the attacker’s actions and the Merkle root calculation overview are provided below.

CryptoNote code had a flaw in the Merkle root calculation, which was used to compute the block hash from the hashes of the transactions contained within it. In certain situations the transactions inside the block may be substituted without the block hash being affected. In this particular case if there are exactly 513 transactions in the block (excluding the coinbase transaction), the 512th and 513th transactions can be replaced with no consequences to block hash.

The attacker has created two blocks with exactly the same 513 transactions except for the last 2, which were different for the blocks. Due to the flaw in the Merkle root calculation, these two blocks had the same hashes. Each of the two blocks have been relayed across various Monero network nodes, dividing them into two sub-networks.


Pre-requisite

The attacker had to create the block containing 513 transactions. Normally, the Monero network block size does not exceed 25,400 bytes, since the daemons are creating blocks within 1.3 medians of the last 100 blocks. The block size median was originally roughly equal to 20,000 bytes. This corresponds to a normal block containing less than 10 typical transactions. Even though CryptoNote has adaptive limits imposed on the block median size allowing it to be shifted, the attacker could not easily move the median to include 513 ordinary transactions as it would require the median size to be substantially larger than 20,000 bytes.

Therefore, certain actions had to be performed for the Monero network to accept and relay the 513-transaction blocks. The pre-requisites are:

1. First 511 transactions should be of the smallest possible size. The attacker has created special transactions for this particular purpose that had only 1 input, no outputs, and an empty extra field. Each of these transactions is roughly 105-106 bytes, which is likely the smallest possible transaction size.

2. The 512th and 513th transactions of both corrupt blocks should be normal for either of them to be included into one the sub-network’s blockchains, or these transactions are spent on different sub-networks.

3. The median block size should be increased for the corrupt block to be accepted by the network. The 202612 block size is 55503 bytes, which means that the median has been lifted from 20,000 bytes to at least 55,503 / 2 = 27,752 bytes.


Details

Part 1. Attack preparation
2014-08-31

The malicious activity had likely started on 2014-08-31. The attacker had created 2574 outputs equal to 0.000000000001 XMR (1 atomic unit). This had been done to generate enough inputs for the 511 small transactions of the corrupt block. Note that 2574 outputs is enough for 5 of such blocks, which implies that the attack might have been plotted to be broader than its actual reach.
Here is the last transaction with such small output: http://chainradar.com/xmr/transaction/34c75f71fd8999fac02cd13a29439cf1e58dbf8ab1b7e4f272fbff3aac5696b0


Part 2. Median shifted with the transaction flood
2014-09-03, 08:47:20 UTC (block 201481)

At height 201481 the blocks containing 1 and more transactions started to emerge on the network. The attacker had likely started the transaction flood in order to gradually shift the median size from 20,000 bytes to 27,752 bytes.


Part 3. Finding the corrupt block
2014-09-03, 17:16:19 UTC (block 202023)

The median has exceeded 27,752 bytes starting with the block height 202023 and continued to increase further. Apparently, this was the time when the corrupt block with 513 transactions started to be mined.

2014-09-04, 04:22:50 UTC (block 202612)
The mining had taken approximately 11 hours until the corrupt block was found on height 202612. After the block had been mined, the transaction flood stopped around the block 202646 (when the block median size started to decrease). Thus, the transaction flood took place between 2014-09-03, 08:47:20 UTC and 2014-09-04, 04:52:05 UTC, lasting roughly 20 hours.

According to our analysis, during this period 4037 transactions with an overall fee of 344.174025917752 XMR have been created. The total size of these transactions was 35,756,751 bytes (31.1 MB). However, the transaction flood had been well orchestrated to look indistinguishable from the normal network transactions. Thus, this is the upper estimate of the malicious activity and the costs of the transaction flood.


Part 4. Relaying the blocks

The corrupt 202612 block had been relayed to one part of the network (sub-network A). Its exact copy with the 512th and 513th transactions replaced had been relayed to the second part of the network (sub-network B). Due to the Merkle root calculation flaw, both of these blocks had exactly the same hash.

This does not imply a split, at least until the 512th and 513th transactions of one of the sub-networks are accepted by the other sub-network as valid transactions.

The block 202612 on sub-network A had the following 2 last transactions:
d2d714c86291781bb86df24404754df7d9811025f659c34d3c67af3634b79da6
d59297784bfea414885d710918c1b91bce0568550cd1538311dd3f2c71edf570

The block 202612 on sub-network B had the following 2 last transactions:
2a58f802202db09cbd1377630ae73becff1eaff52e8969980672496dc39a5f6f
57ce3aab446d75726221c908a4bf6ac2f67485cab80a2e2bedfe5519cabd8848

(Note that certain URLs above might become unavailable when all block explorers migrate to the correct chain)


Part 5. Split starts
2014-09-04, 04:25:05 UTC (block 202614)

The attacker had likely sent the transactions of the block 202612-B to mining pools on the sub-network A. These transactions had been included in the blockchain on height 202614 by one of the pools.

The sub-network A daemons accepted that block since they didn't have the 2a58f802202db09cbd1377630ae73becff1eaff52e8969980672496dc39a5f6f and 57ce3aab446d75726221c908a4bf6ac2f67485cab80a2e2bedfe5519cabd8848 transactions on the blockchain.

The sub-network B deamons rejected the block since those transactions had already been included in block 202612-B. Accepting these transactions a second time would imply double-spending.

Therefore, the network had been split on height 202614 when the two sub-networks turned into two different chains. Fortunately, the large majority of the Monero network had remained on the chain A, which helped to avoid larger negative consequences for the currency.


Part 6. Second attempt to perform the split

As discussed above, there are 2 possibilities for the split to emerge. Apart from the case explained in part 5, the split could have been started if the outputs of the 512th and 513th transactions were spent on each of the sub-networks.

We have checked whether such actions took place by analyzing the blockchains of the 2 sub-networks. Indeed, we’ve identified that the attacker tried to spend the outputs of the corrupt transactions.

Here are these transactions:
Tx 8167e70172da333859220771838c0c338de15c8a4ca9fbd6ba779e579b19eb22 spends all the outputs of tx d2d714c86291781bb86df24404754df7d9811025f659c34d3c67af3634b79da6 of the block 202612-A.
Tx 2cad16a7734c0084e5590fb264be1879c82d590d139d789876444920a0079dd6 spends all the outputs of tx d59297784bfea414885d710918c1b91bce0568550cd1538311dd3f2c71edf570 of the block 202612-A.
Tx f7a2c4d0c4ccbfae37d550253c5f032156d9e8d0897d76137e26ea5fa8a92f44 spends all the outputs of tx 2a58f802202db09cbd1377630ae73becff1eaff52e8969980672496dc39a5f6f of the block 202612-B.
Tx e3b94625d8eb5513dbc98b599a86a3b8622a23dce0124334f5b9982b656c59c5 spends all the outputs of tx 57ce3aab446d75726221c908a4bf6ac2f67485cab80a2e2bedfe5519cabd8848 of the block 202612-B.

We are unsure why the attacker had pursued both ways to split the network. It might have been done to ensure that the split actually started. Nevertheless, even if the split would not have started at block 202614 the way it has, it could have still be caused by spending the transaction outputs at a later time.


Timeline

The timing is derived from the timestamps of the corresponding blocks.

2014-08-31 — the transactions with 1 atomic unit outputs are created for the corresponding 511 small transactions of the corrupt block
2014-09-03, 08:47:20 UTC — transaction flooding begins in an attempt to increase the median block size
2014-09-03, 17:16:19 UTC — the median is exceeded and reaches the size required for the split
2014-09-04, 04:22:50 UTC — the corrupt block is found, duplicated, and relayed across the network dividing Monero network into two sub-networks
2014-09-04, 04:25:05 UTC — the transactions of the 202612-B block has been included into the sub-network’s A blockchain and the split starts


The fix

In order to patch the vulnerability and fix the split, the following steps are required:

1. Apply the official CryptoC-3 patch for the Merkle root calculation algorithm vulnerability.
2. Hardcode the block height and the block hash for the software to know which sub-network is the “right” one.
3. Hardcode the transaction hashes of the “right” block.
4. Adjust the daemon so it checks at startup whether it is on the correct chain. If it’s not, the daemon should prune the incorrect part of the blockchain.

This would protect the network from the future exploits and explicitly state which of the two chains is correct.


Conclusion

The vector of the network split had likely been the financial gains. The attacker had spent a significant amount of time and funds to research the vulnerability and organize the series of activities that had led to the network split. Theoretically, the attacker could have divided the exchanges across sub-networks to trade the coins for Bitcoins on both sub-networks by applying a double-spending attacks. Fortunately, the community had responded quickly by freezing the trades on all the major exchanges, which helped avoid financial losses.

In this document we have investigated the root causes and identified an imperfection in the CryptoNote code base that has led to the Monero network split. As soon as an official patch was made available CryptoNote communicated it to all the CryptoNote-based coins. All CryptoNote-based coins are urged to apply this pre-emptive patch to protect them against this condition. CryptoNote’s team and community are committed to the technology and are continuing to contribute to the development of CryptoNote based coins.

Albert Werner,
Core Developer
CryptoNote Team
Werner_Albert
 
Posts: 56
Joined: Wed Mar 26, 2014 3:23 pm

Re: Monero network exploit post-mortem

Postby johannes.meier » Tue Sep 09, 2014 12:03 am

The hash tree explained

The following text explains the Merkle root calculation algorithm and the vulnerability that was exploited. CryptoNote organizes transactions within a block into a hash tree. The single tree root is a proof of the transactions’ integrity: it is almost impossible to alter any of the transactions (or alter the whole set) and keep the root hash intact.

Image

Since every tree node has exact two children it is relatively easy to construct a tree of 2^N transactions. However if the number of transactions is not a single-base exponential function, a more complicated scheme is required. For instance, the Bitcoin algorithm simply doubles some hash values, “imitating” the missed transaction.

Image

It is not the best solution possible since doubling the inner hash results in a “ghost hash”. The resulting root hash may be the same even if the hash was not doubled, but created from some child node(s). Thus, different transactions sets might produce the same root hash, which is unacceptable. This particular situation is very rare, but should nevertheless be avoided to eliminate a potential attack vector. For this particular reason CryptoNote utilizes a different tree construction scheme.

Image

The CryptoNote algorithm does not double the values, but constructs an asymmetrical (in common sense) tree. Every transaction hash becomes a tree leaf on the last or the next to the last levels. No more than one “incomplete” level is created, and each distinct transaction set produces unique root hashes. Each node can be described in a few lines of code. Let’s say there are “n” transaction and therefore 2*n-1 nodes. Every hash is computed as follows:

Code: Select all
h[i] = hash( h[2 * i + 1], h[2 * i + 2] ), if i <= n – 2 (an inner node)
h[i] = hash( tx[i - n + 1] ), if n - 1 <= i (a leaf)


The first step is to determine how many nodes should be on the last complete level. The maximum number of nodes per-level is 2^N, hence an incomplete level will have less than 2^N transactions. On the picture above the last complete level has 4 nodes.

The hash of the nodes with no children is the hash of the transaction itself. The hash of nodes with children is derived from its children (transactions). The rest of the tree can be computed as usual.

The vulnerability was not in the algorithm itself, but in its first step. When searching for the position of the high-order bit of N, a single conversion from bytes to bits was missed, more specifically, the multiplication by 8 (or “x8”) was missed. This led to an insufficient amount of bitwise operations and a wrong result when N > 512. For a smaller number of transactions the algorithm worked properly. Moreover, the bug described in this document can appear only if N=514 (or 1026-1028, or 2050-2056, etc.)

The incorrect result from the first step led to an incorrect memory allocation and the computation of the last two inner hashes did not take into account the last four transactions (transaction 3-6 as on the picture 3). As a result, the last two transactions’ hashes were not included in the calculation set, prior to computing the remaining nodes. The algorithm worked as if there were only 512 (or 1024 or 2048 etc) hashes, and computed a full tree with 2^N leaves.

Image

A root hash was computed without the last two transaction. This means that these two transactions could be altered or replaced without affecting the root. Therefore, several blocks could be created with the same hash but different sets of transactions. Upon restoring the missed “x8” multiplication every possible number of transactions will be processed as originally designed.
johannes.meier
 
Posts: 5
Joined: Wed Mar 26, 2014 3:08 pm

Re: Monero network exploit post-mortem

Postby ochtend » Wed Sep 10, 2014 1:18 pm

In the first post your wrote about tx #512 and 513
So as Monero dev https://bitcointalk.org/index.php?topic ... msg8677607
But the second post (on tree explanation) says 514 txs.
I'm confused
ochtend
 
Posts: 3
Joined: Fri Mar 28, 2014 9:49 am

Re: Monero network exploit post-mortem

Postby Werner_Albert » Wed Sep 10, 2014 2:33 pm

The tree-hash scheme includes so called coinbase transaction. It comes with a block and contains a reward for the miner. From the tree-hash algorithm stand point it is an ordinary transaction; it does not differ from the others on the hash tree.
But when we talk about the attack, we mention only specific transactions: 511 of the doctored ones (with small inputs) and two transactions, which were the cause of the fork (512 and 513). Add the coinbase one and you will get 511+2+1=514

We hope that answers your question.
Werner_Albert
 
Posts: 56
Joined: Wed Mar 26, 2014 3:23 pm


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 1 guest