[SECURITY] Incorrect Sign Detection Due to High Bit Activation in U256

[pventuzelo]

Overview

Our team (@FuzzingLabs) discovered a bug in the is_negative function, which incorrectly detects certain values as negative due to the activation of the high bit (bit 255) in the U256 representation. This issue arises even when the actual value is below the threshold of 2^255, leading to unexpected behavior in functions relying on is_negative for sign determination.

Steps to Reproduce

Payload

[58, 63, 58, 5]

GASPRICE
EXTCODEHASH
GASPRICE
SDIV1

Add to [test](https://github.com/lambdaclass/lambda_ethereum_rust/blob/main/crates/vm/levm/tests/tests.rs) :

#[test]
fn test_is_negative() {
    let mut vm = new_vm_with_bytecode(Bytes::copy_from_slice(&[58, 63, 58, 5]));
    let mut current_call_frame = vm.call_frames.pop().unwrap();
    vm.execute(&mut current_call_frame);
}

Root Cause Analysis

fn is_negative(value: U256) -> bool {
    value.bit(255)
}

pub const fn bit(&self, index: usize) -> bool {
	let &$name(ref arr) = self;
	arr[index / 64] & (1 << (index % 64)) != 0
}

The high bit (bit 255) is activated due to how the value is represented internally within U256. The is_negative function relies on this bit for sign detection. However, in this specific case, it is unintentionally set, leading to an incorrect interpretation.

This issue likely results from an erroneous representation or incorrect bit manipulation when constructing the U256 value. As a result, values less than 2^255 can still be misinterpreted as negative.

Example

fn main() {
    let value = U256::from_dec_str("89477152217924674838424037953991966239322087453347756267410168184682657981552").unwrap();
    println!("Bit value: {}", is_negative(value)); // Expected: false, Actual: true
}

fn is_negative(value: U256) -> bool {
    println!("Bit value : {}, Value : {}", value.bit(255), value);
    value.bit(255)
}

Bit value : true, Value : 89477152217924674838424037953991966239322087453347756267410168184682657981552

Representation Details

• Part 0: 0b0111101111111010110110000000010001011101100001011010010001110000
• Part 1: 0b1110010100000000101101100101001111001010100000100010011100111011
• Part 2: 0b1001001001111110011111011011001011011100110001110000001111000000
• Part 3: 0b1100010111010010010001100000000110000110111101110010001100111100 (Bit 255 is set to 1)

Because the divisor is flagged as a negative value, the quotient (=0 here) will be set to a negative value too:

let quotient_is_negative = dividend_is_negative ^ divisor_is_negative;
let quotient = if quotient_is_negative {
          negate(quotient)
      } else {
          quotient
      };

Finally, the function negate is called with a value equal to 0 :

/// Negates a number in two's complement
fn negate(value: U256) -> U256 {
    !value + U256::one()
}

!0 = U256::MAX , so here we have an overflow because we are doing U256::MAX+1.

Backtrace

---- tests::test_is_negative stdout ----
thread 'tests::test_is_negative' panicked at /home/.../.cargo/registry/src/index.crates.io-6f17d22bba15001f/primitive-types-0.12.2/src/lib.rs:38:1:
arithmetic operation overflow
stack backtrace:
   0: rust_begin_unwind
             at /rustc/59e2c01c2217a01546222e4d9ff4e6695ee8a1db/library/std/src/panicking.rs:658:5
   1: core::panicking::panic_fmt
             at /rustc/59e2c01c2217a01546222e4d9ff4e6695ee8a1db/library/core/src/panicking.rs:74:14
   2: <primitive_types::U256 as core::ops::arith::Add<T>>::add
             at /home/mhoste/.cargo/registry/src/index.crates.io-6f17d22bba15001f/uint-0.9.5/src/uint.rs:1387:5
   3: ethereum_rust_levm::opcode_handlers::arithmetic::negate
             at ./src/opcode_handlers/arithmetic.rs:267:5
   4: ethereum_rust_levm::opcode_handlers::arithmetic::<impl ethereum_rust_levm::vm::VM>::op_sdiv
             at ./src/opcode_handlers/arithmetic.rs:94:13
   5: ethereum_rust_levm::vm::VM::execute
             at ./src/vm.rs:155:33
   6: lib::tests::test_is_negative
             at ./tests/tests.rs:96:5
   7: lib::tests::test_is_negative::{{closure}}
             at ./tests/tests.rs:93:22
   8: core::ops::function::FnOnce::call_once
             at /rustc/59e2c01c2217a01546222e4d9ff4e6695ee8a1db/library/core/src/ops/function.rs:250:5
   9: core::ops::function::FnOnce::call_once
             at /rustc/59e2c01c2217a01546222e4d9ff4e6695ee8a1db/library/core/src/ops/function.rs:250:5