Repository: bitcoin-core/secp256k1
Pull request #568 (2018-10-24 18:04:22)

Fix integer overflow in ecmult_multi_var when n is large
Without this PR ecmult_multi could return wrong results. If the number of points `n` is large enough then some or all multiplications could be skipped or the function could end up in an infinite loop. This PR adds two checks to prevent `n` from wrapping around.

apoelstra: ACK
real-or-random: Oh I didn't want to bother you with nits only. I assumed that the missing parentheses are real bugs but no, we deal with unsigned integers. :)
ACK
jonasnick: Replaced `(size_t)-1` with `MAX_SIZE`
gmaxwell: ACK
jimpo: This seems fine, though you could also avoid the overflow checks entirely with

```c
n_batches = 1 + (n-1)/max_points;
n_batch_points = 1 + (n-1)/n_batches;
```

This should work in all cases since `n` is guaranteed to be `> 0`.
jonasnick: I rewrote this PR with @jimpo's suggestion. I think this is better because the previous code was complex enough that we missed a potential bug [0] and the new code doesn't have unnecessary return 0's. Because `n = SIZE_MAX` is now actually possible of  I had to rewrite the tests to directly test the batch_size_helper.

[0] `if (n_batches == 0 || n > SIZE_MAX - (*n_batches-1)) {` (first asterisk missing)
real-or-random: ACK
jimpo: utACK
laanwj: utACK c37e53d12b57a9f3ff248f1f0664872500cfd165, changes look correct to me
gmaxwell: The addition of the trivial ecmult_multi algorithm in pr580 unfortunately created a trivial merge conflict for this PR, sorry about that. I am ACK on the PR, but need the rebase.
gmaxwell: If you'd prefer I can make a fixup commit, whatever you'd be happiest with.

Patch:
diff --git a/src/ecmult_impl.h b/src/ecmult_impl.h
index 7c37821..cbafd07 100644
--- a/src/ecmult_impl.h
+++ b/src/ecmult_impl.h
@@ -1111,12 +1111,31 @@ static int secp256k1_ecmult_multi_simple_var(const secp256k1_ecmult_context *ctx
     return 1;
 }
 
+/* Compute the number of batches and the batch size given the maximum batch size and the
+ * total number of points */
+static int secp256k1_ecmult_multi_batch_size_helper(size_t *n_batches, size_t *n_batch_points, size_t max_n_batch_points, size_t n) {
+    if (max_n_batch_points == 0) {
+        return 0;
+    }
+    if (max_n_batch_points > ECMULT_MAX_POINTS_PER_BATCH) {
+        max_n_batch_points = ECMULT_MAX_POINTS_PER_BATCH;
+    }
+    if (n == 0) {
+        *n_batches = 0;
+        *n_batch_points = 0;
+        return 1;
+    }
+    /* Compute ceil(n/max_n_batch_points) and ceil(n/n_batches) */
+    *n_batches = 1 + (n - 1) / max_n_batch_points;
+    *n_batch_points = 1 + (n - 1) / *n_batches;
+    return 1;
+}
+
 typedef int (*secp256k1_ecmult_multi_func)(const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t);
 static int secp256k1_ecmult_multi_var(const secp256k1_ecmult_context *ctx, secp256k1_scratch *scratch, secp256k1_gej *r, const secp256k1_scalar *inp_g_sc, secp256k1_ecmult_multi_callback cb, void *cbdata, size_t n) {
     size_t i;
 
     int (*f)(const secp256k1_ecmult_context*, secp256k1_scratch*, secp256k1_gej*, const secp256k1_scalar*, secp256k1_ecmult_multi_callback cb, void*, size_t, size_t);
-    size_t max_points;
     size_t n_batches;
     size_t n_batch_points;
 
@@ -1133,24 +1152,17 @@ static int secp256k1_ecmult_multi_var(const secp256k1_ecmult_context *ctx, secp2
         return secp256k1_ecmult_multi_simple_var(ctx, r, inp_g_sc, cb, cbdata, n);
     }
 
-    max_points = secp256k1_pippenger_max_points(scratch);
-    if (max_points == 0) {
+    /* Compute the batch sizes for pippenger given a scratch space. If it's greater than a threshold
+     * use pippenger. Otherwise use strauss */
+    if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_pippenger_max_points(scratch), n)) {
         return 0;
-    } else if (max_points > ECMULT_MAX_POINTS_PER_BATCH) {
-        max_points = ECMULT_MAX_POINTS_PER_BATCH;
     }
