[Bug] Usize underflow and usize overflow vulnerabilities via controllable arguments in ‎nonnative_params::find_parameters() function

[feezybabee]

https://hackerone.com/reports/2258963

Summary:

The nonnative_params::find_parameters() function accepts two parameters that are involved in further arithmetic operations: base_field_prime_length and target_field_prime_bit_length.
Both parameters can be considered controllable as they are thrown to the PoseidonSponge API:

• PoseidonSponge::compress_elements() -> get_params() -> find_parameters()
• PoseidonSponge::get_limbs_representations_from_big_integer() -> get_params() -> find_parameters()

Where base_field_prime_length will be equal to F::size_in_bits() and target_field_prime_bit_length will be equal to TargetField::size_in_bits().

Consider the following code line: https://github.com/AleoHQ/snarkVM/blob/c620cc4a89bcd81e9de07e827886a2a57e4375e6/algorithms/src/traits/algebraic_sponge.rs#L177.
Since base_field_prime_length value is not checked to be more then 13, usize underflow may occur.

At the same way since target_field_prime_bit_length value is not checked, usize overflow may occur on the following code line: https://github.com/AleoHQ/snarkVM/blob/c620cc4a89bcd81e9de07e827886a2a57e4375e6/algorithms/src/traits/algebraic_sponge.rs#L184.

And we can see many such cases further down the code, since the function does not contain any checks at all.

Proof-of-Concept (PoC)

To check these vulnerabilities, I have prepared the following tests:

#[cfg(test)]
mod tests {
    use super::nonnative_params;

    #[test]
    fn test_find_parameters_usize_underflow() {
        let base_field_prime_length = 0; // min value to trigger attempt to subtract with overflow
        let target_field_prime_bit_length = 256;
        let optimization_type = nonnative_params::OptimizationType::Constraints;
        let _res = nonnative_params::find_parameters(
            base_field_prime_length,
            target_field_prime_bit_length,
            optimization_type,
        );
    }

    #[test]
    fn test_find_parameters_usize_overflow() {
        let base_field_prime_length = 256;
        let target_field_prime_bit_length = usize::MAX; // max value to trigger attempt to add with overflow
        let optimization_type = nonnative_params::OptimizationType::Constraints;
        let _res = nonnative_params::find_parameters(
            base_field_prime_length,
            target_field_prime_bit_length,
            optimization_type,
        );
    }
}

Results are shown below:

running 1 test
thread 'traits::algebraic_sponge::tests::test_find_parameters_usize_underflow' panicked at 'attempt to subtract with overflow', algorithms/src/traits/algebraic_sponge.rs:177:34
stack backtrace:
   0: rust_begin_unwind
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/std/src/panicking.rs:593:5
   1: core::panicking::panic_fmt
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/core/src/panicking.rs:67:14
   2: core::panicking::panic
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/core/src/panicking.rs:117:5
   3: snarkvm_algorithms::traits::algebraic_sponge::nonnative_params::find_parameters
             at ./src/traits/algebraic_sponge.rs:177:34
   4: snarkvm_algorithms::traits::algebraic_sponge::tests::test_find_parameters_usize_underflow
             at ./src/traits/algebraic_sponge.rs:243:20
   5: snarkvm_algorithms::traits::algebraic_sponge::tests::test_find_parameters_usize_underflow::{{closure}}
             at ./src/traits/algebraic_sponge.rs:239:47
   6: core::ops::function::FnOnce::call_once
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/core/src/ops/function.rs:250:5
   7: core::ops::function::FnOnce::call_once
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

running 1 test
thread 'traits::algebraic_sponge::tests::test_find_parameters_usize_overflow' panicked at 'attempt to add with overflow', algorithms/src/traits/algebraic_sponge.rs:184:33
stack backtrace:
   0: rust_begin_unwind
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/std/src/panicking.rs:593:5
   1: core::panicking::panic_fmt
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/core/src/panicking.rs:67:14
   2: core::panicking::panic
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/core/src/panicking.rs:117:5
   3: snarkvm_algorithms::traits::algebraic_sponge::nonnative_params::find_parameters
             at ./src/traits/algebraic_sponge.rs:184:33
   4: snarkvm_algorithms::traits::algebraic_sponge::tests::test_find_parameters_usize_overflow
             at ./src/traits/algebraic_sponge.rs:255:20
   5: snarkvm_algorithms::traits::algebraic_sponge::tests::test_find_parameters_usize_overflow::{{closure}}
             at ./src/traits/algebraic_sponge.rs:251:46
   6: core::ops::function::FnOnce::call_once
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/core/src/ops/function.rs:250:5
   7: core::ops::function::FnOnce::call_once
             at /rustc/eb26296b556cef10fb713a38f3d16b9886080f26/library/core/src/ops/function.rs:250:5
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

Impact

In a release build, this vulnerability will not cause panic and will produce false results on specifically crafted TargetField and PrimeField.

[ljedrz]

Nit: both cases are overflows.

As for the vulnerability, I don't think it's possible with current snarkVM/OS code, but it's something that may need to be fixed with future users of the snarkVM libraries in mind.