search

scipr-lab / libsnark

C++ library for zkSNARKs
Other
1.83k stars 585 forks source link

stack-buffer-overflow in libsnark::SHA512_rng? #24

Closed ghost closed 7 years ago

ghost commented 8 years ago

Hi,

I'm currently digging through libsnark with ASan enabled, and I might have found a stack-buffer-overflow in libsnark::SHA512_rng triggered by various test-cases.

undefined behaviour:

src/common/rng.tcc:53:13: runtime error: load of address 0x7fd2a506d488 with insufficient space for an object of type 'mp_limb_t'
0x7fd2a506d488: note: pointer points here
 b9 54 ea a1  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00 00 00 00 00  00 00 00 00
              ^
=================================================================

stack-bo:

=================================================================
==7314==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffee90be1a8 at pc 0x0000005a7cfb bp 0x7ffee90be0a0 sp 0x7ffee90be098
READ of size 8 at 0x7ffee90be1a8 thread T0
    #0 0x5a7cfa in libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> libsnark::SHA512_rng<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >(unsigned long) src/common/rng.tcc:53
    #1 0x410f98 in libsnark::knapsack_CRH_with_field_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::sample_randomness(unsigned long) src/gadgetlib1/gadgets/hashes/knapsack/knapsack_gadget.tcc:132
    #2 0x6dcce5 in libsnark::knapsack_CRH_with_field_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::sample_randomness(unsigned long) /usr/include/c++/5/bits/stl_bvector.h:830
    #3 0x6dcce5 in libsnark::knapsack_CRH_with_field_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::get_hash(std::vector<bool, std::allocator<bool> > const&) src/gadgetlib1/gadgets/hashes/knapsack/knapsack_gadget.tcc:98
    #4 0x7176a1 in libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::get_hash(std::vector<bool, std::allocator<bool> > const&) src/gadgetlib1/gadgets/hashes/knapsack/knapsack_gadget.tcc:208
    #5 0x718b8c in libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::hash_value_type libsnark::two_to_one_CRH<libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> > >(libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::hash_value_type const&, libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >::hash_value_type const&) src/common/data_structures/merkle_tree.tcc:36
    #6 0x7198fd in libsnark::merkle_tree<libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> > >::merkle_tree(unsigned long, unsigned long) src/common/data_structures/merkle_tree.tcc:53
    #7 0x71bd0f in libsnark::set_commitment_accumulator<libsnark::knapsack_CRH_with_bit_out_gadget<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> > >::set_commitment_accumulator(unsigned long, unsigned long) src/common/data_structures/set_commitment.tcc:24
    #8 0xb3b218 in libsnark::r1cs_mp_ppzkpcd_keypair<libsnark::default_r1cs_ppzkpcd_pp> libsnark::r1cs_mp_ppzkpcd_generator<libsnark::default_r1cs_ppzkpcd_pp>(std::vector<libsnark::r1cs_pcd_compliance_predicate<libsnark::default_r1cs_ppzkpcd_pp::curve_A_pp::Fp_type>, std::allocator<libsnark::r1cs_pcd_compliance_predicate<libsnark::default_r1cs_ppzkpcd_pp::curve_A_pp::Fp_type> > > const&) src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/r1cs_mp_ppzkpcd.tcc:240
    #9 0xb42768 in bool libsnark::run_r1cs_mp_ppzkpcd_tally_example<libsnark::default_r1cs_ppzkpcd_pp>(unsigned long, unsigned long, unsigned long, bool, bool, bool) src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/examples/run_r1cs_mp_ppzkpcd.tcc:113
    #10 0xb53e10 in void test_tally<libsnark::default_r1cs_ppzkpcd_pp>(unsigned long, unsigned long, bool, bool) src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/tests/test_r1cs_mp_ppzkpcd.cpp:18
    #11 0x406fa0 in main src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/tests/test_r1cs_mp_ppzkpcd.cpp:30
    #12 0x7f77f982460f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2060f)
    #13 0x40ecc8 in _start (/home/daniel/code/git/libsnark/src/zk_proof_systems/pcd/r1cs_pcd/r1cs_mp_ppzkpcd/tests/test_r1cs_mp_ppzkpcd+0x40ecc8)

Address 0x7ffee90be1a8 is located in stack of thread T0 at offset 136 in frame
    #0 0x5a775f in libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> libsnark::SHA512_rng<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >(unsigned long) src/common/rng.tcc:22

  This frame has 4 object(s):
    [32, 40) 'iter'
    [96, 136) 'rval' <== Memory access at offset 136 overflows this variable
    [192, 256) 'hash'
    [288, 504) 'sha512'
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow src/common/rng.tcc:53 libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> libsnark::SHA512_rng<libsnark::Fp_model<5l, libsnark::mnt46_modulus_A> >(unsigned long)
Shadow bytes around the buggy address:
  0x10005d20fbe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fbf0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc10: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc20: 00 00 00 00 f1 f1 f1 f1 00 f4 f4 f4 f2 f2 f2 f2
=>0x10005d20fc30: 00 00 00 00 00[f4]f4 f4 f2 f2 f2 f2 00 00 00 00
  0x10005d20fc40: 00 00 00 00 f2 f2 f2 f2 00 00 00 00 00 00 00 00
  0x10005d20fc50: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc60: 00 00 00 f4 f3 f3 f3 f3 00 00 00 00 00 00 00 00
  0x10005d20fc70: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10005d20fc80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
==7314==ABORTING

edit 2016/04/11: updated to human readable filenames and line numbers

daira commented 8 years ago

Thanks, we'll check this.

daira commented 8 years ago

I looked at the code, and it has a clear off-by-one bug. In the first iteration of the loop at lines 48-56, part will be equal to FieldT::num_limbs. rval is declared as bigint<FieldT::num_limbs> rval; on line 29, so the rval.data[part] &= ~(1ul<<bit); on line 53 will read/assign one past the end of the array.

The intent was probably to initialize bitno to (GMP_NUMB_BITS * FieldT::num_limbs) - 1. Also, nothing currently stops bitno from underflowing if all bits were zero, so the loop condition should be changed to ensure correct termination.

daira commented 8 years ago

Also, we should fix the weird dissociation of the while condition on line 62 from its corresponding do loop ("just" a whitespace issue, but confusing).

daira commented 8 years ago

See https://github.com/zcash/zcash/issues/780.

Also, the buggy code is trying to generate a field element uniformly at random, right? Generating an integer significantly larger than a field element (say by 128 bits) and then reducing it modulo the field size is a better way to do that than rejection sampling, IMHO.

daira commented 8 years ago

I just want to emphasise that this code is clearly incorrect and has undefined behaviour.

daira commented 8 years ago

In Zcash's fork of libsnark we removed this PRNG: https://github.com/zcash/zcash/pull/1104 . It's still broken (and potentially a security bug) in upstream libsnark.

madars commented 7 years ago

Thanks! This has been fixed in libff.