-    n_batches = (n+max_points-1)/max_points;
-    n_batch_points = (n+n_batches-1)/n_batches;
-
     if (n_batch_points >= ECMULT_PIPPENGER_THRESHOLD) {
         f = secp256k1_ecmult_pippenger_batch;
     } else {
-        max_points = secp256k1_strauss_max_points(scratch);
-        if (max_points == 0) {
+        if (!secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, secp256k1_strauss_max_points(scratch), n)) {
             return 0;
         }
-        n_batches = (n+max_points-1)/max_points;
-        n_batch_points = (n+n_batches-1)/n_batches;
         f = secp256k1_ecmult_strauss_batch;
     }
     for(i = 0; i < n_batches; i++) {


Test patch:
diff --git a/src/tests.c b/src/tests.c
index 224ddc6..f1c4db9 100644
--- a/src/tests.c
+++ b/src/tests.c
@@ -2854,6 +2854,50 @@ void test_ecmult_multi_pippenger_max_points(void) {
     CHECK(bucket_window == PIPPENGER_MAX_BUCKET_WINDOW);
 }
 
+void test_ecmult_multi_batch_size_helper(void) {
+    size_t n_batches, n_batch_points, max_n_batch_points, n;
+
+    max_n_batch_points = 0;
+    n = 1;
+    CHECK(secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, max_n_batch_points, n) == 0);
+
+    max_n_batch_points = 1;
+    n = 0;
+    CHECK(secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, max_n_batch_points, n) == 1);
+    CHECK(n_batches == 0);
+    CHECK(n_batch_points == 0);
+
+    max_n_batch_points = 2;
+    n = 5;
+    CHECK(secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, max_n_batch_points, n) == 1);
+    CHECK(n_batches == 3);
+    CHECK(n_batch_points == 2);
+
+    max_n_batch_points = ECMULT_MAX_POINTS_PER_BATCH;
+    n = ECMULT_MAX_POINTS_PER_BATCH;
+    CHECK(secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, max_n_batch_points, n) == 1);
+    CHECK(n_batches == 1);
+    CHECK(n_batch_points == ECMULT_MAX_POINTS_PER_BATCH);
+
+    max_n_batch_points = ECMULT_MAX_POINTS_PER_BATCH + 1;
+    n = ECMULT_MAX_POINTS_PER_BATCH + 1;
+    CHECK(secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, max_n_batch_points, n) == 1);
+    CHECK(n_batches == 2);
+    CHECK(n_batch_points == ECMULT_MAX_POINTS_PER_BATCH/2 + 1);
+
+    max_n_batch_points = 1;
+    n = SIZE_MAX;
+    CHECK(secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, max_n_batch_points, n) == 1);
+    CHECK(n_batches == SIZE_MAX);
+    CHECK(n_batch_points == 1);
+
+    max_n_batch_points = 2;
+    n = SIZE_MAX;
+    CHECK(secp256k1_ecmult_multi_batch_size_helper(&n_batches, &n_batch_points, max_n_batch_points, n) == 1);
+    CHECK(n_batches == SIZE_MAX/2 + 1);
+    CHECK(n_batch_points == 2);
+}
+
 /**
  * Run secp256k1_ecmult_multi_var with num points and a scratch space restricted to
  * 1 <= i <= num points.
@@ -2936,6 +2980,7 @@ void run_ecmult_multi_tests(void) {
     test_ecmult_multi(scratch, secp256k1_ecmult_multi_var);
     secp256k1_scratch_destroy(scratch);
 
+    test_ecmult_multi_batch_size_helper();
     test_ecmult_multi_batching();
 }