Topic: The trasaction fetch memory exhaustion attack (TFMEA) - page 2. (Read 4012 times)

The trasaction fetch memory exhaustion attack (TFMEA)

I'm publishing this attack since:

1. It's not truly practical (only if it's government-sponsored)
2. I'm unsure if it can be really done, since I haven't tested it.
3. The network can recover by simply installing a new version that offers some kind of protection.


Overview

Suppose most Bitcoin clients are installed in Windows operating systems. Suppose most people that use Windows does not compile the source code,
but download the 32 bit executable from Sourceforge, which is a 32-bit application. This assumptions seems probable in practice.

To process a transaction the Satoshi client loads all referred transactions inputs into RAM (see CTransaction::FetchInputs()).

The Attack

The attacker mines 2000 blocks. Each one containing a 1 Mbyte transaction.
Then the attacker can construct a transaction that requires 2 Gb of RAM to be processed, be linking to each one of 2000 big transactions.
All Windows clients processing this transaction will segfault. Nodes must update to recover.

How long it takes?

The fastest the attack can be made is by mining 2000 blocks as fast as possible. 2000 blocks in 10 minute intervals represents 14 days.
Because difficulty is re-computer every 2016 blocks, the attacker can also increase the total hashing power to reduce the block interval.

How much it cost to attack?

Current Bitcoin hashing power is 20000 GHash/s.
Take the Bitforce Single 'SC', which makes 60 GH/s for 1300 USD. Then 50% of the hashing power can be bought for
20000/60*1300 = 433K USD.

With 50% of the hashing power, the first 2000 blocks will contain half of the attacker's blocks, and will be mined at 2x speed.
That's 7 days. The remaining 2000 blocks (containing the other half) will be mined at a normal 1x speed.
The total atack time is therefore 21 days.

If the attacker is willing to invest more?

Investing four times that amount, or 1.7M USD, the attacker gets 80% of the hashing power.
The first 2000 blocks will contain 80% of the attackers blocks, mined in only 2.8 days.
The remaining 400 attacker blocks will take an additional 3 days.
The total atack time is therefore 5.8 days.

What if the attacker is a miner who already has 10% of the network hashing power?

We suppose the miner has already amortized his mining hardware.
We suppose than mining fees are very low compared to the 25 BTC block reward.
If we suppose that mining is profitable, then mining each block costs, on average, less than 25 BTC.
Then the attack has no cost, and it takes 140 days to store 2000 1Mb transactions in the blockchain.

Proposed Solutions

1. Limit the number of transaction bytes that a transaction can request (TxSizeRequested(Tx)<1 Mb).
 TxSizeRequested() can be computed as  
   TxSizeRequested(Tx) = Sum( for each distinct tx2 in tx.previns: Size(Tx2.Size) )
   
(this is a hard fork, but is likely that there is a  transaction in the current block-chain whose TxSizeRequested(Tx)>10 Kbytes)

OR    

2. Free older transactions while fetching new transactions in as in a sliding window, in FetchInputs().
   Reload transactions in ConnectInputs(), and dispose after verifying script.

Comments welcomed!

Edit: Piuk has discovered a worse problem: the attack could be executed during a blockchain download, where the difficulty is lower. not tested, yet.