Algorithmic Complexity DoS in Frontier modexp Precompile

Frontier is a Substrate FRAME pallet that provides an Ethereum compatibility layer, enabling Substrate-based blockchains to execute EVM (Ethereum Virtual Machine) smart contracts. A critical component of the EVM specification is the set of precompiled contracts, which perform complex cryptographic or mathematical operations natively for efficiency. One such precompile is modexp (modular exponentiation), located at address 0x00...05.

The vulnerability, identified as CVE-2023-28431, lies in the gas pricing mechanism for this precompile. In EVM implementations, gas acts as a fee that limits computational work. If the gas cost of an operation is significantly lower than the actual computational resources required to execute it, the system becomes vulnerable to Denial of Service (DoS) attacks.

Frontier failed to accurately model the execution time of modexp operations when the modulus is an even number. This oversight exposed the network to an algorithmic complexity attack where an attacker could force nodes to perform heavy computations while paying minimal fees.

The root cause stems from the implementation details of the num-bigint Rust crate, which Frontier uses to perform big integer arithmetic. The library employs two distinct algorithms for modular exponentiation depending on the parity of the modulus:

1. Odd Moduli: The library utilizes Montgomery multiplication. This algorithm is highly optimized for modular arithmetic and performs efficiently.
2. Even Moduli: The library falls back to a standard binary exponentiation (binary power) algorithm. This method is significantly less efficient for large numbers compared to the Montgomery approach.

Benchmarks indicate that the "plain" binary power algorithm for even moduli can be up to 20 times slower than the Montgomery algorithm used for odd moduli. Frontier's gas cost calculation was calibrated based on the performance of the optimized (odd) path. Consequently, it did not apply a penalty or multiplier for the slow (even) path. This created a discrepancy between the priced cost (gas) and the actual cost (CPU cycles), violating the resource-metering guarantees of the EVM.

The remediation involved updating the gas calculation logic to detect the modulus parity and apply a penalty multiplier if the modulus is even. The fix was applied in frame/evm/precompile/modexp/src/lib.rs.

Vulnerable Logic (Conceptual): Previously, the code calculated complexity based solely on the length of the base, modulus, and exponent, ignoring the value of the modulus itself.

Patched Logic: The fix introduces a check for modulus.is_even() and applies a multiplier of 20 to the gas cost if true.

// frame/evm/precompile/modexp/src/lib.rs
 
fn calculate_gas_cost(
    base_length: u64,
    mod_length: u64,
    exponent: &BigUint,
    exponent_bytes: &[u8],
    mod_is_even: bool, // [!code ++] New parameter to track parity
) -> u64 {
    // ... standard complexity calculation based on bit lengths ...
 
    // Calculate the base gas cost
    let gas = max(
        MIN_GAS_COST,
        multiplication_complexity * iteration_count / 3,
    );
 
    // Apply the 20x penalty for even moduli to account for the slow path in num-bigint
    gas.saturating_mul(if mod_is_even { 20 } else { 1 }) // [!code ++]
}

The call site was updated to pass the parity status:

let modulus = BigUint::from_bytes_be(&mod_buf);
 
let gas_cost = calculate_gas_cost(
    base_len as u64,
    mod_len as u64,
    &exponent,
    &exp_buf,
    modulus.is_even(), // [!code ++] Check if modulus is even
);

This change ensures that the gas cost aligns with the actual CPU time required by the underlying library, neutralizing the economic advantage of the attack.

An attacker looking to disrupt a Frontier-based network would craft an Ethereum transaction that interacts with the modexp precompile. The payload would consist of a modexp call where the modulus is a large even number (e.g., 2048-bit).

Attack Steps:

1. Construct Payload: The attacker generates a calldata payload for the precompile address 0x00...05. The parameters are set to maximize the difference between the gas cost and execution time. This typically involves a large base, a large exponent, and a large even modulus.
2. Broadcast Transaction: The attacker signs and broadcasts the transaction to the network. Because the gas cost is calculated using the "fast path" formula, the transaction fee is low, allowing the attacker to include many such calls in a single block or across multiple blocks without draining their funds.
3. Node Exhaustion: When validators and full nodes attempt to process the block, they encounter the modexp instruction. The num-bigint library triggers the slow binary exponentiation path. The CPU usage spikes, and block processing takes significantly longer than expected.

If the attacker sustains this volume, valid transactions may time out, block propagation may be delayed, and nodes with lower hardware specifications may fall out of sync, effectively causing a Denial of Service.

The primary impact of CVE-2023-28431 is reduced availability (DoS).

• Availability: High. A successful attack can stall block production and validation. While it does not halt the network permanently, it can severely degrade performance and throughput.
• Confidentiality & Integrity: None. This vulnerability does not allow an attacker to read memory, leak private keys, or modify state (other than consuming gas).

The vulnerability is particularly dangerous for permissionless public networks where any user can submit transactions. In permissioned chains, the risk is lower as the attacker must already be an authorized participant.