Fix integer overflow in ecmult_multi

jonasnick commented at 6:04 pm on October 24, 2018: contributor

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.

in src/ecmult_impl.h:987 in 040f58d809 outdated

982+    }
983+    /* Check overflow */
984+    if (n > (size_t)-1 - (max_points-1)) {
985+        return 0;
986+    }
987+    *n_batches = (n + max_points-1) / max_points;

real-or-random commented at 7:09 pm on October 24, 2018:

0    *n_batches = (n + (max_points-1)) / max_points;

you could also CHECK/VERIFY that *n_batches != 0 here. As I understand it, this can only happen if n == 0 and then this function won’t be called currently.

in src/ecmult_impl.h:992 in 040f58d809 outdated

987+    *n_batches = (n + max_points-1) / max_points;
988+    /* Check overflow */
989+    if (n > (size_t)-1 - (*n_batches-1)) {
990+        return 0;
991+    }
992+    *n_batch_points = (n + *n_batches-1) / *n_batches;

real-or-random commented at 7:09 pm on October 24, 2018:

0    *n_batch_points = (n + (*n_batches-1)) / *n_batches;

apoelstra commented at 7:34 pm on October 24, 2018: contributor

ACK

jonasnick commented at 9:23 pm on October 24, 2018: contributor

@real-or-random I added a commit

in src/ecmult_impl.h:980 in 486aebf6d3 outdated

971@@ -972,12 +972,32 @@ static size_t secp256k1_pippenger_max_points(secp256k1_scratch *scratch) {
972     return res;
973 }
974 
975+/* Compute the number and size of batches given the maximum number of points in a batch and the
976+ * total number of points */
977+static int secp256k1_ecmult_multi_batch_size_helper(size_t *n_batches, size_t *n_batch_points, size_t max_points, size_t n) {
978+    if (max_points == 0) {
979+        return 0;
980+    } else if (max_points > ECMULT_MAX_POINTS_PER_BATCH) {

dcousens commented at 10:21 pm on October 24, 2018:

unnecessary else?

jonasnick commented at 8:24 am on October 26, 2018:

indeed, thanks

real-or-random commented at 8:40 am on October 25, 2018: contributor

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 force-pushed on Oct 26, 2018

jonasnick commented at 8:27 am on October 26, 2018: contributor

Removed unnecessary else (h/t @dcousens) and squashed

in src/ecmult_impl.h:985 in 24908bed13 outdated

980+    }
981+    if (max_points > ECMULT_MAX_POINTS_PER_BATCH) {
982+        max_points = ECMULT_MAX_POINTS_PER_BATCH;
983+    }
984+    /* Check overflow */
985+    if (n > (size_t)-1 - (max_points-1)) {

gmaxwell commented at 0:12 am on October 27, 2018:

Unless we have a reason, I think we’d prefer to use stdint SIZE_MAX here. (and in all the other cases where the largest SIZE_T is required)

real-or-random commented at 9:38 am on October 27, 2018:

SIZE_MAX requires C99 as far as I remember.

gmaxwell commented at 0:16 am on October 28, 2018:

@real-or-random It is an stdint.h type, like uint32_t. The codebase uses stdint.h ( https://github.com/bitcoin-core/secp256k1/blob/master/src/util.h#L15) types everywhere. In practice every compiler someone would want to use has this header (even non C99 compilers), but if someone did have a compiler without it, they’d have to provide a compatibility header.

real-or-random commented at 3:15 pm on October 28, 2018:

Okay, I see. It’s equivalent but yes, SIZE_MAX is obviously much nicer to read. I was the one who suggested size_t(-1) to @jonasnick in the Schnorr signature PR: #558#pullrequestreview-165077679 Maybe that’s why @apoelstra used it in #557 too…

jonasnick force-pushed on Oct 30, 2018

jonasnick commented at 4:41 pm on October 30, 2018: contributor

Replaced (size_t)-1 with MAX_SIZE

gmaxwell commented at 5:14 pm on November 17, 2018: contributor

ACK

jimpo commented at 7:58 pm on November 27, 2018: none

This seems fine, though you could also avoid the overflow checks entirely with

0n_batches = 1 + (n-1)/max_points;
1n_batch_points = 1 + (n-1)/n_batches;

This should work in all cases since n is guaranteed to be > 0.

jonasnick force-pushed on Jan 15, 2019

jonasnick commented at 7:14 pm on January 15, 2019: contributor

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 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 commented at 9:20 am on January 16, 2019: contributor

ACK

jimpo commented at 8:47 pm on January 16, 2019: none

utACK

laanwj commented at 3:49 pm on February 21, 2019: member

utACK c37e53d12b57a9f3ff248f1f0664872500cfd165, changes look correct to me

gmaxwell commented at 7:29 pm on February 24, 2019: contributor

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 commented at 7:58 pm on February 24, 2019: contributor

If you’d prefer I can make a fixup commit, whatever you’d be happiest with.

jonasnick force-pushed on Feb 25, 2019

Fix integer overflow in ecmult_multi_var when n is large 2277af5ff0

gmaxwell merged this on Feb 25, 2019

gmaxwell closed this on Feb 25, 2019

gmaxwell referenced this in commit aa15154a48 on Feb 25, 2019

gmaxwell commented at 9:09 pm on February 25, 2019: contributor

ACK

real-or-random cross-referenced this on Apr 23, 2020 from issue Improve C89 compliance by real-or-random

Fix integer overflow in ecmult_multi_var when n is large #568