Missing enforcment of valid r range in ecrecover

[c4-bot-10]

Lines of code

https://github.com/kkrt-labs/kakarot/blob/7411a5520e8a00be6f5243a50c160e66ad285563/src/kakarot/precompiles/ec_recover.cairo#L40

Vulnerability details

Impact

The valid range of r is not being enforced when calling ecrecover. This causes an issue where if r is set outside its valid range (as defined by the Ethereum yellow paper), Kakarot will panic, while on Ethereum, it will simply return address(0).

Proof of Concept

According to the Ethereum yellow paper, an ECDSA signature is only valid if all the following conditions are true:

• 0 < r < secp256k1n
• 0 < s < secp256k1n / 2 + 1
• v = 27 || 28
  where secp256k1n = 115792089237316195423570985008687907852837564279074904382605163141518161494337 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
  https://ethereum.github.io/yellowpaper/paper.pdf

If s and v are valid, but r exceeds its maximum value (i.e., r >= 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141):

• On Ethereum, ecrecover returns address(0).
• On Kakarot, it causes a panic with errors like "Invalid argument" and "Option::unwrap failed."

This is a significant difference between Kakarot and Ethereum.

The issue occurs when the precompiler ecrecover is invoked, and the following function is executed:

    func run{
        syscall_ptr: felt*,
        pedersen_ptr: HashBuiltin*,
        range_check_ptr,
        bitwise_ptr: BitwiseBuiltin*,
    }(_address: felt, input_len: felt, input: felt*) -> (
        output_len: felt, output: felt*, gas_used: felt, reverted: felt
    ) {
        alloc_locals;

        let (input_padded) = alloc();
        slice(input_padded, input_len, input, 0, 4 * 32);

        let v_uint256 = Helpers.bytes32_to_uint256(input_padded + 32);
        let v = Helpers.uint256_to_felt(v_uint256);

        if ((v - 27) * (v - 28) != 0) {
            let (output) = alloc();
            return (0, output, GAS_COST_EC_RECOVER, 0);
        }

        let msg_hash = Helpers.bytes_to_uint256(32, input_padded);
        let r = Helpers.bytes_to_uint256(32, input_padded + 32 * 2);
        let s = Helpers.bytes_to_uint256(32, input_padded + 32 * 3);

        // v - 27, see recover_public_key comment
        let (helpers_class) = Kakarot_cairo1_helpers_class_hash.read();
        let (success, recovered_address) = ICairo1Helpers.library_call_recover_eth_address(
            class_hash=helpers_class, msg_hash=msg_hash, r=r, s=s, y_parity=v - 27
        );

        if (success == 0) {
            let (output) = alloc();
            return (0, output, GAS_COST_EC_RECOVER, 0);
        }

        let (output) = alloc();
        memset(output, 0, 12);
        Helpers.split_word(recovered_address, 20, output + 12);

        return (32, output, GAS_COST_EC_RECOVER, 0);
    }

https://github.com/kkrt-labs/kakarot/blob/7411a5520e8a00be6f5243a50c160e66ad285563/src/kakarot/precompiles/ec_recover.cairo#L40

This function does not enforce the valid range for r. It should ensure that r is between 1 and 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140, as explained in the Recommendation section.

PoC

In the following tests, s and v are valid, but r is outside the valid range. On Ethereum, ecrecover returns address(0), but on Kakarot, the system panics, as shown in the output logs.

To run the end-to-end tests correctly, the make test-end-to-end13 command should be used, as defined in the Makefile.

test-end-to-end13: deploy
	uv run pytest tests/end_to_end/Simple/test_ecrecover_revert.py -m "not slow" -s --seed 42	

import pytest
import pytest_asyncio

from kakarot_scripts.utils.kakarot import deploy


@pytest_asyncio.fixture(scope="package")
async def target():
    return await deploy(
        "Simple",
        "TestEcrecoverRevert",
    )



@pytest.mark.asyncio(scope="package")
class Test:

    class TestEcrecoverRevert1:
        async def test_ecrecover_revert1(self, target):
            # r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
            # s = 1
            # v = 27
            addr = await target.call1(115792089237316195423570985008687907852837564279074904382605163141518161494337, 1)
            print("r is max valid value + 1: " + str(addr)) 

    class TestEcrecoverRevert2:
        async def test_ecrecover_revert2(self, target):
            # r = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
            # s = 1
            # v = 27
            addr = await target.call1(115792089237316195423570985008687907853269984665640564039457584007913129639935, 1)
            print("r is big: " + str(addr)) 

pragma solidity ^0.8.0;

contract TestEcrecoverRevert {
    function call1(uint256 _r, uint256 _s) public view returns (address) {
        return ecrecover(bytes32(uint256(0)), 27, bytes32(_r), bytes32(_s));
    }
}

