Skip to content
This repository has been archived by the owner. It is now read-only.

Signature Malleability #1129

Closed
bytemaster opened this issue Dec 11, 2014 · 10 comments

Comments

5 participants
@bytemaster
Copy link
Contributor

commented Dec 11, 2014

If elliptic curve signatures have the property that:

digest(transaction) + signature => pulbic_key
AND
digest(transaction) + (-signature mod N) => public_key

Then given a transaction signed with signature, you could create two identical transactions (transaction that execute the same operations) that each transaction has a different ID because the hash of the signatures would be different.

The block chain currently only checks for duplicates of transaction ID and not duplicates of digest(transaction).

Under this assumption then all transactions need to withdraw at least 51% of full balance and deposit change back to a new balance record or the receiver could replay the transaction with the modified signature and execute a double spend (within the expiration window of the transaction).

If the above property is true of elliptic curve crypto then a hard fork will be required to change how the transaction ID is calculated.

Signature Malleability

The first form of malleability is in the signatures themselves. Each signature has exactly one DER-encoded ASN.1 octet representation, but openssl does not enforce this, and as long as a signature isn't horribly malformed, it will be accepted.[1] In addition for every ECDSA signature (r,s), the signature (r, -s (mod N)) is a valid signature of the same message.[2]

bytemaster added a commit that referenced this issue Dec 11, 2014

Issue #1129 - Fix for Transaction Malleqbility
This patch creates a hard fork where signature format becomes far more
strict than SSL strictly allows.   It depends upon a recent update to FC
which allows optional strict checking of signatures.
@drltc

This comment has been minimized.

Copy link
Contributor

commented Dec 11, 2014

I think adding a check for uniqueness of H(tx) would mitigate this issue and only require delegates to upgrade.

@drltc

This comment has been minimized.

Copy link
Contributor

commented Dec 11, 2014

Although:

  • Getting a fix out there quickly is more important than avoiding a hardfork at this point, @bytemaster's patch gets +5% since it's already written
  • On reflection, I realized that checking for uniqueness of H(tx) would still require an upgrade block number to avoid risking a permanently forked chain (otherwise, at the moment that 51 delegates have switched over to the new semantics, 50 old delegates and some standby delegates may decide to start producing their own branch)

So maybe we'll leave uniqueness check on H(tx) to some future patch, and focus on getting @bytemaster's fix into the wild.

How quickly can we make a new release and get delegates to upgrade?

Is this serious enough that we should recommend merchants / exchanges to shut down and transact their entire balance to themselves until we fix it?

@drltc

This comment has been minimized.

Copy link
Contributor

commented Dec 11, 2014

Also, adding missing citations from OP would be appreciated.

@nmushegian

This comment has been minimized.

Copy link
Contributor

commented Dec 11, 2014

I wrote tests for the malleability cases we discussed which aren't in the OP and ad4c5d8 passes them all.

bytemaster added a commit that referenced this issue Dec 11, 2014

Issue #1129 - Fix for Transaction Malleqbility
This patch creates a hard fork where signature format becomes far more
strict than SSL strictly allows.   It depends upon a recent update to FC
which allows optional strict checking of signatures.

Conflicts:
	libraries/blockchain/include/bts/blockchain/checkpoints.hpp
	libraries/blockchain/include/bts/blockchain/fork_blocks.hpp

bytemaster added a commit that referenced this issue Dec 12, 2014

Issue #1129 - Fix for Transaction Malleqbility
This patch creates a hard fork where signature format becomes far more
strict than SSL strictly allows.   It depends upon a recent update to FC
which allows optional strict checking of signatures.

Conflicts:
	libraries/blockchain/include/bts/blockchain/checkpoints.hpp
	libraries/blockchain/include/bts/blockchain/fork_blocks.hpp

@vikramrajkumar vikramrajkumar added this to the v0.4.26 milestone Dec 13, 2014

pmconrad added a commit to PTS-DPOS/PTS that referenced this issue Dec 15, 2014

Issue bitshares#1129 - Fix for Transaction Malleqbility
This patch creates a hard fork where signature format becomes far more
strict than SSL strictly allows.   It depends upon a recent update to FC
which allows optional strict checking of signatures.

Conflicts:
	libraries/blockchain/include/bts/blockchain/checkpoints.hpp
	libraries/blockchain/include/bts/blockchain/fork_blocks.hpp
	libraries/blockchain/include/bts/blockchain/transaction_evaluation_state.hpp
	libraries/fc
@vikramrajkumar

This comment has been minimized.

Copy link
Member

commented Dec 16, 2014

And: a7ddce2

@vikramrajkumar

This comment has been minimized.

Copy link
Member

commented Dec 18, 2014

Also: f90c842

@vikramrajkumar

This comment has been minimized.

Copy link
Member

commented Dec 23, 2014

Still buggy; unique transaction cache isn't populated properly on startup since chain_id hasn't been initialized yet: https://github.com/BitShares/bitshares/blob/bitshares/libraries/blockchain/chain_database.cpp#L152-L157

@vikramrajkumar

This comment has been minimized.

Copy link
Member

commented Dec 24, 2014

Dupe feed update seems to have slipped in 3 days ago: 9a24317

Haven't figured out whether we are still vulnerable but it was in all likelihood due to the poor transaction cache handling that is still in master branch. This code has been rewritten in bitshares branch which is what revealed the above dupe.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
You can’t perform that action at this time.