Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
feezybabee opened this issue Jan 10, 2024 · 2 comments
Labels
bug Something isn't working does not block mainnet For when we make decisions that this will not block mainnet.

Comments

@feezybabee
Copy link

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).

@feezybabee feezybabee added the bug Something isn't working label Jan 10, 2024
@ljedrz
Copy link
Collaborator

ljedrz commented Jan 10, 2024

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
Copy link
Contributor

vicsn commented Jan 12, 2024

@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.

@raychu86 raychu86 added the does not block mainnet For when we make decisions that this will not block mainnet. label Jul 3, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working does not block mainnet For when we make decisions that this will not block mainnet.
Projects
None yet
Development

No branches or pull requests

4 participants