Retry if r is zero during signing #732

1. 
   real-or-random commented at 1:10 pm on March 31, 2020: contributor

   This reverts commit 25e3cfbf9b52d2f5afa543f967a73aa8850d2038. The reverted commit was probably based on the assumption that this is about the touched checks cover the secret nonce k instead of 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.

   Then a second commit makes the resulting code constant-time in whether r is zero, in order to pass the new constant-time test.

   Fixes #720.

2. Revert "ecdsa_impl: replace scalar if-checks with VERIFY_CHECKs in ecdsa_sig_sign"

   This reverts commit 25e3cfbf9b52d2f5afa543f967a73aa8850d2038. The reverted
   commit was probably based on the assumption that this is about the touched
   checks cover the secret nonce k instead of 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.
   
   Fixes #720.

   93d343bfc5
3. Make ecdsa_sig_sign constant-time again after reverting 25e3cfb 37ed51a7ea
4. real-or-random renamed this:
   Return 0 if r is zero during signing
   Retry if r is zero during signing
   on Mar 31, 2020
5. 
   elichai commented at 9:30 am on April 1, 2020: contributor

   ACK 37ed51a7eafa5fd9955ceb66213251cdd8b8b8c4 makes sense. took me a minute to understand the comment but it looks correct.

   can we somehow test this condition under the exhaustive tests?

6. 
   jonasnick commented at 1:34 pm on April 10, 2020: contributor

   If I understand correctly this issue may not show up in the exhaustive tests if the curve order (EXHAUSTIVE_TEST_ORDER) is not a valid X coordinate.
7. 
   real-or-random commented at 12:44 pm on April 16, 2020: contributor

   If I understand correctly this issue may not show up in the exhaustive tests if the curve order (EXHAUSTIVE_TEST_ORDER) is not a valid X coordinate.

   Indeed. I’d be willing to write a test but I don’t see a way to come up with a test vector. So this is ready for review.

8. jonasnick approved
9. 
   jonasnick commented at 12:20 pm on April 18, 2020: contributor

   ACK 37ed51a7eafa5fd9955ceb66213251cdd8b8b8c4

   I looked into the exhaustive test code again because the overflow == 1 condition should have appeared in the exhaustive tests (the scalar group is only 13). But in the small order case scalar_set_b32 always sets overflow to 0 (“just deny overflow, it basically always happens”). I tried changing that, but it results in an infinite loop, presumably because it’s extremely unlikely that k does not overflow during a signing attempt.

10. jonasnick merged this on Apr 18, 2020
11. jonasnick closed this on Apr 18, 2020

    ---

12. sipa cross-referenced this on Jun 9, 2020 from issue Update libsecp256k1 subtree by sipa
13. fanquake referenced this in commit 8c97780db8 on Jun 13, 2020
14. sidhujag referenced this in commit 8a3a072968 on Jun 13, 2020
15. ComputerCraftr referenced this in commit b98f1c6e6c on Jun 16, 2020
16. jasonbcox referenced this in commit 1745e523aa on Sep 27, 2020
17. deadalnix referenced this in commit 67c1d7ecc9 on Sep 28, 2020
18. UdjinM6 referenced this in commit 9d36ba6570 on Aug 10, 2021
19. 5tefan referenced this in commit 8ded2caa74 on Aug 12, 2021
20. gades referenced this in commit d855cc511d on May 8, 2022

Contributors
real-or-random elichai jonasnick