The output log is:

FAILED tests/end_to_end/Simple/test_ecrecover_revert.py::Test::TestEcrecoverRevert1::test_ecrecover_revert1 - starknet_py.net.client_errors.ClientError: Client failed with code 40. Message: Contract error. Data: {'revert_error': "Error at pc=0:49:\nGot an exception while executing a hint: Execution failed. Failure reason: 0x4f7074696f6e3a3a756e77726170206661696c65642e ('Option::unwrap failed.').\nCairo traceback (most recent call last):\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23352)\nUnknown location (pc=0:22085)\nUnknown location (pc=0:21853)\nUnknown location (pc=0:17801)\nUnknown location (pc=0:6002)\n"}
FAILED tests/end_to_end/Simple/test_ecrecover_revert.py::Test::TestEcrecoverRevert2::test_ecrecover_revert2 - starknet_py.net.client_errors.ClientError: Client failed with code 40. Message: Contract error. Data: {'revert_error': "Error at pc=0:49:\nGot an exception while executing a hint: Execution failed. Failure reason: 0x496e76616c696420617267756d656e74 ('Invalid argument').\nCairo traceback (most recent call last):\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23354)\nUnknown location (pc=0:23352)\nUnknown location (pc=0:22085)\nUnknown location (pc=0:21853)\nUnknown location (pc=0:17801)\nUnknown location (pc=0:6002)\n"}

Tools Used

Recommended Mitigation Steps

The following modifications are needed to constraint the valid range of r:

    //.......
    from starkware.cairo.common.uint256 import Uint256, uint256_reverse_endian
+   from starkware.cairo.common.math_cmp import is_not_zero, is_nn
    from starkware.cairo.common.cairo_secp.bigint import bigint_to_uint256
    //........

    func run{
        syscall_ptr: felt*,
        pedersen_ptr: HashBuiltin*,
        range_check_ptr,
        bitwise_ptr: BitwiseBuiltin*,
    }(_address: felt, input_len: felt, input: felt*) -> (
        output_len: felt, output: felt*, gas_used: felt, reverted: felt
    ) {
        alloc_locals;

        let (input_padded) = alloc();
        slice(input_padded, input_len, input, 0, 4 * 32);

        let v_uint256 = Helpers.bytes32_to_uint256(input_padded + 32);
        let v = Helpers.uint256_to_felt(v_uint256);

        if ((v - 27) * (v - 28) != 0) {
            let (output) = alloc();
            return (0, output, GAS_COST_EC_RECOVER, 0);
        }

        let msg_hash = Helpers.bytes_to_uint256(32, input_padded);
        let r = Helpers.bytes_to_uint256(32, input_padded + 32 * 2);
        let s = Helpers.bytes_to_uint256(32, input_padded + 32 * 3);

+       let r_high = r.high;
+       let r_low = r.low;
+
+       if (is_not_zero(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF - r_high) == FALSE) {
+           let (output) = alloc();
+           return (0, output, GAS_COST_EC_RECOVER, 0);
+       } 
+
+       let is_r_high_not_big = is_not_zero(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE - r_high);
+       let is_r_low_big = is_nn(r_low - 0xBAAEDCE6AF48A03BBFD25E8CD0364141);
+       let is_r_not_valid = (1 - is_r_high_not_big) * is_r_low_big;
+       if ( is_r_not_valid != FALSE){
+           let (output) = alloc();
+           return (0, output, GAS_COST_EC_RECOVER, 0);
+       }
+
        // v - 27, see recover_public_key comment
        let (helpers_class) = Kakarot_cairo1_helpers_class_hash.read();
        let (success, recovered_address) = ICairo1Helpers.library_call_recover_eth_address(
            class_hash=helpers_class, msg_hash=msg_hash, r=r, s=s, y_parity=v - 27
        );

        if (success == 0) {
            let (output) = alloc();
            return (0, output, GAS_COST_EC_RECOVER, 0);
        }

        let (output) = alloc();
        memset(output, 0, 12);
        Helpers.split_word(recovered_address, 20, output + 12);

        return (32, output, GAS_COST_EC_RECOVER, 0);
    }

https://github.com/kkrt-labs/kakarot/blob/7411a5520e8a00be6f5243a50c160e66ad285563/src/kakarot/precompiles/ec_recover.cairo#L40

Assessed type

Context

[ClementWalter]

Severity: Medium

Comment: The function does not follow the specs, it will be fixed. Considering the tx reverts, there is no clear attack paths.

[c4-judge]

dmvt marked the issue as partial-50

[c4-judge]

dmvt marked the issue as nullified

[dmvt]

This is a dup of 13 given it's the same fundamental root cause.