Add exhaustive test for group functions on a low-order subgroup #310

apoelstra commented at 1:13 AM on September 18, 2015: contributor

We observe that when changing the b-value in the elliptic curve formula y^2 = x^3 + ax + b, the group law is unchanged. Therefore our functions for secp256k1 will be correct if and only if they are correct when applied to the curve defined by y^2 = x^3 + 4 defined over the same field. This curve has a point P of order 199.

This commit adds a test which computes the subgroup generated by P and exhaustively checks that addition of every pair of points gives the correct result.

Unfortunately we cannot test scalar multiplication, const-time or otherwise, by the same mechanism. The reason is that our ecmult functions both compute a wNAF representation of the scalar, and this representation is tied to the order of the group.

Testing with the incomplete version of gej_add_ge (found in 5de4c5dff^) shows that this detects the incompleteness when adding P - 106P, which is exactly what we expected since 106 is a cube root of 1 mod 199.

Exhaustive tests added for the following internal functions:

secp256k1_ge_is_infinity, secp256k1_gej_is_infinity
secp256k1_gej_add_var, secp256k1_gej_add_ge, secp256k1_gej_add_ge_var, secp256k1_gej_add_zinv_var
secp256k1_gej_double_nonzero, secp256k1_gej_double_var
secp256k1_ge_neg, secp256k1_gej_neg
secp256k1_ecmult, secp256k1_ecmult_const

