Erroneous comment and VERIFY_CHECK in ecdsa_sig

LLFourn commented at 3:32 pm on February 27, 2020: none

I’ve been following along the ECDSA signing code and have come across what I think is an incorrect comment. In secp256k1_ecdsa_sig_sign the code makes the following recommendation:

https://github.com/bitcoin-core/secp256k1/blob/96d8ccbd16090551aa003bfa4acd108b0496cb89/src/ecdsa_impl.h#L285-L293

However, these two conditions are not actually checked before calling. The main call doesn’t:

https://github.com/bitcoin-core/secp256k1/blob/96d8ccbd16090551aa003bfa4acd108b0496cb89/src/secp256k1.c#L491-L510

Note that sigr is the nonce (R)’s x coordinate reduced modulo q as a scalar. The caller is only checking properties of the secret nonce not sigr (it doesn’t even compute the point for R). Maybe this code was meant to check the secret nonce that’s passed in instead?

There doesn’t seem to be any problem with sigr overlfowing (the verification algorithm actually accounts for this possibility by adding the curve order to sigr if it doesn’t work the first time!). sigr being 0 is a problem but the probability of this happening is so low I wouldn’t bother accounting for it. I think this comment and VERIFY_CHECKS can be removed.

More generally there doesn’t seem to be a problem with the secret nonce overflowing either but the while loop in the caller enforces that and that it’s not 0.

real-or-random commented at 10:20 am on March 4, 2020: contributor

Hm, this in indeed strange. I agree, this is not an issue. Both of these conditions are computationally unreachable, so this is not a problem and not at all exploitable. But we should still fix it.

This was introduced by @apoelstra in https://github.com/bitcoin-core/secp256k1/commit/25e3cfbf9b52d2f5afa543f967a73aa8850d2038. As I read this commit message, I think he really had the secret nonce k in mind instead r, which is the x-coord of the public nonce. A signature with a zero r is invalid by the spec, so we should return 0 to make the caller retry with a different nonce. Overflow is not an issue.

I think we should basically revert that commit, but then change the resulting code to fail late to be compliant with the new constant-time test (#710, #708). @apoelstra Can you comment on this?

apoelstra commented at 1:22 pm on March 11, 2020: contributor

Yeah I have no idea what I was thinking here. These are cryptographically unreachable, and it doesn’t make sense for the caller to have checked them. Possibly I ran into trouble with the exhaustive tests and put the comment in for that reason.

Agree with Tim’s solution.

real-or-random referenced this in commit 93d343bfc5 on Mar 31, 2020

real-or-random cross-referenced this on Mar 31, 2020 from issue Retry if r is zero during signing by real-or-random

jonasnick closed this on Apr 18, 2020

jonasnick referenced this in commit ecd8b17b9e on Apr 30, 2020

jonasnick referenced this in commit 9b6a59c15d on May 12, 2020

Erroneous comment and VERIFY_CHECK in ecdsa_sig_sign #720