CVE-2022-21685: Integer Underflow (Wrap or Wraparound) (CWE-191)
value: Frontier is Substrate's Ethereum compatibility layer. Prior to commit number `8a93fdc6c9f4eb1d2f2a11b7ff1d12d70bf5a664`, a bug in Frontier's MODEXP precompile implementation can cause an integer underflow in certain conditions. This will cause a node crash for debug builds. For release builds (and production WebAssembly binaries), the impact is limited as it can only cause a normal EVM out-of-gas. Users who do not use MODEXP precompile in their runtime are not impacted. A patch is available in pull request #549.
CWE description: The product subtracts one value from another, such that the result is less than the minimum allowable integer value, which produces a value that is not equal to the correct result.
CVSS v3 base score: 6.5
Published: 2022-01-14T17:15Z
Repository: https://github.com/paritytech/frontier
Language: Rust
Files changed: frame/evm/precompile/modexp/src/lib.rs
Commit date: 2022-01-13 17:23:07 +0100
Commit message: Handle 0 exponent with fudged length correctly in ModExp (#549)

* Handle 0 exponent with fudged length correctly in ModExp

* cargo fmt

* Revert to following EIP-2565 strictly, subtract after adding terms to prevent underflow

* Update frame/evm/precompile/modexp/src/lib.rs

Clean up test case

Co-authored-by: Wei Tang <accounts@that.world>

* More revert

* cargo fmt

* Prefer expect to match

Co-authored-by: Wei Tang <accounts@that.world>
Diff: diff --git a/frame/evm/precompile/modexp/src/lib.rs b/frame/evm/precompile/modexp/src/lib.rs
index a7ae46e5..2aaad31b 100644
--- a/frame/evm/precompile/modexp/src/lib.rs
+++ b/frame/evm/precompile/modexp/src/lib.rs
@@ -45,11 +45,14 @@ fn calculate_gas_cost(
 		let mut words = max_length / 8;
 		if max_length % 8 > 0 {
 			words += 1;
 		}
 
-		// TODO: prevent/handle overflow
+		// Note: can't overflow because we take words to be some u64 value / 8, which is
+		// necessarily less than sqrt(u64::MAX).
+		// Additionally, both base_length and mod_length are bounded to 1024, so this has
+		// an upper bound of roughly (1024 / 8) squared
 		words * words
 	}
 
 	fn calculate_iteration_count(exp_length: u64, exponent: &BigUint) -> u64 {
 		let mut iteration_count: u64 = 0;
@@ -61,12 +64,21 @@ fn calculate_gas_cost(
 		} else if exp_length > 32 {
 			// construct BigUint to represent (2^256) - 1
 			let bytes: [u8; 32] = [0xFF; 32];
 			let max_256_bit_uint = BigUint::from_bytes_be(&bytes);
 
+			// from the EIP spec:
+			// (8 * (exp_length - 32)) + ((exponent & (2**256 - 1)).bit_length() - 1)
+			//
+			// Notes:
+			// * exp_length is bounded to 1024 and is > 32
+			// * exponent can be zero, so we subtract 1 after adding the other terms (whose sum
+			//   must be > 0)
+			// * the addition can't overflow because the terms are both capped at roughly
+			//   8 * max size of exp_length (1024)
 			iteration_count =
-				(8 * (exp_length - 32)) + ((exponent.bitand(max_256_bit_uint)).bits() - 1);
+				(8 * (exp_length - 32)) + exponent.bitand(max_256_bit_uint).bits() - 1;
 		}
 
 		max(iteration_count, 1)
 	}
 
@@ -87,11 +99,11 @@ fn calculate_gas_cost(
 // 4) base, size as described above
 // 5) exponent, size as described above
 // 6) modulus, size as described above
 //
 //
-// NOTE: input sizes are arbitrarily large (up to 256 bits), with the expectation
+// NOTE: input sizes are bound to 1024 bytes, with the expectation
 //       that gas limits would be applied before actual computation.
 //
 //       maximum stack size will also prevent abuse.
 //
 //       see: https://eips.ethereum.org/EIPS/eip-198
@@ -131,11 +143,11 @@ impl Precompile for Modexp {
 
 		buf.copy_from_slice(&input[64..96]);
 		let mod_len_big = BigUint::from_bytes_be(&buf);
 		if mod_len_big > max_size_big {
 			return Err(PrecompileFailure::Error {
-				exit_status: ExitError::Other("unreasonably large exponent length".into()),
+				exit_status: ExitError::Other("unreasonably large modulus length".into()),
 			});
 		}
 
 		// bounds check handled above
 		let base_len = base_len_big.to_usize().expect("base_len out of bounds");
@@ -160,11 +172,10 @@ impl Precompile for Modexp {
 
 			let exp_start = base_start + base_len;
 			let exponent = BigUint::from_bytes_be(&input[exp_start..exp_start + exp_len]);
 
 			// do our gas accounting
-			// TODO: we could technically avoid reading base first...
 			let gas_cost =
 				calculate_gas_cost(base_len as u64, exp_len as u64, mod_len as u64, &exponent);
 			if let Some(gas_left) = target_gas {
 				if gas_left < gas_cost {
 					return Err(PrecompileFailure::Error {
@@ -421,6 +432,41 @@ mod tests {
 			Err(_) => {
 				panic!("Modexp::execute() returned error"); // TODO: how to pass error on?
 			}
 		}
 	}
+
+	#[test]
+	fn test_zero_exp_with_33_length() {
+		// This is a regression test which ensures that the 'iteration_count' calculation
+		// in 'calculate_iteration_count' cannot underflow.
+		//
+		// In debug mode, this underflow could cause a panic. Otherwise, it causes N**0 to
+		// be calculated at more-than-normal expense.
+		//
+		// TODO: cite security advisory
+
+		let input = vec![
+			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+			0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+			0, 0, 0, 0, 0, 33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+			0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
+		];
+
+		let cost: u64 = 100000;
+
+		let context: Context = Context {
+			address: Default::default(),
+			caller: Default::default(),
+			apparent_value: From::from(0),
+		};
+
+		let precompile_result = Modexp::execute(&input, Some(cost), &context, false)
+			.expect("Modexp::execute() returned error");
+
+		assert_eq!(precompile_result.output.len(), 1); // should be same length as mod
+		let result = BigUint::from_bytes_be(&precompile_result.output[..]);
+		let expected = BigUint::parse_bytes(b"0", 10).unwrap();
+		assert_eq!(result, expected);
+	}
 }

Vulnerable code: 		// TODO: prevent/handle overflow
				(8 * (exp_length - 32)) + ((exponent.bitand(max_256_bit_uint)).bits() - 1);
// NOTE: input sizes are arbitrarily large (up to 256 bits), with the expectation
				exit_status: ExitError::Other("unreasonably large exponent length".into()),
			// TODO: we could technically avoid reading base first...
Fixed code: 		// Note: can't overflow because we take words to be some u64 value / 8, which is
		// necessarily less than sqrt(u64::MAX).
		// Additionally, both base_length and mod_length are bounded to 1024, so this has
		// an upper bound of roughly (1024 / 8) squared
			// from the EIP spec:
			// (8 * (exp_length - 32)) + ((exponent & (2**256 - 1)).bit_length() - 1)
			//
			// Notes:
			// * exp_length is bounded to 1024 and is > 32
			// * exponent can be zero, so we subtract 1 after adding the other terms (whose sum
			//   must be > 0)
			// * the addition can't overflow because the terms are both capped at roughly
			//   8 * max size of exp_length (1024)
				(8 * (exp_length - 32)) + exponent.bitand(max_256_bit_uint).bits() - 1;
// NOTE: input sizes are bound to 1024 bytes, with the expectation
				exit_status: ExitError::Other("unreasonably large modulus length".into()),

	#[test]
	fn test_zero_exp_with_33_length() {
		// This is a regression test which ensures that the 'iteration_count' calculation
		// in 'calculate_iteration_count' cannot underflow.
		//
		// In debug mode, this underflow could cause a panic. Otherwise, it causes N**0 to
		// be calculated at more-than-normal expense.
		//
		// TODO: cite security advisory

		let input = vec![
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 33, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
			0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,
		];

		let cost: u64 = 100000;

		let context: Context = Context {
			address: Default::default(),
			caller: Default::default(),
			apparent_value: From::from(0),
		};

		let precompile_result = Modexp::execute(&input, Some(cost), &context, false)
			.expect("Modexp::execute() returned error");

		assert_eq!(precompile_result.output.len(), 1); // should be same length as mod
		let result = BigUint::from_bytes_be(&precompile_result.output[..]);
		let expected = BigUint::parse_bytes(b"0", 10).unwrap();
		assert_eq!(result, expected);
	}