View source for CVE-2012-3789

== Multiple DoS Vulnerabilties in Satoshi Bitcoin client ==

Private Release Date: 12-MAY-2012<br />
Public Release Date: 08-JAN-2013<br />

=== Systems Affected ===
----------------

- Satoshi Bitcoin Client (Bitcoin-Qt, bitcoind)<br />
- All Bitcoin clients that mimic Satoshi client behaviour related to orphan transactions<br />

=== Affected Versions ===
-----------------

- Bitcoin version 0.5.3, released 14 March 2012<br />
- Bitcoin version 0.5.3.1 released 16 March 2012<br />
- Bitcoin version 0.6.0 released 30 March 2012<br />
- Bitcoin version 0.6.1 released 4 May 2012<br />
- Bitcoin version 0.6.2 released 8 May 2012<br />

=== Overview ===
--------

This report contains information regarding two new vulnerabilities discovered in May-2012. The more severe one allows a 
connected peer to hang the victim's client application in less than 20 minutes by sending a stream of specially 
crafted transactions, as a denial-of-service attack.

=== Background ===
----------

Each peer defines a transaction as "Orphan" if the transaction references a parent transaction (previous output) which is
neither part of a block in the current best chain, nor it is  in the in-memory transaction pool.
Before version 0.5.3 of Satoshi Bitcoin client, orphan transactions were stored in a temporary table in memory until the parent transactions could be located in a block or the parent transaction was forwarded by a peer.
The storage for ophan transaction was unlimited. This feature allowed an attacker to perform a DoS attack by sending transactions continuously until the victim's virtual memory was filled and the victim's operating system began trashing. This situation probably leads to the victim's computer or application to hang. 
The time needed for this DoS attack varies depending on the link bandwidth between the attacker and the victim, and the victim's RAM size. For an average computer and Internet connection it takes approximately 12 hours.

The vulnerability was discovered by Sergio Demian Lerner and communicated to the Bitcoin.org development team, who developed and applied a patch (https://github.com/bitcoin/bitcoin/pull/911) that was incorporated in version 0.5.3. 
The patch limits the number of orphan transactions that are stored in memory and randomly erases a previous stored transaction on the arrival of a new one, if the memory table becomes full.

Unfortunately the patch is ineffective and allows two new vectors of attack that are more severe than the original attack. The patched version still allows an attacker to fill the victim's memory with orphan transactions (see vulnerability 1) and it also allows an attacker to hang the victim's client application (see vulnerability 2) in less than 20 minutes.

=== Vulnerability 1 Details ===
-----------------------

Orphan transactions are stored in the table mapOrphanTransactions. The patch limits the number of entries to 10000 (constant MAX_ORPHAN_TRANSACTIONS). This number is arbitrary, and the criteria for the selection of the constant is unknown. Because transactions are not limited in size, is easy to create an orphan transaction whose size reaches 
1 megabyte. If the transaction is built with thousands of random inputs (prevouts which are unknown to the victim app) then also the table mapOrphanTransactionsByPrev can fill the entire RAM. Prevouts whose hash is chosen at random would make trashing worse since virtual memory page faults will become inevitable. 

Suppose the attacker wants the victim to store 4 Gigabytes of data in virtual memory. Assume a 50 Kb/sec connection bandwidth.
Then the attack takes approximately 11 hours.

=== Patching vulnerability 1 ===
------------------------

The application must limit the amount of memory used by tables mapOrphanTransactions and mapOrphanTransactionsByPrev, either by counting the number of bytes used or by limiting the maximum size of each orphan transaction.

Added note: Bitcoin version 0.6.3 and later only store orphan transactions whose size is less than 5000 byles. This limits the amount of memory that mapOrphanTransactions can consume, totalling no more than 50 Mbytes. Since the "map" data structure has a significant overhead when storing a single element, 5000 transactions that link to many random missing previns can force mapOrphanTransactionsByPrev to consume as high as 200 additional megabytes.

Some extra security provisions may be implemented:

* Prioritize orphan transactions that provide a proof of work per input (network protocol must be changed).
* Limit the amount of transactions that each peer can send depending on the peer connection time  (older peers get more bandwidth)

=== Vulnerability 2 Details ===
-----------------------

Each time a transaction must be erased from mapOrphanTransactions, all references to parent transactions must be erased from the table mapOrphanTransactionsByPrev too (see EraseOrphanTx()). The method wrongly assumes that the number of 
associations between a parent transaction and its potential childs is low, and so the code iterates through all pairs parent/child until the transaction to be erased is found. Code excerpt:

 BOOST_FOREACH(const CTxIn& txin, tx.vin)
    {
        for (multimap<uint256, CDataStream*>::iterator mi = mapOrphanTransactionsByPrev.lower_bound(txin.prevout.hash);
             mi != mapOrphanTransactionsByPrev.upper_bound(txin.prevout.hash);)
        {
            if ((*mi).second == pvMsg)
                mapOrphanTransactionsByPrev.erase(mi++);
            else
                mi++;
        }
    }


Each reference to a previous transaction is specified by a prevout, which is a hash of the transaction and an index of the outpoint referred. An attacker can send 10000 transactions that whose inputs refer to the same parent transaction (same hash), but specifying different indexes. Index numbers can be chosen incrementally (from 1 to 1M) since indexes cannot be verified to be out of range for a (still unknown) parent transaction.

The attack is strengthened by the fact that client applications do not check for empty scripts in inputs, so each input size can be as low as 41 bytes. 11K transaction containing 100 fake inputs each is enough to hang a Satoshi client in an Intel Core 2 CPU 4300 running on a local testnet in less than a minute. If a connection of 50 Kb/sec is assumed, then the attack takes less than 20 minutes. Note that only one core of the CPU gets 100% of usage, because the client runs a single thread to process all messages from peers. Simulations were carried on on a local testnet, so the outcome of the attack on a real node (with plenty of peer connections) was not evaluated.

=== Patching vulnerability 2 ===
------------------------

One possible change is to modify the mapOrphanTransactionsByPrev data structure from:

 multimap<uint256, CDataStream*> mapOrphanTransactionsByPrev;

to:

 map<uint256, map<uint256,CDataStream*> > mapOrphanTransactionsByPrev;

Example new EraseOrphanTx() method (not tested): 

 void static EraseOrphanTx(uint256 hash)
 {
    if (!mapOrphanTransactions.count(hash))
        return;
    const CDataStream* pvMsg = mapOrphanTransactions[hash];
    CTransaction tx;
    BOOST_FOREACH(const CTxIn& txin, tx.vin)
    {
       mapOrphanTransactionsByPrev[txin.prevout.hash].erase(hash);
    }
    mapOrphanTransactions.erase(hash);
 }


Added note: Bitcoin version 0.6.3 and later includes this modification.

=== Disclosure Timeline ===
-------------------

* 2012-05-12 - Vulnerability reported to Gavin Andressen
* 2012-05-17 - Gavin Andressen patches ready for review
* 2012-06-20 - 0.6.3rc1 available for testing
* 2012-06-25 - Bitcoin version 0.6.3 released, fixing the vulnerabilities.
* 2013-01-08 - Vulnerability disclosure

=== Credit ===
------

This vulnerability was discovered by Sergio Demian Lerner, from Certimix.com, who also did
the vulnerability research and report editing for the public good.

==See Also==

* [[Common Vulnerabilities and Exposures]]