Opcode EXP for large even number can make starkent transaction revert due to running out of steps

[c4-bot-8]

Lines of code

https://github.com/kkrt-labs/kakarot/blob/7411a5520e8a00be6f5243a50c160e66ad285563/src/utils/uint256.cairo#L344

Vulnerability details

Impact

When the opcode is EXP ( i.e 0x0A ), the uint256.cairo::uint256_fast_exp function is called ( interpreter.cairo::exec_opcode -> stop_and_math_operations.cairo::exec_math_operation -> uint256.cairo::uint256_fast_exp )

The uint256.cairo::uint256_fast_exp function is as follows :

// @notice Internal fast exponentiation of two 256-bit integers.
// @dev The result is modulo 2^256.
// @param value - The base.
// @param exponent - The exponent.
// @return The result of the exponentiation.
func uint256_fast_exp{range_check_ptr}(value: Uint256, exponent: Uint256) -> Uint256 {
    alloc_locals;

    let one = Uint256(1, 0);
    let zero = Uint256(0, 0);

    let (exponent_is_zero) = uint256_eq(exponent, zero);
    if (exponent_is_zero != FALSE) {
        return one;
    }

    let (exponent_is_one) = uint256_eq(exponent, one);
    if (exponent_is_one != FALSE) {
        return value;
    }

    let (half_exponent, is_odd) = uint256_unsigned_div_rem(exponent, Uint256(2, 0));
    let pow = uint256_fast_exp(value, half_exponent);

    if (is_odd.low != FALSE) {
        let (res, _) = uint256_mul(pow, pow);
        let (res, _) = uint256_mul(res, value);
        return res;
    }

->  let pow = uint256_fast_exp(value, half_exponent);
    let (res, _) = uint256_mul(pow, pow);
    return res;
}

This function executes let pow = uint256_fast_exp(value, half_exponent); twice for even number even though it's already executed once and this makes transaction revert due to running out of steps when the exponent is large and even.

The uint256.cairo::uint256_fast_exp function is using Exponentiation by squaring method which have time complexity of O(log exp) where exp is the exponent. But due to inefficient implementation, the time complexity is O(exp) which makes the transaction revert due to running out of steps when the exponent is large and even.

NOTE: The max steps allowed is 10,000,000 as per starknet docs ( refer: Max transaction size (Cairo steps) ). So in mainnet, this transaction will revert due to out of steps error.

