[Bug] Integer overflow in EvaluationDomain::reindex_by_subdomain() function

[feezybabee]

Summary:

The attacker can trigger integer overflow function EvaluationDomain::reindex_by_subdomain() when using the big input index.

Consider the following branch:

            let i = index - other.size();
            let x = period - 1;
            Ok(i + (i / x) + 1)

i is controllable variable (equal toindex - other.size()). At the same time, there are no usize bounds checks in the code.
Let's consider the case where other.size() = 1, self.size() = 2 and index = usize::MAX / 2 + 2.
In this case usize will overflow and the result will be equal to:

• usize::MAX + 2 = 1 in release build
• panic in debug build

Proof-of-Concept (PoC)

Cargo.toml

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

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

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

src/main.rs

use snarkvm_algorithms::fft::domain::EvaluationDomain;
use snarkvm_curves::bls12_377::Fr;

fn main() {
    if let Some(domain1) = EvaluationDomain::<Fr>::new(2) {
        if let Some(domain2) = EvaluationDomain::<Fr>::new(1) {
            println!("size1: {}, size2: {}", domain1.size(), domain2.size());
            let res = domain1.reindex_by_subdomain(&domain2, usize::MAX / 2 + 2);
            println!("{:?}", res);
        }
    }
}

Result (release)

$ ./target/release/test
size1: 2, size2: 1
Ok(1)

Result (debug)

$ RUST_BACKTRACE=1 ./target/debug/test
size1: 2, size2: 1
thread 'main' panicked at 'attempt to add with overflow', /tmp/Aleo/snarkVM/algorithms/src/fft/domain.rs:341:16
stack backtrace:
   0: rust_begin_unwind
             at /rustc/d5c2e9c342b358556da91d61ed4133f6f50fc0c3/library/std/src/panicking.rs:593:5
   1: core::panicking::panic_fmt
             at /rustc/d5c2e9c342b358556da91d61ed4133f6f50fc0c3/library/core/src/panicking.rs:67:14
   2: core::panicking::panic
             at /rustc/d5c2e9c342b358556da91d61ed4133f6f50fc0c3/library/core/src/panicking.rs:117:5
   3: snarkvm_algorithms::fft::domain::EvaluationDomain<F>::reindex_by_subdomain
             at /tmp/Aleo/snarkVM/algorithms/src/fft/domain.rs:341:16
   4: test::main
             at ./src/main.rs:8:23
   5: core::ops::function::FnOnce::call_once
             at /rustc/d5c2e9c342b358556da91d61ed4133f6f50fc0c3/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Impact

The severity of this issue will strongly depend on the use of the function in the code. The issue may lead to DoS and to more serious problems (since the code will not panic in release builds, but will still provide an incorrect result).

[ljedrz]

I can confirm that I can reproduce the panic with the attached program with 6b2a814 (current testnet3); as long as the problematic conditions are possible, this could also lead to incorrect results in release builds.

[vicsn]

@ljedrz same as the other recent related low level reports, this is an invalid bug submission and they did not show anything actually exploitable, but it would be nice to fix our inner function API at some point.