NCC-2016-003 - Conversion to ‘std::size_t’ from ‘long int’

[rcseacord]

the loop interator i should be declared as size_t in three locations:

src/algebra/curves/alt_bn128/alt_bn128_pairing.cpp:327:38: warning: conversion to ‘long int’ from ‘size_t {aka long unsigned int}’ may change the sign of the result [-Wsign-conversion]
     for (long i = loop_count.max_bits(); i >= 0; --i)
                   ~~~~~~~~~~~~~~~~~~~^~
src/algebra/curves/alt_bn128/alt_bn128_pairing.cpp:329:47: warning: conversion to ‘std::size_t {aka long unsigned int}’ from ‘long int’ may change the sign of the result [-Wsign-conversion]
         const bool bit = loop_count.test_bit(i);
                                               ^
src/algebra/curves/alt_bn128/alt_bn128_pairing.cpp: In function ‘libsnark::alt_bn128_Fq12 libsnark::alt_bn128_ate_miller_loop(const libsnark::alt_bn128_ate_G1_precomp&, const libsnark::alt_bn128_ate_G2_precomp&)’:
src/algebra/curves/alt_bn128/alt_bn128_pairing.cpp:381:38: warning: conversion to ‘long int’ from ‘size_t {aka long unsigned int}’ may change the sign of the result [-Wsign-conversion]
     for (long i = loop_count.max_bits(); i >= 0; --i)
                   ~~~~~~~~~~~~~~~~~~~^~
src/algebra/curves/alt_bn128/alt_bn128_pairing.cpp:383:47: warning: conversion to ‘std::size_t {aka long unsigned int}’ from ‘long int’ may change the sign of the result [-Wsign-conversion]
         const bool bit = loop_count.test_bit(i);
                                               ^
src/algebra/curves/alt_bn128/alt_bn128_pairing.cpp: In function ‘libsnark::alt_bn128_Fq12 libsnark::alt_bn128_ate_double_miller_loop(const libsnark::alt_bn128_ate_G1_precomp&, const libsnark::alt_bn128_ate_G2_precomp&, const libsnark::alt_bn128_ate_G1_precomp&, const libsnark::alt_bn128_ate_G2_precomp&)’:
src/algebra/curves/alt_bn128/alt_bn128_pairing.cpp:435:38: warning: conversion to ‘long int’ from ‘size_t {aka long unsigned int}’ may change the sign of the result [-Wsign-conversion]
     for (long i = loop_count.max_bits(); i >= 0; --i)
                   ~~~~~~~~~~~~~~~~~~~^~
src/algebra/curves/alt_bn128/alt_bn128_pairing.cpp:437:47: warning: conversion to ‘std::size_t {aka long unsigned int}’ from ‘long int’ may change the sign of the result [-Wsign-conversion]
         const bool bit = loop_count.test_bit(i);

Repair in 3 locations:

-    for (long i = loop_count.max_bits(); i >= 0; --i)
+    for (size_t i = loop_count.max_bits(); i >= std:size_t{0}; --i)

Similar problems:

src/algebra/fields/field_utils.tcc:175:29: warning: conversion to ‘long int’ from ‘std::vector<libsnark::Fp2_model<4l, ((const libsnark::bigint<4l>&)(& libsnark::alt_bn128_modulus_q))> >::size_type {aka long unsigned int}’ may change the sign of the result [-Wsign-conversion]
     for (long i = vec.size()-1; i >= 0; --i)

src/algebra/fields/field_utils.tcc:177:34: warning: conversion to ‘std::vector<libsnark::Fp2_model<4l, ((const libsnark::bigint<4l>&)(& libsnark::alt_bn128_modulus_q))> >::size_type {aka long unsigned int}’ from ‘long int’ may change the sign of the result [-Wsign-conversion]
         const FieldT old_el = vec[i];
                               ~~~^
src/algebra/fields/field_utils.tcc:178:12: warning: conversion to ‘std::vector<libsnark::Fp2_model<4l, ((const libsnark::bigint<4l>&)(& libsnark::alt_bn128_modulus_q))> >::size_type {aka long unsigned int}’ from ‘long int’ may change the sign of the result [-Wsign-conversion]
         vec[i] = acc_inverse * prod[i];
         ~~~^
