Remove unnecessary sign variable from wnaf

jonasnick commented at 8:06 pm on April 17, 2020: contributor

There currently is a single branch in the ecmul_const function that is not being exercised by the tests. This branch is unreachable and therefore I’m suggesting to remove it.

For your convenience the paper the wnaf algorithm can be found here (The Width-w NAF Method Provides Small Memory and Fast Elliptic Scalar Multiplications Secure against Side Channel Attacks). Similarly, unless I’m missing something important, I don’t see how their algorithm needs to consider sign(u[i-1]) unless d can be negative - which doesn’t make much sense to me either.

jonasnick cross-referenced this on Apr 17, 2020 from issue Review if ECDH is still experimental by ysangkok

in src/ecmult_const_impl.h:113 in 3d555b359e outdated

112-        u += sign * even;
113-        u_last -= sign * even * (1 << w);
114+        /* In contrast to the original algorithm, u_last is always > 0 and
115+         * therefore we do not need to check its sign. In particular, it's easy
116+         * to see that u_last is never < 0 because u is never < 0. Moreover,
117+         * u_last is never = 0 because u is never even. */

real-or-random commented at 11:52 am on April 18, 2020:

I think “u is never even” is not true.

jonasnick commented at 12:27 pm on April 18, 2020:

should say “u is never even after a loop iteration”

in src/ecmult_const_impl.h:116 in 3d555b359e outdated

113-        u_last -= sign * even * (1 << w);
114+        /* In contrast to the original algorithm, u_last is always > 0 and
115+         * therefore we do not need to check its sign. In particular, it's easy
116+         * to see that u_last is never < 0 because u is never < 0. Moreover,
117+         * u_last is never = 0 because u is never even. */
118+        VERIFY_CHECK(u_last > 0);

real-or-random commented at 12:54 pm on April 18, 2020:

0        VERIFY_CHECK(u_last > 0);
1        VERIFY_CHECK(u_last & 1 == 0);

jonasnick commented at 9:57 am on April 28, 2020:

I would argue that this is excessive given that the u_last > 0 is only there to show a single specific difference to the paper and the whole point of the algorithm is that u is never even. But I can see that this slightly helps review if you don’t look at the paper. I added this line.

jonasnick commented at 6:57 pm on April 28, 2020:

should be VERIFY_CHECK((u_last & 1) == 1); (“is never even”)

real-or-random commented at 7:05 pm on April 28, 2020:

Don’t trust code I’ve written using the GitHub web interface.

edit: To be clear, don’t trust any code I’ve written.

in src/tests.c:3225 in 3d555b359e outdated

3220@@ -3220,7 +3221,8 @@ void test_constant_wnaf(const secp256k1_scalar *number, int w) {
3221         secp256k1_scalar_add(&x, &x, &t);
3222     }
3223     /* Skew num because when encoding numbers as odd we use an offset */
3224-    secp256k1_scalar_cadd_bit(&num, skew == 2, 1);
3225+    secp256k1_scalar_set_int(&scalar_skew, 1 << (skew == 2));
3226+    secp256k1_scalar_add(&num, &num, &scalar_skew);

real-or-random commented at 12:55 pm on April 18, 2020:

Can you explain this change?

jonasnick commented at 7:34 pm on April 22, 2020:

I added a test with num = n-1, but cadd_bit can not deal with overflows. Will add that to the commit description.

jonasnick force-pushed on Apr 28, 2020

in src/tests.c:3362 in f95fb318ee outdated

3345+    /* Test -1, because it's a special case in wnaf_const */
3346+    n = secp256k1_scalar_one;
3347+    secp256k1_scalar_negate(&n, &n);
3348+    test_constant_wnaf(&n, 4);
3349+
3350+    /* Test 0 for fixed wnaf */

real-or-random commented at 7:13 pm on April 28, 2020:

This comment should be in above line 3337?

jonasnick commented at 7:27 pm on April 28, 2020:

There’s a difference between constant and “fixed” wnaf. This comment is about the fixed wnaf call below. If that’s confusing I think we can just remove it.

real-or-random commented at 9:10 pm on April 28, 2020:

Okay, I really got confused because the commit message said “This commit also adds a test for 0.” and then my impression was that you added the test but the comment in different places.

Don’t remove it. The resulting code is not confusing, just the diff confused me.

real-or-random commented at 11:59 am on April 29, 2020: contributor

ACK modulo this:

It took me some more effort to think about the invariant in the first loop iteration, which depends on all that negation/flipping stuff before the loop.

This made me add two tests tests, which for example catch a bug if we’d change flip to secp256k1_scalar_is_high(&s) here: https://github.com/bitcoin-core/secp256k1/pull/741/files#diff-bb69027d01eaa0554f24272ea41380a0L97`. So this was not covered by the tests previously. But it’s not worth to have a separate PR. Can you cherry-pick the two top commits from mhttps://github.com/real-or-random/secp256k1/tree/ecmult_const_playground and squash this if you agree with the additions?

jonasnick force-pushed on Apr 29, 2020

jonasnick commented at 12:34 pm on April 29, 2020: contributor

Thanks for the additional edge case tests. Cherry-picked and squashed.

jonasnick force-pushed on Apr 29, 2020

Fix test_constant_wnaf for -1 and add a test for it.

Before, test_constant_wnaf used scalar_cadd_bit to correct for the skew. But
this function does not correctly deal with overflows which is why num = -1
couldn't be tested.

This commit also adds tests for 0, 1/2 and 1/2-1 as they are corner cases
in constant_wnaf.

6bb0b77e15

Remove unnecessary sign variable from wnaf_const 37dba329c6

real-or-random commented at 2:33 pm on April 29, 2020: contributor

ACK 37dba329c6cb0f7a4228a11dc26aa3a342a3a5d0 I verified the correctness of the change and claimed invariant by manual inspection. I tested the code, both with 32bit and 64bit scalars.

real-or-random approved

real-or-random commented at 2:33 pm on April 29, 2020: contributor

ACK

real-or-random requested review from apoelstra on Apr 30, 2020

real-or-random cross-referenced this on Jul 26, 2020 from issue Improve constant-timeness on PowerPC by real-or-random

gmaxwell commented at 10:05 am on July 26, 2020: contributor

ACK. I reviewed the code and agree that it cannot be negative. I also added a test to check vastly more values, tested with endomorphism on-and-off, and introduced several faults and confirmed that the tests work.

real-or-random removed review request from apoelstra on Jul 26, 2020

real-or-random merged this on Jul 26, 2020

real-or-random closed this on Jul 26, 2020

jasonbcox referenced this in commit ba5ec2d463 on Sep 27, 2020

deadalnix referenced this in commit 35b58110b9 on Sep 28, 2020

Remove unnecessary sign variable from wnaf_const #741