Earlier this year, we opened a contest with a special focus on backdoors in cryptocurrencies. Despite offering a $500 first-place prize from our sponsor Zcash, and a $250 second-place prize from our sponsor NCC Cryptography Services, only one person sent in a submission. It’s a good one, though, and our judges agreed to award it the first-place prize.
Here’s the slide deck for our talk at Crypto & Privacy Village, where we announced the winner. The winning entry is by nickler. You can download the entire entry here (12KiB). What follows is the author’s own explanation of their entry.
F*** your shoebox money. Eleeterium is the next generation cryptocurrency. It offers perfect anonymity, infinite scalability, absolute decentralization and super-Turing hyper-complete smart contracts. Get your eleet coins and start profiting today. To do so just send all your bitcoins to burn address
3LEETmEZWJX9ULbsFQVgL2QgGCJHPZJVaJ to destroy them. This triggers the
creation of eleet coins and transfers them directly to your wallet. Coins sent to the burn address are provably unspendable. The address encodes the Bitcoin script
<signature> OP_2 <pubkey1> <pubkey2> OP_2 OP_CHECKMULTISIG (*). It’s easy to see that the multisig requires signatures for both pubkeys. One signature is already provided in the script. Of course it’s impossible to
create a valid signature for a fixed pubkey without knowing the message. Therefore, this script’s evaluation can never succeed and coins sent to it are transferred irreversibly.
(*) You can verify that yourself by executing
Burn addresses have been used in Bitcoin to transfer value to another blockchain in a one-way fashion. The idea is that coins sent to the burn address are destroyed which allows to create a proportional amount on the alternative blockchain. For example
1CounterpartyXXXXXXXXXXXXXXXUWLpVr is a historical burn address that was used to bootstrap the counterparty system. Another burn address is
1111111111111111111114oLvT2 which would require a signature for a public key whose RIPEMD-160 hash is all zeros.
In contrast, the burn address used to bootstrap Eleeterium is created from a multisig script. In general, spending coins in a multisig address requires providing signatures for the public keys stated in the script. Let’s look a little bit deeper into what happens when Alice sends coins to the burn address. Alice creates a transaction
TxA with an output
out0 that contains the script and an integer denoting the amount of coins.
+------------+ +------------+ | out0 +--------> in0 out0 | +------------+ +------------+ TxA TxB
If Bob would want to spend this output, Bob creates a transaction
TxB that has an input
in0 containing a reference to
out0 in the form of a
TxA‘s hash and
out0‘s index. Additionally, the input has to contain the script (scriptSig) which makes referenced output script (scriptPubKey) evaluate to true. Bob effectively moves the coins by adding an output
out0 to his transaction containing the public key of the receiver of the coins.
In the case of the burn address the encoded scriptPubKey is special because it already contains one of the two required signatures. The message for which the signature is verified is the hash of the transaction spending the coins (
TxB). However, at the time of creation of the scriptPubKey, the hash of
TxB can not be known to Bob because it contains Alice’s transaction hash. Therefore, the signature in the scriptPubKey must be invalid and there is no scriptSig that would allow spending the coins…
Exploiting the backdoor
Contrary to our expectation of signature schemes, the creator of the burn address is able to spend coins sent there because of a subtle bug in Bitcoin’s signature scheme known as
SIGHASH_SINGLE is a so called sighash flag. Sighash flags are appended to signatures and determine which part of the transaction is hashed and therefore which part of the transaction is covered by the signature. The standard sighash flag
SIGHASH_ALL indicates that all outputs of the transaction are signed. Its counterpart is
SIGHASH_NONE which to my knowledge does not have a use case as of today. A signature with the
SIGHASH_SINGLE flag covers only the output that has the same index as the input containing the signature. This can be useful when multiple parties jointly create a transaction by independently adding their own input-output pairs. Consider the following transaction subgraph:
+------------+ | out0 +---+ +------------+ | +------------+ TxA +----> in0 out0 | | | +----> in1 | +------------+ | +------------+ | out0 +---+ TxC | | | out1 | +------------+ TxB
If the signature in input
TxC has the
SIGHASH_SINGLE flag then the signature covers output
out0. What happens if a signature in input
in1 has the
SIGHASH_SINGLE flag and there is no corresponding output? It would be reasonable to assume that such a signature is invalid. And indeed Bitcoin’s SignatureHash function returns error code
1 in such a case. However,
1 is never interpreted as an error code but rather as the actual result of the hash function. What a classic bug!
It turns out that due to the SIGHASH_SINGLE bug the creator of the “burn” address is in fact in control of the coins. The python script appended to this article demonstrates insertion and exploitation of the backdoor using python-bitcoinlib and a private “regtest” Bitcoin network. In order to further investigate the resulting transactions, run
bitcoin-cli -regtest getrawtransaction <txid> 1.
The scammer created the backdoored address in the following way: He generated two fresh key pairs
(pubkey1, sk1), (pubkey2, sk2) and created a multisig script that requires a signature for
pubkey1 and a signature for
pubkey2. He used
sk2 to sign the message
1, added the resulting signature with
SIGHASH_SINGLE to the multisig script and converted the entire script to the “burn” address. The script requires multiple signatures to ensure that only he has access to the backdoor. Let’s assume Bob sends coins to the address in output
out0 of transaction
TxB. When the scammer decides to spend those coins, he creates a transaction
TxC that spends an arbitrary output he has control over (
TxA:out0) and the output sending to the “burn” address (
in1 has a greater index than
out0, the signature for
pubkey2 is valid and he just to provide a signature over
pubkey1. This time he uses
SIGHASH_ALL to protect from replay attacks against himself.
Bitcoin improvement proposal 141 (“Segregated Witness”) introduces a new signature scheme that fixes the
SIGHASH_SINGLE bug. If there is no corresponding output to the input then
SIGHASH_SINGLE will just behave like
SIGHASH_NONE and not sign any of the outputs. In contrast to the old scheme, the input reference is included in the signature hash which makes Eleeterium backdoor impossible in the new scheme. However, segregated witness is backwards compatible (“softfork”) and therefore does not prevent messing with the
SIGHASH_SINGLE bug. Segregated witness was merged into Bitcoin Core recently and will be fully deployed once the softfork activates.