3

In the Yellow paper, appendix F "Signing Transactions", it says a valid signature must satisfy:

(281)       0 < s < secp256k1n ÷ 2 + 1

However, in both the cited paper here (ECDSA SIGNATURE VERIFICATION heading) and wikipedia, it is said that r and s must be verified to be in [1, n-1], which is understandable given that they are results of a modulo n operation.

So why does Ethereum restrict s to only half of its usual range?

And how should a wallet proceed if a signature it generates contains an invalid s as per the paper? Generating a new one with different k?


Edit 1: Not Duplicate clarification

I honestly can't see how this question is a duplicate of the linked question, but here goes:

  • This question is about s in the signature triplet (v, r, s), while the linked question is about v, specifically the recovery id contained in v
  • This question is about a validity check of s, which is more restrictive than original ECDSA scheme, whereas the linked question doesn't even have any mention about such check in both the question and accepted answer. In fact, the validity check in question requires s < n/2 + 1, while the linked question's answer provided a sample code of how to produce recovery id in the case s > n/2 (quoted below), which suggests the validity check in question does not apply, because otherwise such code would be pointless.

    if (s > curve.n / 2) id = id ^ 1; // Invert id if s of signature is over half the n

  • I also do think this is duplicate but I think it is out of the scope here, perhaps a better place to ask about it is crypto.stackexchange.com – Ismael Aug 1 '18 at 13:45
  • 1
    This is a great question, not really sure why it got closed. Very ETH specific as well, although maybe not at first glance. – Tjaden Hess Aug 2 '18 at 18:47
1

The restriction that s < n/2 + 1 is not a requirement of ECDSA, but is specified in EIP-2

All transaction signatures whose s-value is greater than secp256k1n/2 are now considered invalid. The ECDSA recover precompiled contract remains unchanged and will keep accepting high s-values; this is useful e.g. if a contract recovers old Bitcoin signatures.

The reasoning is

Allowing transactions with any s value with 0 < s < secp256k1n, as is currently the case, opens a transaction malleability concern, as one can take any transaction, flip the s value from s to secp256k1n - s, flip the v value (27 -> 28, 28 -> 27), and the resulting signature would still be valid. This is not a serious security flaw, especially since Ethereum uses addresses and not transaction hashes as the input to an ether value transfer or other transaction, but it nevertheless creates a UI inconvenience as an attacker can cause the transaction that gets confirmed in a block to have a different hash from the transaction that any user sends, interfering with user interfaces that use transaction hashes as tracking IDs. Preventing high s values removes this problem.

This trick works because the r value does not uniquely determine a point, but determines a point +-R up to sign, while the v determines the sign.

When we do ECDSA recovery, we note that

s = k^-1(z+rd)

So the public key dG is given by

dG = r^-1(sR - zG)

If we flip the sign on s, and also on R then (-s)(-R) = sR, so the new signature gives the same public key.

Notably, Bitcoin does not impose this requirement and thus has malleable transactions, which was potentially used to steal funds from Mt. Gox.

  • Great answer! Do you have some resources on how s and -s are both valid signature in ECDSA? I searched for transaction malleability but couldn't find any in-depth explanation (from cryptography point of view) about how that works. I had to dive into ECDSA myself and figured out a little, yet it's still not very clear due to my lack of understanding in ECC math. – lenin Aug 6 '18 at 10:01
  • Edited to include a quick explanation of the EC arithmetic involved – Tjaden Hess Aug 6 '18 at 13:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.