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.
Our sponsors:
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.
Nickler’s Explanation
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.
-q.e.d.
(*) You can verify that yourself by executing bitcoin-cli decodescript
47304402203c5288058306b3bf5cd8202413b867e11588a351117a07b9929f41f693043623022017430fa896ff26763970aa9f0c169d48250ac274fe9b3313b37ea585a7358eda035221023b439207c8a0a082a5c5a968632be9a363f5e1a4150276604eedbaa4943f2650210316b0dbf710b8739eec21a806e7142db1755a0f902b79ccef3116c782a74a510652ae
.
–cryptopirate42
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 TxA
‘s output 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
bug. 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 in0
of 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 (TxB:out0
). Because in1
has a greater index than out0
, the signature for pubkey2
is valid and he just to provide a signature over TxC
for 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.
nickler, 2016-06-30