In February 2014, the bitcoin exchange Mt Gox – at this time one of the largest trading platforms in the market – had to suspend withdrawals completely, apparently in an attempt to recover from a massive attack. A few days later, the company filed for bankruptcy, claiming that it had lost 850.000 BTC, at this time worth roughly 500 Mio. USD. Earlier press releases issued by Mt Gox indicated that a weakness of the bitcoin protocol called transaction malleability had been leveraged by an attacker to steal the bitcoin – a claim that could not be confirmed by an independent analysis carried out by two researchers from the ETH Zürich a few weeks later. Still, that research also showed that this weakness was actively exploited, even though not at the scale claimed by Mt Gox. The purpose of this post is to explain this weakness in a bit more detail and show how it is related to the scripting language used in the bitcoin protocol.
We have seen that signatures and public keys in a bitcoin transaction come as parts of scripts, and that verifying a signature is equivalent to executing a script built out of a transaction input and the corresponding transaction output. Theoretically, this approach is extremely flexible – we could use any valid script and obtain a valid bitcoin transaction.
However, in practice, the bitcoin reference implementation has a few built in checks that restrict the set of scripts that are accepted, and also the scripting language itself has some limitations, there are, for instance, no loops. This has several reasons.
The first reason is the possibility of a denial-of-service attack on a bitcoin node. Suppose the scripting language were powerful enough to build a program that never terminates. When a transaction containing such a script is validated by a node, it starts the scripting engine to validate the transaction and gets stuck in an infinite loop, thus blocking at least one thread forever. Even worse, a very powerful and complicated scrip could leverage errors in the implementation of the scripting engine and so malicious code could be injected into a bitcoin node as part of a transaction. Thus, from a security point of view, it makes sense to place some limitations on the set of allowed scripts.
However, there is another, more subtle reason which is a consequence of the fact that, if a bitcoin transaction is signed, the signature script is not part of the data to which the signature is actually applied, as we will see in a later post. To illustrate why this could be a problem, suppose Alice owes Bob 50 bitcoins and makes a corresponding payment. So she would assemble a transaction – let me call that A – and sign it with her private key. She would then publish that transaction in the network. For bookkeeping purposes, her wallet would probably remember the ID of the transaction. By convention, the ID of a bitcoin transaction is simply its hash value.
Bob could now try the following attack. He could obtain the transaction from the network before it is added to a block, change its signature script by adding some code to the script that essentially does nothing, and publish that transaction as transaction B, as indicated below.
If the new, updated signature script is functionally equivalent to the script contained in A, both transactions would be valid. Moreover, both refer to the same unspent transaction output. However, as they have different signature scripts, they have different hash values and therefore different transaction IDs.
What Bob is hoping for is that the manipulated transaction B created by him is picked up by a miner first and added to a block. Bob would then obtain the bitcoin payment. However, Alice transaction A would be rejected due to double spend! Therefore Bob could now approach Alice and claim that he never received the payment. If Alice checks the status of the transaction ID that she knowns – that of transaction A – she would in fact learn that the transaction has been rejected by the network. In the worst case, she would feel obliged to initiate another payment, and Bob would receive the amount twice.
A similar situation could arise if Bob simply alters the signature created by Alice by replacing s by -s. This would still be a valid signature, but also changes the hash value and therefore the transaction ID.
This is the weakness that has been termed transaction malleability – the ability to modify a transaction without having to sign it again.
Can that be exploited to actually steal bitcoins? Well, maybe. Suppose that Alice is in fact a bitcoin exchange like Mt Gox, managing a large amount of bitcoins for different users. Suppose further that this exchange has implemented a wallet that automatically re-issues a transaction if the first transaction is rejected by the network. In this case, a malicious attacker like Bob could request withdrawals from the exchange, i.e. transfer to his own bitcoin address, and could then create and post modified transactions for each of the resulting transactions generated by the exchange. Even if only a certain percentage of the modified transactions are actually included in the blockchain, this could in fact lead to multiple payments triggered in favor of Bob, so that Bob can actually steal a significant amount of bitcoins from the exchange.
With BIP 62 and BIP 66, certain standards for scripts and the decoding of the signature are enforced to avoid these issues. With the segregated witness features (BIP 141 (Segregated witness)), additional protection is implemented as the signature is no longer part of the transaction that is signed. This at least addresses the currently known sources of transaction malleability. However, as always, this does not guarantee that similar flaws will not be detected and actively exploited in the future. The lesson is obvious – like any other complex distributed system, the blockchain is not immune to this kind of problems and will never be – developers and users should be aware of this.
LeftAsExercise 