Buggy CVE-2013-4627 patch, open new vectors of attack

Secure coding is hard. But in Bitcoin, secure coding also means understanding every little detail of the undocumented (or code-documented) rules that Satoshi the great has brought to us mortals. CVE-2013-4627 patches a DoS vulnerability discovered by Peter Todd. The vulnerability is easy to spot once you read the code after the patch was applied. Bitcoin network messages can be of arbitrary sizes, and this is generally not a problem, with the sole exception of transaction messages. Almost all objects that are exchanged between Satoshi clients are deserialized to be stored in memory and serialized again when they need to be forwarded. . Transactions are also first deserialized in order to be parsed, but they are stored “as is” in a temporary cache called MapRelay, and forwarded without being serialized again. I really don’t know why this is done. But the point is that the storage of messages as they are received leads to the possibility that an attacker creates messages much bigger than the actual transaction object contained, which, when stored in MapRelay memory, can be used to exhaust the memory of a node. This is the code that patches the vulnerability:

unsigned int nSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION);
unsigned int oldSize = vMsg.size();

if (nSize < oldSize) {
vMsg.resize(nSize); + printf("truncating oversized TX %s (%u -> %u)\n",
oldSize, nSize);

This patch that supposedly solves the CVE-2013-4627 bug opens the door at least two other attacks. Transactions on the wire may have an encoding which is different from the enconding you get when you serialize and deserialize it.
Still after many efforts to standardize transactions, preventing ambiguity and storing signatures in a canonical form, transactions are malleable. So when you truncate vMsg, you don’t know what are you truncating.

Double-spend Attack

My attack works against sites that accept 0 confirmations like SatoshiDice. It could allow 100% effective double-spends. The idea is that you create a message vMsg with a transaction Tx such that:

vMsg.size() == n
nSize = ::GetSerializeSize(tx, SER_NETWORK, PROTOCOL_VERSION) == n-1

But in the transaction stored in vMsg, the field vin.size is stored in a non-standard format that takes 4 bytes more.

Suppose that vin.size = 1. Then it is stored as: 0xfe 0x01 0x00 0x00 0x00, instead of being stored as “0x01”

When vMsg is truncated by vMsg.resize(nSize), it will become an invalid transaction (since 3 good bytes at the end will be chopped off).
Now the node that receives vMsg will process the Tx normally, but will relay the transaction vMsg (which is invalid). This is because the invalid tx in the msg will be stored in MapRelay for 15 minutes. Peers will ignore this invalid message. If the node processes Tx and responds with a transaction Tx’ (using Tx outputs, such as SatoshiDice) then Tx’ will end up in peer’s orphan cache, because Tx is not present since it wasn’t accepted.

So the attack works with 100% success rate for sites that create transactions as response to unconfirmed transactions, such as SatoshiDice, and are running version 0.8.3 of the Satoshi client.

Suppose that a site called InstantBitBets uses version 0.8.3 of the Satoshi client. The attack against InstantBitBets looks like this:

1. Locate the node of InstantBitBets. Connect directly to this node.
2. Create a bet in a Tx. Create a non-standard message vMsg with 1 extra byte and a non-standard  vin.size field.
3. Send it directly to InstantBitBets node.
4. If you receive a Tx’ saying that you won, broadcasts Tx to the rest of the network (normally).
5. If you’ve lost, move the funds from Tx to Tx2, and try again from Tx2 (this step might not even be necessary).

Also the attack could help to execute other kind of unknown attacks, since everybody expects a node to broadcasts successfully a Tx that it accepts.

Remote Anonymous Denial of Service Attack
If the right mix of Bitcoinj, old Satoshi nodes and new 0.8.3 nodes are present in the network, then a new attack vector emerges that is able to disconnect 0.8.3 nodes from Bitcoinj nodes remotely.
Consider, for example,  the following mix: old nodes=50%, 0.8.3 nodes=40%, Bitcoinj nodes=10%.

The attacker builds a transaction with an expanded var_int field (e.g.: input count). The expansion consist of encoding the count in more bytes than it is required. This transaction is forwarded to a bunch of 0.8.1 and prior clients. Alternatively, transactions passing through the attackers node can be modified on-the-fly, expanding the input count fields. Each of these clients will resend the tx without modification, and the tx will spread. When the transaction arrives to an old Satoshi code, it will broadcast it. When this transaction arrives to a 0.8.3 node, it will resend it truncated, and this will disconnect the 0.8.3 node from all Bitcoinj nodes surrounding it. I have not verified by testing that Bitcoinj does this, but I’m almost sure that the exception thrown will terminate the connection.
If the attack does not success the first time, the attacker can try as many times as he wants. As previously said, he can even use existing relayed transactions, expanding the input_count field. So after some minutes, and high number of modified txs, the attack must be successful.
The success probability depends on the number of old, 0.8.3 and bitcoinj nodes, and network topology. And the attackey may try sending the tx to different nodes to find the right path to the victim’s node. So I think that with enough tries, it will succeed even with very different client version mixes.

So basically the attack takes advantage of the network client mix, and remotely (an anonymously) harm 0.8.3/Bitcoinj nodes.
If the attacker knows that two victims are connected, one is a 0.8.3 nodes, and the other is a Bitcoinj node, he can remotely perform the attack to disconnect them.

Are these problems vulnerabilities of Bitcoin? It depends on what you expect from the protocol. If you expected the Satoshi code to be protected from DoS and 0-confirmation double-spends, then it is. It seems that Satoshi code was not designed to protect you from DoS, but it’s also true that the core developers have tried to add some DoS preventions since the Satoshi times. In any case, it’s only a minor vulnerability or flaw. What worries me is not that a bug was found, nor that a bug in the patch was found, but that the github commit of the patch does not show a history of  a discussion regarding the patch correctness, nor it is recorded if the code was audited and by whom. This lack of standardized protocol for the treatment of sensitive patches should be corrected, and I offer myself to review security critical code, whenever it is needed, and whenever I can.

, ,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: