Prevent arithmetic on NULL pointer if the scratch space is too small

Fabcien commented at 11:38 am on October 26, 2020: contributor

If the scratch space is too small when calling secp256k1_ecmult_strauss_batch(), the state.pre_a allocation will fail and the pointer will be NULL. This causes state.pre_a_lam to be computed from the NULL pointer.

It is also possible that the first allocation to fail is for state.ps, which will cause the failure to occur when in secp256k1_ecmult_strauss_wnaf().

The issue has been detected by UBSAN using Clang 10:

0CC=clang \
1CFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" \
2LDFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" \
3../configure
4
5UBSAN_OPTIONS=print_stacktrace=1:halt_on_error=1 make check

real-or-random commented at 12:13 pm on October 26, 2020: contributor

Thanks for the PR!

Before I have to time a real reply, let me note for anyone reading here that this is not something to worry about because scratch spaces are used nowhere in the public API currently. This is dead code used for future extensions.

in src/ecmult_impl.h:601 in 7efe94247c outdated

595@@ -596,14 +596,15 @@ static int secp256k1_ecmult_strauss_batch(const secp256k1_callback* error_callba
596     state.prej = (secp256k1_gej*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_gej));
597     state.zr = (secp256k1_fe*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_fe));
598     state.pre_a = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * 2 * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
599-    state.pre_a_lam = state.pre_a + n_points * ECMULT_TABLE_SIZE(WINDOW_A);
600     state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(struct secp256k1_strauss_point_state));
601 
602-    if (points == NULL || scalars == NULL || state.prej == NULL || state.zr == NULL || state.pre_a == NULL) {
603+    if (points == NULL || scalars == NULL || state.prej == NULL || state.zr == NULL || state.pre_a == NULL || state.ps == NULL) {

real-or-random commented at 12:33 pm on October 26, 2020:

Crazy that we missed this in #600.

nit: Maybe it will be better to call secp256k1_scratch_alloc also for state.pre_a_lam. This will be more consistent. I think the current code was good when we still had the endo ifdefs but it’s no longer natural now that we removed these. But I don’t have strong opinions on this. The version after the PR here is correct but invites doing NULL pointer arithmetic..

in .travis.yml:34 in 7efe94247c outdated

30@@ -31,6 +31,7 @@ env:
31     - BUILD=distcheck WITH_VALGRIND=no CTIMETEST=no BENCH=no
32     - CPPFLAGS=-DDETERMINISTIC
33     - CFLAGS=-O0 CTIMETEST=no
34+    - CFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" LDFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" UBSAN_OPTIONS="print_stacktrace=1:halt_on_error=1" CTIMETEST=no

real-or-random commented at 12:37 pm on October 26, 2020:

I think this should go to a different PR (if we want this at all). Not sure how long this takes on Travis, and it may not run on the GCC version on Travis etc.

Fabcien commented at 3:22 pm on October 26, 2020:

Here is the result on Travis: https://travis-ci.org/github/Fabcien/secp256k1-1/builds/738981454 UBSAN has a low overhead so the duration is only slightly impacted.

real-or-random commented at 12:37 pm on October 26, 2020: contributor

Concept ACK

real-or-random cross-referenced this on Oct 26, 2020 from issue gcc emits -Warray-bounds warnings by hebasto

Fabcien force-pushed on Oct 26, 2020

Fabcien commented at 4:05 pm on October 26, 2020: contributor

@real-or-random Now calling secp256k1_scratch_alloc for state.pre_a_lam. Let me know if you still want me to move the Travis change to its own PR. I personally prefer to keep the changes and the tests together.

real-or-random commented at 4:58 pm on October 26, 2020: contributor

I’m ok with adding it here (can’t speak for the others) but I think then it should look more like this line then (enable all the stuff) BIGNUM=no ASM=x86_64 ECDH=yes RECOVERY=yes EXPERIMENTAL=yes SCHNORRSIG=yes

And should we add print_summary=1? By the way, I can’t find official docs on UBSAN_OPTIONS. Do you have a good resource?

Fabcien commented at 8:21 pm on October 26, 2020: contributor

The best resource I could find is the documentation from LLVM. The GCC documentation explains the halt_on_error behavior. I didn’t know the print_summary option but it seems to be useless with halt_on_error=1, which needs to be set for the build to fail if UBSAN finds an issue.

Fabcien force-pushed on Oct 26, 2020

sipa commented at 2:53 am on October 27, 2020: contributor

Concept ACK.

I think CI tests with -fsanitize=undefined is a good idea in any case. Can you do that in a separate commit though? It’s an unrelated change.

Prevent arithmetic on NULL pointer if the scratch space is too small

If the scratch space is too small when calling
`secp256k1_ecmult_strauss_batch()`, the `state.pre_a` allocation will
fail and the pointer will be `NULL`. This causes `state.pre_a_lam` to be
computed from the `NULL` pointer.

It is also possible that the first allocation to fail is for `state.ps`,
which will cause the failure to occur when in
`secp256k1_ecmult_strauss_wnaf()`.

The issue has been detected by UBSAN using Clang 10:
```
CC=clang \
CFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" \
LDFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" \
../configure

UBSAN_OPTIONS=print_stacktrace=1:halt_on_error=1 make check
```

7506e064d7

Run the undefined behaviour sanitizer on Travis

Run UBSAN with both GCC and Clang, on Linux and macOS.
The `halt_on_error=1` option is required to make the build fail if the
sanitizer finds an issue.

29a299e373

Fabcien force-pushed on Oct 27, 2020

Fabcien commented at 7:55 am on October 27, 2020: contributor

@sipa Sure, done.

sipa commented at 6:50 pm on October 27, 2020: contributor

ACK 29a299e373d5f0e326be74c514c7c70ddf50cce1. Reviewed the code changes and verified that building with these sanitizer flags catches the existing error, as well as a signed integer overflow if introduced.

sipa commented at 4:51 pm on October 28, 2020: contributor

There is an issue with Travis’ s390x build, which I’ve cancelled. CI succeeded for all other builds.

real-or-random commented at 3:51 pm on October 30, 2020: contributor

ACK 29a299e373d5f0e326be74c514c7c70ddf50cce1 code inspection

real-or-random approved

jonasnick approved

jonasnick commented at 2:49 pm on November 4, 2020: contributor

utACK 29a299e373d5f0e326be74c514c7c70ddf50cce1

jonasnick merged this on Nov 4, 2020

jonasnick closed this on Nov 4, 2020

real-or-random cross-referenced this on Nov 4, 2020 from issue General CI discussion by real-or-random

jasonbcox referenced this in commit fb908c83a6 on Nov 4, 2020

deadalnix referenced this in commit 533268ef26 on Nov 5, 2020

Prevent arithmetic on NULL pointer if the scratch space is too small #839