And also (unfortunately with a bit of surgery; the original functions don't work with small group orders)

secp256k1_ecdsa_sign
secp256k1_ecdsa_verify

apoelstra commented at 1:15 AM on September 18, 2015: contributor

Fixes #308.

apoelstra force-pushed on Sep 18, 2015

in src/tests.c:None in 7e53d50a80 outdated

1306 | +        secp256k1_fe_t z;
1307 | +        random_fe(&z);
1308 | +
1309 | +        secp256k1_gej_add_ge(&groupj[i], &groupj[i - 1], &gen);
1310 | +        secp256k1_ge_set_gej(&group[i], &groupj[i]);
1311 | +        secp256k1_fe_mul(&groupj[i].z, &groupj[i].z, &z);

sipa commented at 8:50 PM on September 18, 2015:

Use secp256k1_gej_rescale ?

apoelstra force-pushed on Sep 18, 2015

apoelstra force-pushed on Sep 19, 2015

apoelstra commented at 5:06 PM on September 19, 2015: contributor

Push to move exhaustive tests to their own binary; add testing for non-constant ecmult code.

apoelstra force-pushed on Sep 19, 2015

sipa commented at 7:48 PM on September 22, 2015: contributor

Needs rebase (even if github doesn't realize that).

sipa cross-referenced this on Nov 2, 2015 from issue Using HD tree branch for encryption with Curve25519? by christianlundkvist

apoelstra force-pushed on Jan 14, 2016

apoelstra commented at 7:23 PM on January 14, 2016: contributor

Rebased and cleaned up. I think this is ready for review.

There aren't any exhaustive tests for modules yet.

sipa commented at 11:38 PM on January 23, 2016: contributor

Travis's on fire, yo.

apoelstra force-pushed on Jul 7, 2016

apoelstra commented at 11:09 AM on July 7, 2016: contributor

Rebased and completed verification

apoelstra force-pushed on Jul 7, 2016

apoelstra commented at 11:55 AM on July 7, 2016: contributor

Updated to just disable static precomputation for tests_exhaustive.c instead of whining to the user about her ./configure options.

in src/ecdsa_impl.h:None in addceb17fd outdated

 202 | @@ -203,7 +203,9 @@ static int secp256k1_ecdsa_sig_serialize(unsigned char *sig, size_t *size, const
 203 |  static int secp256k1_ecdsa_sig_verify(const secp256k1_ecmult_context *ctx, const secp256k1_scalar *sigr, const secp256k1_scalar *sigs, const secp256k1_ge *pubkey, const secp256k1_scalar *message) {
 204 |      unsigned char c[32];
 205 |      secp256k1_scalar sn, u1, u2;
 206 | +#if !defined(EXHAUSTIVE_TEST_ORDER)

sipa commented at 3:09 PM on July 7, 2016:

ifndef ?

apoelstra commented at 3:16 PM on July 7, 2016:

We're inconsistent about this throughout the code. Unless you feel strongly about this I'm not going to change it .. we can do a cleanup pass at some point in the future.

sipa commented at 3:17 PM on July 7, 2016:

OKAY

in src/scalar_low.h:None in addceb17fd outdated

   0 | @@ -0,0 +1,17 @@
   1 | +/**********************************************************************
   2 | + * Copyright (c) 2014 Pieter Wuille                                   *

sipa commented at 3:13 PM on July 7, 2016:

I can't remember writing this code!

in src/scalar_low.h:None in addceb17fd outdated

  10 | +#include <stdint.h>
  11 | +
  12 | +/** A scalar modulo the group order of the secp256k1 curve. */
  13 | +typedef uint32_t secp256k1_scalar;
  14 | +
  15 | +#define SECP256K1_SCALAR_CONST(d7, d6, d5, d4, d3, d2, d1, d0) ((uint32_t)(d0))

sipa commented at 3:14 PM on July 7, 2016:

Is this called anywhere? If it's needed, maybe it's better to have a SECP256K1_SCALAR_CONST_SMALL instead that just takes a single uint32_t, and in the non-low case call the normal one?

in src/ecmult_const_impl.h:None in addceb17fd outdated

  77 | @@ -78,7 +78,7 @@ static int secp256k1_wnaf_const(int *wnaf, secp256k1_scalar s, int w) {
  78 |      /* Negative numbers will be negated to keep their bit representation below the maximum width */
  79 |      flip = secp256k1_scalar_is_high(&s);
  80 |      /* We add 1 to even numbers, 2 to odd ones, noting that negation flips parity */
  81 | -    bit = flip ^ (s.d[0] & 1);
  82 | +    bit = flip ^ !secp256k1_scalar_is_even(&s);

sipa commented at 3:17 PM on July 7, 2016:

Good. Layer violation prevented.

in src/scalar_low_impl.h:None in addceb17fd outdated

  17 | +
  18 | +SECP256K1_INLINE static void secp256k1_scalar_clear(secp256k1_scalar *r) { *r = 0; }
  19 | +SECP256K1_INLINE static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v) { *r = v; }
  20 | +
  21 | +SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits(const secp256k1_scalar *a, unsigned int offset, unsigned int count) {
  22 | +    if (offset < 32)

sipa commented at 3:20 PM on July 7, 2016:

Either the if/else is unnecessary, or the (offset < 32) * is.

apoelstra commented at 5:34 AM on November 18, 2016:

I don't recall the context here, but the offending (offset < 32) * has been removed. This was the result of an in-person discussion.

in src/scalar_low_impl.h:None in addceb17fd outdated

  25 | +        return 0;
  26 | +}
  27 | +
  28 | +SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count) {
  29 | +    if (offset < 32)
  30 | +        return (offset < 32) * ((*a >> offset) & ((((uint32_t)1) << count) - 1));

sipa commented at 3:21 PM on July 7, 2016:

Same here.

apoelstra force-pushed on Jul 8, 2016

apoelstra force-pushed on Jul 9, 2016

apoelstra commented at 8:06 AM on July 9, 2016: contributor

Updated to force-disable the endomorphism optimization for the exhaustive tests, since the scalar_low impl it uses does not support it.

apoelstra force-pushed on Jul 9, 2016

apoelstra commented at 11:30 AM on July 9, 2016: contributor

Updated again to put endomorphism support back and just implement SECP256K1_SCALAR_CONST, which was the point of incompatibility. Turns out the Schnorr module also needs this macro.

sipa commented at 11:40 AM on July 9, 2016: contributor

Hmm, how can the endomorphism work without changing the lambda constant? (a cubic root of 1 mod the curve order)

apoelstra commented at 11:41 AM on July 9, 2016: contributor

@sipa it observably does .. I have not checked into why but my belief is that it always splits n into n + 0*lambda for such small n.

Edit: Yes, this is what's happening.

apoelstra force-pushed on Nov 18, 2016

Add exhaustive test for group functions on a low-order subgroup

We observe that when changing the b-value in the elliptic curve formula
`y^2 = x^3 + ax + b`, the group law is unchanged. Therefore our functions
for secp256k1 will be correct if and only if they are correct when applied
to the curve defined by `y^2 = x^3 + 4` defined over the same field. This
curve has a point P of order 199.

This commit adds a test which computes the subgroup generated by P and
exhaustively checks that addition of every pair of points gives the correct
result.

Unfortunately we cannot test const-time scalar multiplication by the same
mechanism. The reason is that these ecmult functions both compute a wNAF
representation of the scalar, and this representation is tied to the order
of the group.

Testing with the incomplete version of gej_add_ge (found in 5de4c5dff^)
shows that this detects the incompleteness when adding P - 106P, which
is exactly what we expected since 106 is a cube root of 1 mod 199.

20b8877be1

apoelstra force-pushed on Nov 25, 2016

apoelstra force-pushed on Nov 26, 2016

in src/scalar_low_impl.h:None in ac59807342 outdated

  23 | +        return ((*a >> offset) & ((((uint32_t)1) << count) - 1));
  24 | +    else
  25 | +        return 0;
  26 | +}
  27 | +
  28 | +SECP256K1_INLINE static unsigned int secp256k1_scalar_get_bits_var(const secp256k1_scalar *a, unsigned int offset, unsigned int count) {

sipa commented at 12:03 AM on November 26, 2016:

Does this need a separate implementation from secp256k1_scalar_get_bits? It could just call the other function, or even be #defined to be identical.

sipa commented at 12:27 AM on November 26, 2016:

Fixed.

in src/scalar_impl.h:None in ac59807342 outdated

 288 | + * nontrivial to get full test coverage for the exhaustive tests. We therefore
 289 | + * (arbitrarily) set k2 = k + 5 and k1 = k - k2 * lambda.
 290 | + */
 291 | +static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a) {
 292 | +    *r2 = (*a + 5) % EXHAUSTIVE_TEST_ORDER;
 293 | +    *r1 = (10000 * EXHAUSTIVE_TEST_ORDER + *a - *r2 * EXHAUSTIVE_TEST_LAMBDA) % EXHAUSTIVE_TEST_ORDER;

sipa commented at 12:06 AM on November 26, 2016:

I think this can be written as r1 = (*a + (EXHAUSTIVE_TEST_ORDER - *r2) * EXHAUSTIVE_TEST_LAMBDA) % EXHAUSTIVE_TEST_ORDER;, avoiding the weird constant.

in src/scalar_low_impl.h:None in ac59807342 outdated

  30 | +        return ((*a >> offset) & ((((uint32_t)1) << count) - 1));
  31 | +    else
  32 | +        return 0;
  33 | +}
  34 | +
  35 | +SECP256K1_INLINE static int secp256k1_scalar_check_overflow(const secp256k1_scalar *a) { return *a > EXHAUSTIVE_TEST_ORDER; }

sipa commented at 12:07 AM on November 26, 2016:

>= ?

in src/scalar_low_impl.h:None in ac59807342 outdated

  67 | +    return *a == 0;
  68 | +}
  69 | +
  70 | +static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a) {
  71 | +    *r = EXHAUSTIVE_TEST_ORDER - *a;
  72 | +    *r %= EXHAUSTIVE_TEST_ORDER;

sipa commented at 12:08 AM on November 26, 2016:

Faster: if (*a) { *r = EXHAUSTIVE_TEST_ORDER - *a; } else { *r = 0; }.

in src/tests_exhaustive.c:None in ac59807342 outdated

 199 | +    secp256k1_fe_normalize(&x);
 200 | +    secp256k1_fe_get_b32(x_bin, &x);
 201 | +    secp256k1_scalar_set_b32(r, x_bin, NULL);
 202 | +}
 203 | +
 204 | +/* hee hee hee */

sipa commented at 12:09 AM on November 26, 2016:

LOL

in src/tests_exhaustive.c:None in ac59807342 outdated

 212 | +        }
 213 | +    }
 214 | +    return -1;
 215 | +}
 216 | +
 217 | +void test_exhaustive_sign(const secp256k1_context *ctx, const secp256k1_ge *group, int order) {

sipa commented at 12:11 AM on November 26, 2016:

Is there a use in passing order as a parameter? Almost all of this code already depends on knowing it is equal to EXHAUSTIVE_TEST_ORDER anyway.

apoelstra force-pushed on Nov 26, 2016

in src/scalar_impl.h:None in 02b4ba36b8 outdated

 288 | + * nontrivial to get full test coverage for the exhaustive tests. We therefore
 289 | + * (arbitrarily) set k2 = k + 5 and k1 = k - k2 * lambda.
 290 | + */
 291 | +static void secp256k1_scalar_split_lambda(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *a) {
 292 | +    *r2 = (*a + 5) % EXHAUSTIVE_TEST_ORDER;
 293 | +    *r1 = (*a + (EXHAUSTIVE_TEST_ORDER - *r2) * EXHAUSTIVE_TEST_LAMBDA) % EXHAUSTIVE_TEST_ORDER;;;;

sipa commented at 12:27 AM on November 26, 2016:

;;;;?

Add exhaustive tests for group arithmetic, signing, and ecmult on a small group

If you compile without ./configure --enable-exhaustive-tests=no,
this will create a binary ./exhaustive_tests which will execute
every function possible on a group of small order obtained by
moving to a twist of our curve and locating a generator of small
order.

Currently defaults to order 13, though by changing some #ifdefs
you can get a couple other ones. (Currently 199, which will take
forever to run, and 14, which won't work because it's composite.)

TODO exhaustive tests for the various modules

83836a9547

Add exhaustive test for verification b4ceedf14f

apoelstra force-pushed on Nov 26, 2016

sipa commented at 12:48 AM on November 26, 2016: contributor

ACK

sipa merged this on Nov 26, 2016

sipa closed this on Nov 26, 2016

sipa referenced this in commit a8abae7e5f on Nov 26, 2016

sipa cross-referenced this on Nov 28, 2016 from issue Small subgroup alternative curve verification of group law by gmaxwell