src/algebra/fields/field_utils.tcc:178:36: warning: conversion to ‘std::vector<libsnark::Fp2_model<4l, ((const libsnark::bigint<4l>&)(& libsnark::alt_bn128_modulus_q))> >::size_type {aka long unsigned int}’ from ‘long int’ may change the sign of the result [-Wsign-conversion]
         vec[i] = acc_inverse * prod[i];
                                ~~~~^

Repair:

-   for (long i = vec.size()-1; i >= 0; --i)
+    for (size_t i = vec.size()-1; i >= size_t{0}; --i)

[nathan-at-least]

Is this a. either very easy, or b. notable risk of compromise (on any architecture)? If so, let's put it in the 1.0 target, otherwise, after 1.0.

paging @daira and @ebfull for their libsnark & security expertise here.

[coinspect]

Changing the type of a counter from signed to 'std::size_t' can introduce dangerous bugs or memory corruption vulnerabilities in some cases. For example the code above crashes if vec.size() is zero. Before changing the type, check if < 0 or while >= 0 is being used as a boundary check.

for (size_t i = vec.size()-1; i >= size_t{0}; --i) 

[ebfull]

None of these are exploitable, so we can bump this to 1.0.1. (We'll want to patch them upstream.)

[nathan-at-least]

@daira: Please review for exploitability. If you agree it's not an exposed attack surface, postpone this to 1.0.1.

[daira]

This is definitely not exploitable.

[daira]

Note that the proposed repair is wrong because size_t is unsigned, so will always be >= 0 even at the intended end of the loop.

[radix42]

Portability note: to get libsnark to work on a native (non-Cygwin) build on 64 bit Windows, in MANY places we had to change instances of size_t to int64_t (size_t is 32 bits wide on windows, always, as is long), and there are a few places in the zcash code itself where the same was true.

In libsnark issue 66 we're changing ALL integer types to C++11 types that have an explicit bit width that does not vary due to platform: banishing long, unsigned long and size_t (as myself and @joshuayabut have had to do to get libsnark and zcash working on Windows in the pruned subset of libsnark we forked from zcash/libsnark).

[tromer]

Why would you need to change size_t?

When long or unsigned long are used for data (e.g., limbs of bigints), it's clear why you need to fix the big length.

But size_t is supposed to be used for values which are array sizes, loop indices, byte counts and the like; it's not supposed to matter whether these are 32 bits or 64 bits (as long as they don't overflow).

[radix42]

yes I know its not SUPPOSED to matter, but here we are....I can revert one of the ones we had to change and paste how it blows up for you sometime, but I can assure you it is indeed the case (I'll do that at some point for libsnark 66 but I'm too tired right now to fuss with it)

[radix42]

Here's a spot in my Mac port where a similar change from size_t to uint64_t was needed where that change SHOULDN'T have been needed (@joshuayabut just recently figured out why):

#1800

See the code changes in the "Files" tab and the long error output you get when you revert just that change. The size_t changes needed for libsnark on windows do the same thing.

[radix42]

and yes its maddening and no its not supposed to do that

[tromer]

Ah. The code that actually uses size_t is fine, but conversion to other integer types, or matching against other integer types in overloading, are broken. Makes sense.

Still, it converting size_t to uint64_t loses painstakingly-tracked information about these values (the fact that they are sizes/indices rather than data). That's a shame.

If the size_t portability problems are indeed all compile/link problems (so can be reliably found), and there's a reasonable number of them (no more than a few dozen), then how about keeping the size_t and adding explicit casts to uint64_t where needed to resolve the errors?

[radix42]

that sounds reasonable...in one case in the Mac port @joshuayabut was able to revert one of the size_t->unit64_t changes that'd been made by fooling with where it was blowing up by adding an explicit template somewhere...I'd need to go digging through git logs to find what that was

[tromer]

FYI, @rcseacord of NCC submitted a libsnark pull request which changes long to size_t, assert to assert_except, and a few other things: scipr-lab/libsnark#53

It was NAKed for the reasons discussed in that PR's review comments (which partially overlap with the above, #2043 and scipr-lab/libsnark#64).