View source for CVE-2012-4684

== Network-wide DoS using malleable signatures in alerts ==

Private Release Date: 24-AGO-2012<br />
Public Release Date: 01-MAR-2013<br />

== Systems Affected ==

* Satoshi Bitcoin Client (Bitcoin-Qt, bitcoind)
* All Bitcoin clients that mimic the behavior related to the alert system of Satoshi client versions prior 0.6.3

== Affected Versions ==

* 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

== Fixed in version ==

* Bitcoin version 0.7.0 released 2012-09-17

== Overview ==

Bitcoin protocol has an alert system to spread important news regarding the digital currency. Alerts are signed with a private ECDA key, so only the development team can issue new alerts. Nevertheless, prior version 0.7.0, alerts were identified by the hash of the message, which includes the signature. Bitcoin accepts BED-encoded signatures, which are malleable.
An attacker build new signatures at a high rate by changing the signature of an alert still in circulation and therefore increasing dramatically the number of valid alerts spreading across the network. This leads to halting all Bitcoin nodes in the network by RAM exhaustion in approximately 4 hours. The attack is persistent, since if a nodes restarted get flooded again by online peers.

== Details ==

There different ways an attacker can abuse the malleability of alert signatures:

- 1. An attacker may try to fill the RAM of all the nodes by sending 2000 modified alerts, each of 1 Mbyte size, using padding zeros. Such 1 Mbyte alerts would slowly spread through the network, and finally reach every node.

- 2.  An attacker may use the fact that an ECDSA signature consist of two numbers (r,s), and each one can be padded by zeros. By interleaving and extending the zero padding of s and r, the attacker can build a stream of correct signatures whose sizes grows with the square root of the number of signatures generated.
(for example, for X bytes of zero-padding you can generate X different modified signature alerts whose sizes are size(r)=72+i, size(s)=72+X-i for  0 <= i <= X)

This attack can try to exhaust GUI resources. For example, running the attack for 1 hour over a 64 Kbytes/sec link, the attacker is able to produce 321446 alerts. We have not evaluated how Qt responds in each platform to 321446  calls to QMessageBox::critical() without user interaction, but it's plausible that the application halts.

- 3.  An attacker can try to exhaust the victim's computer CPU by:

- 3.1. Forcing excessive signature verification time (this only happens with the very first small alerts sent, and for old CPUs )

- 3.2. Forcing excessive iterations of the loop : for (map<uint256, CAlert>::iterator mi = mapAlerts.begin(); mi != mapAlerts.end()Wink

As an example, in the first hour an attacker is able to send 321446 small alerts. The following hour the attacker is able to send 207757 alerts, starting at size 1218. With a 64 Kbytes/sec link, the attacker can send this last alerts at 52 alerts/second. The code block inside the for loop will be executed 321446*52 = 16,890,430 times, and that takes more than a second to process on an average computer, so CPU is exhausted in the loop.

To maximize the damage of an attack, an attacker requires an existing alert that is relevant for all versions of the protocol, and one that will not have expired and is still in the relay interval.  With such alert, the attacker can reach the maximum number of nodes. Because of this, the vulnerability should not be notified to users by using the alert system. By doing so the attacker may receive the tool required to mount the best possible attack.

== Attack Scenario ==

The best attack is to harm the entire network and possibly generate a rush to the coin. To simplify the analysis, we assume that an average connection bandwidth is 64 Kbytes/sec and that each node has 2 GB of RAM, plus 2 GB of swap space. We assume the attacker executes the attack 1 described in the previous section, which tries to exhaust RAM, but leaves the CPU resources intact to keep spreading the fake alerts. If the such an attack is executed, every node in the network will start trashing after 1.5 hours approximately, as Bitcoin application will be using more than 1.5 GB of RAM. After 2 hours, every node running in Windows 32-bits will halt, since the address space of 2 Gb will be filled. After 8.7 hours, every 64-bit node still alive will fill both the 2 Gb of RAM and the 4 gigabytes of hard disk swap space assumed, and the Bitcoin application will halt.

It is supposed that, in Bitcoin-Qt application, QMessageBox::critical() with modal=false will be called for each alert, so the application may crash much sooner due to lack of Windows or whatever GUI resources Qt uses. This is only relevant to Bitcoin-qt and not Bitcoind releases.

== Suggested Solutions for the 0.7.0 release ==

# Change the way the hash of alerts is computed: exclude the signature from the hash.
# Reject alert signatures that are not DER-encoded.
# Check setKnown before checking signatures.
# Support a special fixed alert message that cancels all previous alerts. This would be a damage control measure if all other protections are violated.

Solutions 1,3 and 4 were implemented in Bitcoin version 0.7.0.

== Disclosure Time-line ==

2012-08-24 - Vulnerability reported to Gavin Andressen and other core devs.<br />
2012-08-24 - Gavin Andressen acknowledges report<br />
2012-08-26 – Private discussions of Gavin Andressen, Gregory Maxwell and Sergio Lerner on how to address the vulnerability.<br />
2012-08-26 – Fix finally scheduled for the 0.7.0 release<br />
2012-09-17 - Bitcoin version 0.7.0 released<br />
2013-03-01 - Patched Bitcoin versions reach 80% of the network nodes upgraded.<br />
2013-03-01 - Vulnerability disclosure<br />

== Credit ==

This vulnerability was discovered by Sergio Demian Lerner, from [http://Certimix.com Certimix.com].<br />
Bitcointalk user Enochian was the first to publish BER/DER encoding problems of Bitcoin signatures in this thread: https://bitcointalk.org/index.php?topic=8392.0. <br />
This report was written by SDL.

==See Also==

* [[Common Vulnerabilities and Exposures]]