The gas EXP opcode takes is ( https://www.evm.codes/?fork=cancun#0a ):

static_gas = 10
dynamic_gas = 50 * exponent_byte_size

Thus, the maximum gas EXP opcode can take is 10 + (50 * 32) = 1610. But if the exponent is of size 32 bytes and even, then the uint256.cairo::uint256_fast_exp function will make the transaction revert due to running out of steps. So any contract which uses EXP can be affected by this issue or if a contract makes a callback to another contract by making sure to only send limited gas and handle the revert case properly, the other contract can use EXP opcode to make the transaction revert forcefully.

Proof of Concept

Add this file named test_uint256_exp_bug.cairo in kakarot/tests/src/utils folder:

%builtins range_check

from starkware.cairo.common.cairo_builtins import HashBuiltin
from starkware.cairo.common.uint256 import Uint256
from starkware.cairo.common.alloc import alloc

from utils.uint256 import uint256_fast_exp

func test__uint256_exp{range_check_ptr}() -> (felt, felt) {
    alloc_locals;
    let (a_ptr) = alloc();
    let (b_ptr) = alloc();
    %{
        segments.write_arg(ids.a_ptr, program_input["a"])
        segments.write_arg(ids.b_ptr, program_input["b"])
    %}
    let res = uint256_fast_exp([cast(a_ptr, Uint256*)], [cast(b_ptr, Uint256*)]);

    return (res.low, res.high);
}

Also, add this file named test_uint256_exp_bug.py in kakarot/tests/src/utils folder:

import pytest
from hypothesis import given, settings
from hypothesis.strategies import integers

from kakarot_scripts.utils.uint256 import int_to_uint256, uint256_to_int

class TestUint256Exp:
    def test_exp(self, cairo_run):
        a = 2
        b = 2**256 - 2 // 2**256 - 1 is odd
        low, high = cairo_run(
            "test__uint256_exp", a=int_to_uint256(a), b=int_to_uint256(b)
        )
        print(f"low: {low}, high: {high}, uint256_to_int: {uint256_to_int(low, high)}")

You can run the test by:

cd kakarot
uv run pytest -s "./tests/src/utils/test_uint256_exp_bug.py::TestUint256Exp::test_exp"

This will take very long time ( due to speed of python ) before throwing error that the transaction ran out of steps ( n_steps=10_000_000 ) which will be something like:

...
Error: End of program was not reached
...

NOTE: You can print number of steps by adding the print statement in kakarot/tests/fixtures/starknet.py:

            if len(function_output) > 0:
                final_output = (final_output, *function_output)
        else:
            final_output = function_output
->      print(f"runner.original_steps: {runner.original_steps}")
->      print(f"runner.vm.current_step: {runner.vm.current_step}")
        return final_output

    return _factory

Although it won't print the steps as the transaction will revert before that.

Whereas, if you change the b value to 2**256 - 1 ( i.e. odd number ), the test will execute in around 16.47s ( in my machine ) and will print low: 0, high: 0, uint256_to_int: 0. The number of steps taken is 186704.

Tools Used

Python test suite

Recommended Mitigation Steps

It can be fixed by removing the extra line let pow = uint256_fast_exp(value, half_exponent); from the function uint256.cairo::uint256_fast_exp:

// @notice Internal fast exponentiation of two 256-bit integers.
// @dev The result is modulo 2^256.
// @param value - The base.
// @param exponent - The exponent.
// @return The result of the exponentiation.
func uint256_fast_exp{range_check_ptr}(value: Uint256, exponent: Uint256) -> Uint256 {
    alloc_locals;

    let one = Uint256(1, 0);
    let zero = Uint256(0, 0);

    let (exponent_is_zero) = uint256_eq(exponent, zero);
    if (exponent_is_zero != FALSE) {
        return one;
    }

    let (exponent_is_one) = uint256_eq(exponent, one);
    if (exponent_is_one != FALSE) {
        return value;
    }

    let (half_exponent, is_odd) = uint256_unsigned_div_rem(exponent, Uint256(2, 0));
    let pow = uint256_fast_exp(value, half_exponent);

    if (is_odd.low != FALSE) {
        let (res, _) = uint256_mul(pow, pow);
        let (res, _) = uint256_mul(res, value);
        return res;
    }

-   let pow = uint256_fast_exp(value, half_exponent);
    let (res, _) = uint256_mul(pow, pow);
    return res;
}

Now it will make time complexity of uint256.cairo::uint256_fast_exp function to O(log exp) where exp is the exponent.

For reference, now for b = 2**256 - 1 in the test will take 186194 steps and for b = 2**256 - 2 in the test will take 185985 steps.

Assessed type

Loop

[ClementWalter]

Severity: Informative

Comment: This is not a security risk. Useless computation only.

[c4-judge]

dmvt changed the severity to QA (Quality Assurance)

[c4-judge]

dmvt marked the issue as grade-b

[Ahmed-Aghadi]

EXP is one of the opcode, thus an important functionality of Kakarot. If EXP doesn't work for a range of numbers then it is at least the function of the protocol or its availability could be impacted. So it should be at least medium.

[koolexcrypto]

Hi @dmvt ,

I agree with @Ahmed-Aghadi . This is not just a useless computation as mentioned for some even large numbers it might revert, for others it might consume too many Cairo steps. Please take into account, this is not a Starknet limitation as it can be easily fixed in the code.

[dmvt]

I agree that it's valid, which is why I brought it to QA despite it being initially submitted as high risk (also it's quite well written). Normally I would invalidate that for overinflated severity. That said, I can't see a justification for medium risk here.

[koolexcrypto]

Would appreciate it if you can be a bit more specific on the reasoning behind your decision.

-- Update --

Additional clarification that might help:
This is actually just a delegation of a security concern to a lower level. The borderline should be, if it can be fixed easily, it's a concern of Kakarot and not Starknet. Imagine, an opcode takes 350K+ Cairo steps. So, if you have a contract with a few opcodes (Exp), the contract won't work on Kakarot given that 10M Cairo step is the limit. So the question is, (from an architect perspective), can this be minimized significantly? If yes, then it's an issue in Kakarot not a limitation of Starknet.

On L1, you could fit 18K of the same opcode in one block. (gas = 10+50*byteLen = 1610 as max if I am not mistaken)

[0xEVom]

PJQA is over @koolexcrypto

[koolexcrypto]

@0xEVom the 48 hours duration is for initial comments. You can always add further comments if you want.

[0xEVom]

That is not the case, see here.

[koolexcrypto]

That's not against adding further comments nor against the purpose of PJQA. Engagement is completely fine if needed. Even from Wardens that are not participants. Of course, It is up to the judge to respond or not.

[0xEVom]

Perhaps there's something you misunderstood in the announcement? It precisely says no comments are allowed outside PJQA, the only exception being when a judge requests further input.