New DoS vuln by Forcing Continuous Hard Disk Seek/Read Activity (fixed in 0.8.0)

New DoS vuln by Forcing Continuous Hard Disk Seek/Read Activity (fixed in 0.8.0)

Private Release Date: 08-JAN-2013
Public Release Date: 14-FEB-2013

Systems Affected

- Satoshi Bitcoin Client (Bitcoin-Qt, bitcoind)
- All Bitcoin clients that mimic the behavior related to transaction validation of Satoshi client versions prior 0.8.0

Affected Versions

- Bitcoin version 0.7.2 released 2012-12-14
- Bitcoin version 0.7.1 released 2012-10-19
- Bitcoin version 0.7.0 released 2012-09-17
- Bitcoin version 0.6.3 released 2012-06-25
- Bitcoin version 0.6.2 released 2012-05-08
- Bitcoin version 0.6.1 released 2012-05-04
- Bitcoin version 0.6.0 released 2012-03-30
- Bitcoin version 0.5.3.1 released 2012-03-16
- Bitcoin version 0.5.3 released 2012-03-14
- Bitcoin version 0.5.2 released 2012-01-09
- Bitcoin version 0.5.1 released 2011-12-15
- Bitcoin version 0.5.0 released 2011-11-21
- Bitcoin version 0.4.0 released 2011-09-23
- Bitcoin version 0.3.24 released 2011-07-08
- Bitcoin version 0.3.23 released 2011-06-14
- Bitcoin version 0.3.22 released 2011-06-05
- Bitcoin version 0.3.21 released 2011-04-27

Overview

Transaction processing has two stages in Satoshi Bitcoin client. In the first stage, transaction inputs are fetched.
This is done by bringing to RAM the transactions that contains the outputs referred by the inputs.
In the second stage, previous outputs are verified to be unspent and the related scripts are evaluated.
Since double spends are not considered to be a DoS attempt by the protocol rules, a transaction that refers to previous spent outputs will pass the first processing stage without being discarded. An attacker can therefore construct transactions that, before being discarded in the second stage of processing, require the victim application to seek and read too many parts of the block chain that could be scattered thought the storage files, delaying any other processing.

Details

We assume that the whole block chain does not fit in RAM, so each transaction fetch requires a HD seek and read. An average 7200 rpm hard drive
can random seek/read a 1Kb block in a non-cached 2 Gb file in 12 msec. Each prevout of a transaction consumes 44 bytes, with empty sigscripts.
The attacker creates transaction with many inputs an one output. In this way, the other sections of the transaction (output scripts, headers) are amortized and become irrelevant to this analysis.
For an Internet connection of 50 Kbytes/sec bandwidth, sending 45 bytes requires less than 1 msec.
By continuously sending this specially crafted transactions an attacker can block any Bitcoin peer from performing other tasks.
Also the attacker may be able to block 10 peers at the same time, since the relation of 1:10 in required resources.
Note that the attacker does not need to sign the inputs nor to have the full block-chain to perform the attack. He only requires the hashes of all previous transactions, which currently requires only 10876856*32=332 Mbytes of storage.

Version 0.8.0 of the Satoshi client stores only unspent prevouts in memory and can abort processing right after a spent prevout is referred by a transaction.

Possible Attack Scenarios

1. Because of the small resources required to mount the attack, it could be performed by botnets to massively attack the Bitcoin network.

2. The attack can be used against miners to prevent them from sending blocks. Nevertheless, currently big miners are ony connected to there own front-line of Bitcoin nodes to preven such attacks.

3. By using many nodes at once, an attacker may try to create a barrier that splits the network in unconnected components, in order to carry another kind of attack.

Not-a-problem variations

1. A valid 1M transaction could be constructed to reference more than 22K unique input transactions. In theory that transaction would take more than 5 minutes to be verified. Nevertheless the attack is unpractical for two reasons:
a. The attacker should have to own those 22K transactions.
b. Those 22K transactions should have to be scatterer thought the blockchain to force HD seeking activity. If they were created in a limited period of time, they would end up confined in a limited portion of the block chain file. The result would be that the hard disk cache will help to reduce the read latency and so attack effectiveness will be reduced. Nevertheless version 0.8.0 of the Satoshi client considers transactions greater that 100K to be non-standard, so the vulnerability is further reduced.

Suggested Solution for 0.6/0.7 versions

The client application could verify that prevouts are not spent each time they are fetched, and abort if a spent prevout is found.

bool CTransaction::FetchInputs(CTxDB& txdb, const map<uint256, CTxIndex>& mapTestPool,
   bool fBlock, bool fMiner, MapPrevTx& inputsRet, bool& fInvalid)
{
  ..
for (unsigned int i = 0; i < vin.size(); i++)
   {
   // Read txPrev
   CTransaction& txPrev = inputsRet[prevout.hash].second;
   ....
   // NEW CODE BEGINS
   if (prevout.n >= txPrev.vout.size() || prevout.n >= txindex.vSpent.size())
   {
   fInvalid = true;
   return DoS(100, error(" .....
   }
   if (!txindex.vSpent[prevout.n].IsNull())
   return false;
   // NEW CODE ENDS
   }
}

Disclosure Timeline

2013-01-09 - Vulnerability reported to Gavin Andressen and other core devs.
2013-01-09 - Gavin Andressen aknowledges report and confirms version 0.8 will not be vulnerable, permits disclosure after 0.8.0 release candidate 1 is available.
2013-02-09 - Bitcoin version 0.8.0 release candidate 1 is available, fixing the vulnerability
2013-02-14 - Vulnerability disclosure

Credit

This vulnerability was discovered by Sergio Demian Lerner, from Certimix.com
This report was written by SDL.
Disclaimer: I haven't tested the attack with exploit code, but it seems to be real and practical.