Only create signatures with even S, and verification mode to check. #2131

sipa commented at 9:11 PM on December 26, 2012: member

To fix a minor malleability found by Sergio Lerner (reported here: https://bitcointalk.org/index.php?topic=8392.msg1245898#msg1245898)

The problem is that if (R,S) is a valid ECDSA signature for a given message and public key, (R,-S) is also valid. Modulo N (the order of the secp256k1 curve), this means that both (R,S) and (R,N-S) are valid. Given that N is odd, S and N-S have a different lowest bit. We solve the problem by forcing signatures to have an even S, excluding one of the alternatives.

This pull request just changes the signing code to always produce even S values, and adds a verification mode to check it. This code is not enabled anywhere yet. Existing tests in key_tests.cpp verify that the produced signatures are still valid.

in src/key.cpp:None in d3f6d65951 outdated

 289 | -    vchSig.resize(nSize); // Make sure it is big enough
 290 | -    if (!ECDSA_sign(0, (unsigned char*)&hash, sizeof(hash), &vchSig[0], &nSize, pkey))
 291 | -    {
 292 | -        vchSig.clear();
 293 | +    ECDSA_SIG *sig = ECDSA_do_sign((unsigned char*)&hash, sizeof(hash), pkey);
 294 | +    if (sig == NULL)

gavinandresen commented at 6:48 PM on December 27, 2012:

Subtle change in semantics here: if sig == NULL, the old code cleared vchSig.

For defensive programming, I'd suggest a vchSig.clear(); as the first statement in this routine.

sipa commented at 4:12 PM on December 28, 2012: member

@gavinandresen Updated.

BitcoinPullTester commented at 7:46 AM on January 3, 2013: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/3e4655404a8839a03c241fdcf67e063940eb462b for binaries and test log.

BitcoinPullTester commented at 1:51 PM on January 18, 2013: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/e1771b85af3d16e12bab2243ea50adf2d52eaf3c for binaries and test log.

gavinandresen commented at 2:41 PM on January 23, 2013: contributor

I think this goes one step too far.

Some almost-baked thoughts on the problem we're actually trying to solve (we'd like transactions ids to be immutable):

I think this ties into a bunch of other almost-baked thoughts I've had surrounding bumping the transaction.version. I think it might make sense to introduce transaction.version=2 messages onto the network, with additional rules for relaying/DoS-banning. In particular, I'm imagining a signature from one of the keys used to sign the inputs (maybe.. . more thought needed on how the signing is tied to the transaction's creator) that covers the transaction id and transaction fee paid.

That should solve the "relayer modifies the signature to change the txid".

(the transaction fee paid would be to help out SPV clients, which is a separate feature)

BitcoinPullTester commented at 4:38 AM on January 24, 2013: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/e1771b85af3d16e12bab2243ea50adf2d52eaf3c for binaries and test log.

gmaxwell commented at 4:42 AM on January 24, 2013: contributor

DOS rules don't prevent a miner from modifying a transaction. We really do need to actually remove the malleability. ... though the actual enforcement would need to be on a version=2 transaction.

sipa commented at 9:42 AM on February 5, 2013: member

@gavinandresen I really don't like the fact that this would mean rules at the transaction validation level would need knowledge about the precise inner script semantics. IMHO, we should just gradually introduce rules to remove malleabilities, and then perhaps use tx.nVersion==2 rule to enforce them in the block chain at some later point.

luke-jr commented at 4:29 AM on July 17, 2013: member

@sipa Needs rebase (or close if it was merged in another form?).

Only create signatures with even S, and verification mode to check.

To fix a minor malleability found by Sergio Lerner (reported here:
https://bitcointalk.org/index.php?topic=8392.msg1245898#msg1245898)

The problem is that if (R,S) is a valid ECDSA signature for a given
message and public key, (R,-S) is also valid. Modulo N (the order
of the secp256k1 curve), this means that both (R,S) and (R,N-S) are
valid. Given that N is odd, S and N-S have a different lowest bit.
We solve the problem by forcing signatures to have an even S value,
excluding one of the alternatives.

This commit just changes the signing code to always produce even S
values, and adds a verification mode to check it. This code is not
enabled anywhere yet. Existing tests in key_tests.cpp verify that
the produced signatures are still valid.

a81cd96805

sipa commented at 10:19 PM on August 15, 2013: member

Rebased. @jgarzik @gmaxwell @gavinandresen @laanwj: opinions?

gmaxwell commented at 10:26 PM on August 15, 2013: contributor

Without this, or a substantially similar, change we cannot eliminate malleability attacks on unconfirmed transaction chains.

Though I almost wish the evenness procedure had been specified in BIP32, as now we're going to see hardware wallet deployed that produce odd signatures. They can be fixed with an after the fact mutation, so perhaps thats not the end of the world.

BitcoinPullTester commented at 11:07 PM on August 15, 2013: none

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/a81cd96805ce6b65cca3a40ebbd3b2eb428abb7b for binaries and test log. This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

gavinandresen commented at 12:20 AM on August 16, 2013: contributor

ACK.

gmaxwell referenced this in commit 47491a90b6 on Aug 16, 2013

gmaxwell merged this on Aug 16, 2013

gmaxwell closed this on Aug 16, 2013

lunokhod referenced this in commit 35befa1584 on Feb 26, 2015

HashUnlimited referenced this in commit b607e74e9d on Jul 2, 2018

HashUnlimited referenced this in commit 4c770f6c73 on Jul 2, 2018

HashUnlimited referenced this in commit e67a2cae02 on Jul 2, 2018

HashUnlimited referenced this in commit c988c1124f on Jul 3, 2018

sidhujag referenced this in commit fb7410b474 on Jul 6, 2018

owlhooter referenced this in commit 6bf389afb8 on Oct 11, 2018

DrahtBot locked this on Sep 8, 2021