Fix integer overflow in ecmult_multi_var when n is large #568

pull jonasnick wants to merge 1 commits into bitcoin-core:master from jonasnick:fix-ecmult-multi-overflow changing 2 files +69 −12

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:

    *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:

    *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 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 12: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 12: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
```
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 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

Contributors

Linked (view graph)

#557 Eliminate scratch memory used when generating contexts #558 Add schnorrsig module which implements BIP-340 compliant signatures #746 Improve C89 compliance