Prevent ints from wrapping around in scratch space functions #648

jonasnick commented at 10:08 AM on July 12, 2019: contributor

This PR increases the general robustness of scratch spaces. It does not fix an existing vulnerability because scratch spaces aren't used anywhere in master. Additionally, it must be prevented anyway that an attacker has (indirect) control over the arguments touched in this PR.

in src/scratch_impl.h:64 in 670cffe46b outdated

  59 | @@ -60,6 +60,10 @@ static size_t secp256k1_scratch_max_allocation(const secp256k1_callback* error_c
  60 |          secp256k1_callback_call(error_callback, "invalid scratch space");
  61 |          return 0;
  62 |      }
  63 | +    /* Ensure that multiplication will not wrap around */
  64 | +    if (objects > SIZE_MAX/(ALIGNMENT - 1)) {

real-or-random commented at 12:28 PM on July 12, 2019:

ALIGNMENT == 1 should be handled.

jonasnick commented at 1:21 PM on July 12, 2019:

I don't think that's necessary but I can fix it. Any suggestion for how to handle it? Is a VERIFY_CHECK enough?

real-or-random commented at 1:36 PM on July 12, 2019:

Yeah, I don't know either how big of a problem it is. But it's not impossible. I can imagine that someone defines ALIGNMENT == 1 because, e.g., on x86, unaligned access is not an issue.

I think we should either

#error out at compile-time (better than with at runtime VERIFY_CHECK)
or just handle it. An if (ALIGNMENT == 1) can anyway be optimized out then by the compiler.

jonasnick commented at 3:49 PM on July 29, 2019:

Added commit to handle that at runtime now.

in src/tests.c:408 in 670cffe46b outdated

 399 | @@ -400,6 +400,15 @@ void run_scratch_tests(void) {
 400 |      secp256k1_scratch_space_destroy(none, scratch);
 401 |      CHECK(ecount == 5);
 402 |  
 403 | +    /* Test that large integers do not wrap around in a bad way */
 404 | +    scratch = secp256k1_scratch_space_create(none, 1000);
 405 | +    /* try max allocation with a large number of objects */
 406 | +    CHECK(!secp256k1_scratch_max_allocation(&none->error_callback, scratch, (SIZE_MAX / (ALIGNMENT - 1)) + 1));
 407 | +    /* try allocating SIZE_MAX */
 408 | +    CHECK(ROUND_TO_ALIGN(SIZE_MAX) == 0);

real-or-random commented at 12:30 PM on July 12, 2019:

Couldn't ROUND_TO_ALIGN(SIZE_MAX) == SIZE_MAX be correct on some platforms?

jonasnick commented at 1:18 PM on July 12, 2019:

On which platforms?

real-or-random commented at 1:26 PM on July 12, 2019:

Judging from the definition of ROUND_TO_ALIGN, I think this happens if and only if ALIGNMENT == 1.

jonasnick commented at 3:49 PM on July 29, 2019:

removed line and added comment

real-or-random commented at 12:34 PM on July 12, 2019: contributor

Approach ACK

real-or-random commented at 12:44 PM on July 30, 2019: contributor

If you want, you can cherry-pick https://github.com/real-or-random/secp256k1/commit/00076ab2347104f8ab6d88b8aa08865d0b3fd93b; this does not need a separate PR.

in src/tests.c:406 in 6a0fc27080 outdated

 399 | @@ -400,6 +400,16 @@ void run_scratch_tests(void) {
 400 |      secp256k1_scratch_space_destroy(none, scratch);
 401 |      CHECK(ecount == 5);
 402 |  
 403 | +    /* Test that large integers do not wrap around in a bad way */
 404 | +    scratch = secp256k1_scratch_space_create(none, 1000);
 405 | +    /* try max allocation with a large number of objects */
 406 | +    CHECK(!secp256k1_scratch_max_allocation(&none->error_callback, scratch, (SIZE_MAX / (ALIGNMENT - 1)) + 1));

real-or-random commented at 12:47 PM on July 30, 2019:

ALIGNMENT could be 1 here too, yielding UB the tests.

jonasnick commented at 3:51 PM on July 30, 2019:

fixed

real-or-random commented at 12:48 PM on July 30, 2019: contributor

ACK except nits, I read the code in detail

jonasnick force-pushed on Jul 30, 2019

jonasnick commented at 3:52 PM on July 30, 2019: contributor

Squashed fixups and cherry-picked @real-or-random's commit such that tests pass now even with #define ALIGNMENT 1

jonasnick force-pushed on Jul 30, 2019

Add check preventing integer multiplication wrapping around in scratch_max_allocation 4edaf06fb0

Add check preventing rounding to alignment from wrapping around in scratch_alloc 8ecc6ce50e

Use ROUND_TO_ALIGN in scratch_create ada6361dec

Don't assume that ALIGNMENT > 1 in tests 60f7f2de5d

real-or-random commented at 11:37 PM on July 30, 2019: contributor

ACK I have read the code and tested it, also using valgrind, both with and without ALIGNMENT=1

(Travis is failing but just in the Java builds and this is some unrelated issue with a missing java package.)

real-or-random requested review from sipa on Mar 26, 2020

real-or-random removed review request from sipa on Mar 26, 2020

real-or-random requested review from apoelstra on Mar 26, 2020

gmaxwell commented at 5:09 PM on August 22, 2020: contributor

Shouldn't the objects count be clamped rather than just failing? E.g. using this approach on a 16bit platform just makes a lot of the batch stuff not work (compared to an alternative change which clamps the object count).

jonasnick commented at 9:32 AM on August 23, 2020: contributor

I think the expectation is that after a successful scratch_create call, the size of the scratch space is close to whatever the user specified. Why does the batch stuff not work on 16 bit platforms? Can't you just create a smaller scratch space?

gmaxwell commented at 10:28 AM on August 23, 2020: contributor

E.g. #define ECMULT_MAX_POINTS_PER_BATCH 5000000 / #define ECMULT_MAX_POINTS_PER_BATCH 10000000 -- these constants don't fit in int.

(I haven't gotten around to fixing scratch/batch on 16-bit so I dunno the full scope yet; there are some other issues, mostly in the test outside of batch-- but I have the rest of the codebase working on 16-bit right now)

But ignore my question, I had forgot how the interface worked and was momentarily confused into thinking that the user asked for a number of points in the batch and thought they were going to have to bisection search the API or something. Sorry. :)

real-or-random commented at 10:33 AM on August 23, 2020: contributor

@apoelstra Can you review this?

jonasnick commented at 12:52 PM on August 23, 2020: contributor

E.g. #define ECMULT_MAX_POINTS_PER_BATCH 5000000 / #define ECMULT_MAX_POINTS_PER_BATCH 10000000 -- these constants don't fit in int.

Oh, I see. Fwiw, those constants don't have a deep meaning. The idea was just to artificially restrict the number of points processed in a single batch to allow testing all possible batch sizes.

gmaxwell commented at 9:23 PM on August 29, 2020: contributor

ACK

sipa commented at 10:23 PM on September 1, 2020: contributor

ACK 60f7f2de5de917c2bee32a4cd79cc3818b6a94a0

real-or-random removed review request from apoelstra on Sep 1, 2020

real-or-random merged this on Sep 2, 2020

real-or-random closed this on Sep 2, 2020

jasonbcox referenced this in commit ec5ca0931f on Sep 28, 2020

deadalnix referenced this in commit aa004f43cd on Sep 29, 2020