[Bug] Addition overflow panics when trying to trim (in sonic_pc) with a supported_degree or a supported_hiding_bound too large

[pventuzelo]

Addition overflow panics when trying to trim (in sonic_pc) with a supported_degree or a supported_hiding_bound too large

We (@FuzzingLabs) found 3 additions with overflow in the trim function, making the library crash when compiled in debug and silently overflow when compiled in release mode (which might lead to undefined behavior).

thread 'main' panicked at /home/ronan/Desktop/Projects/ALEO/snarkVM/algorithms/src/polycommit/sonic_pc/mod.rs:121:55

thread 'main' panicked at /home/ronan/Desktop/Projects/ALEO/snarkVM/algorithms/src/polycommit/sonic_pc/mod.rs:122:49

thread 'main' panicked at /home/ronan/Desktop/Projects/ALEO/snarkVM/algorithms/src/polycommit/sonic_pc/mod.rs:104:34:

Your Environment

• rustc 1.73.0 (cc66ad468 2023-10-03)
• Ubuntu 23.04

Steps to reproduce

Download:

git clone https://github.com/AleoHQ/snarkVM.git

Testing program:

main.rs:

use snarkvm_algorithms::polycommit::sonic_pc::*;
use snarkvm_algorithms::crypto_hash::PoseidonSponge;
use snarkvm_curves::bls12_377::{Fq,Bls12_377};

fn main() {
    let max_degree = 42; // Whatever
    let pp = SonicKZG10::<Bls12_377, PoseidonSponge<Fq, 2, 1>>::load_srs(max_degree).unwrap();
    let supported_lagrange_sizes = Vec::new();
    


    let umax = 8*std::mem::size_of::<usize>(); // umax is the log of the greatest value that we can put in an usize

    let supported_hiding_bound = ((2 as u128).pow(umax as u32)-1) as usize; //greatest value that we can put in an usize
    let supported_degree = 42; // Whatever
    let degree_bounds: Option<&[usize]> = Some(&[42,42]); //or None to have the bug later

    // or, for the other variable error:
    // let supported_hiding_bound = 42; // Whatever
    // let supported_degree = ((2 as u128).pow(umax as u32)-1) as usize; // greatest value that we can put in an usize
    // let degree_bounds: Option<&[usize]> = None;

    let (_, _) = SonicKZG10::<Bls12_377, PoseidonSponge<Fq, 2, 1>>::trim(
        &pp,
        supported_degree,
        supported_lagrange_sizes,
        supported_hiding_bound,
        degree_bounds,
    )
    .unwrap();
}

Cargo.toml:

[package]
name = "tests"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
snarkvm = { path = "../snarkVM" }
snarkvm-algorithms = { path = "../snarkVM/algorithms" }
snarkvm-curves = { path = "../snarkVM/curves" }

Build and run:

cargo build
cargo run

Root causes

https://github.com/AleoHQ/snarkVM/blob/6528130cd63920eb85f09a7a6a1ab15cdc559362/algorithms/src/polycommit/sonic_pc/mod.rs#L121
https://github.com/AleoHQ/snarkVM/blob/6528130cd63920eb85f09a7a6a1ab15cdc559362/algorithms/src/polycommit/sonic_pc/mod.rs#L122
https://github.com/AleoHQ/snarkVM/blob/6528130cd63920eb85f09a7a6a1ab15cdc559362/algorithms/src/polycommit/sonic_pc/mod.rs#L104

Detailed behavior (RUST_BACKTRACE=1)

thread 'main' panicked at /home/ronan/Desktop/Projects/ALEO/snarkVM/algorithms/src/polycommit/sonic_pc/mod.rs:121:55:
attempt to add with overflow
stack backtrace:
   0: rust_begin_unwind
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/std/src/panicking.rs:595:5
   1: core::panicking::panic_fmt
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/panicking.rs:67:14
   2: core::panicking::panic
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/panicking.rs:117:5
   3: snarkvm_algorithms::polycommit::sonic_pc::SonicKZG10<E,S>::trim
             at /home/ronan/Desktop/Projects/ALEO/snarkVM/algorithms/src/polycommit/sonic_pc/mod.rs:121:55
   4: tests::error_usize_trim
             at ./src/main.rs:140:18
   5: tests::main
             at ./src/main.rs:157:5
   6: core::ops::function::FnOnce::call_once
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

thread 'main' panicked at /home/ronan/Desktop/Projects/ALEO/snarkVM/algorithms/src/polycommit/sonic_pc/mod.rs:122:49:
attempt to add with overflow
stack backtrace:
   0: rust_begin_unwind
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/std/src/panicking.rs:595:5
   1: core::panicking::panic_fmt
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/panicking.rs:67:14
   2: core::panicking::panic
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/panicking.rs:117:5
   3: snarkvm_algorithms::polycommit::sonic_pc::SonicKZG10<E,S>::trim
             at /home/ronan/Desktop/Projects/ALEO/snarkVM/algorithms/src/polycommit/sonic_pc/mod.rs:122:49
   4: tests::error_usize_trim
             at ./src/main.rs:140:18
   5: tests::main
             at ./src/main.rs:157:5
   6: core::ops::function::FnOnce::call_once
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

thread 'main' panicked at /home/ronan/Desktop/Projects/ALEO/snarkVM/algorithms/src/polycommit/sonic_pc/mod.rs:104:34:
attempt to add with overflow
stack backtrace:
   0: rust_begin_unwind
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/std/src/panicking.rs:595:5
   1: core::panicking::panic_fmt
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/panicking.rs:67:14
   2: core::panicking::panic
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/panicking.rs:117:5
   3: snarkvm_algorithms::polycommit::sonic_pc::SonicKZG10<E,S>::trim
             at /home/ronan/Desktop/Projects/ALEO/snarkVM/algorithms/src/polycommit/sonic_pc/mod.rs:104:34
   4: tests::error_usize_trim
             at ./src/main.rs:140:18
   5: tests::main
             at ./src/main.rs:157:5
   6: core::ops::function::FnOnce::call_once
             at /rustc/cc66ad468955717ab92600c770da8c1601a4ff33/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

In the snarkVM implementation

The trim function is only used in the batch_circuit_setup function in varuna. The supported_hiding_bound parameter is set to 1 (l.91), so it cannot overflow. The supported_degree parameter is set to indexed_circuit.max_degree() (l.95), which can be only worth an even value (and so <usize_max), or an odd value that is to small to overflow (regarding the ouput of the max_degree function). So the overflow can not occur with current usage.

Solving possibilities

Replace the additions to lines 104, 121, 122 by a checked-add, and check that the result is not None.