RIPEMD160 fails if (length of calldata) % 64 is in the range of 55 to 63

[c4-bot-10]

Lines of code

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

Vulnerability details

Impact

Consider the ripemd160.cairo::finish which is called while calculating RIPEMD160 ( interpreter.cairo::exec_opcode -> precompiles.cairo::exec_precompile -> ripemd160.cairo::run -> ripemd160.cairo::finish ):

// puts bytes from data into X and pad out; appends length
// and finally, compresses the last block(s)
// note: length in bits == 8 * (dsize + 2^32 mswlen).
// note: there are (dsize mod 64) bytes left in data.
func finish{range_check_ptr, bitwise_ptr: BitwiseBuiltin*}(
    buf: felt*, bufsize: felt, data: felt*, dsize: felt, mswlen: felt
) -> (res: felt*, rsize: felt) {
    alloc_locals;
    let (x) = default_dict_new(0);
->  tempvar start = x;

    // put data into x.
    let (local len) = uint32_and(dsize, 63);
    absorb_data{dict_ptr=x}(data, len, 0);

    // append the bit m_n == 1.
    let (index_4, _) = unsigned_div_rem(dsize, 4);
    let (local index) = uint32_and(index_4, 15);
    let (old_val) = dict_read{dict_ptr=x}(index);
    let (local ba_3) = uint32_and(dsize, 3);
    let (factor) = uint32_add(8 * ba_3, 7);
    let (tmp) = pow2(factor);
    let (local val) = uint32_xor(old_val, tmp);
    dict_write{dict_ptr=x}(index, val);

    // length goes to next block.
    let (val) = uint32_mul(dsize, 8);
    let (pow2_29) = pow2(29);
    let (factor, _) = unsigned_div_rem(dsize, pow2_29);
    let len_8 = mswlen * 8;
    let (val_15) = uint32_or(factor, len_8);

    let next_block = is_nn_le(55, len);
    if (next_block == FALSE) {
        dict_write{dict_ptr=x}(14, val);
        dict_write{dict_ptr=x}(15, val_15);

        let (local arr_x: felt*) = alloc();
        dict_to_array{dict_ptr=x}(arr_x, 16);
        default_dict_finalize(start, x, 0);
        let (res, rsize) = compress(buf, bufsize, arr_x, 16);
        return (res=res, rsize=rsize);
    }
    let (local arr_x: felt*) = alloc();
    dict_to_array{dict_ptr=x}(arr_x, 16);
    let (buf, bufsize) = compress(buf, bufsize, arr_x, 16);
    // reset dict to all 0.
    let (x) = default_dict_new(0);

    dict_write{dict_ptr=x}(14, val);
    dict_write{dict_ptr=x}(15, val_15);

    let (local arr_x: felt*) = alloc();
    dict_to_array{dict_ptr=x}(arr_x, 16);
->  default_dict_finalize(start, x, 0);
    let (res, rsize) = compress(buf, bufsize, arr_x, 16);
    return (res=res, rsize=rsize);
}

The last third line default_dict_finalize(start, x, 0); will throw error as the start was initialized on third line for different memory segment x. And this line will be executed if (length of calldata) % 64 is in the range of 55 to 63.

Proof of Concept

Consider the following code:

#define macro MAIN() = takes(0) returns(0) {
    0x20 // retSize
    0x00 // retOffset
    0x37 // argSize
    0x00 // argOffset
    0x00 // value
    0x03 // address
    0xffffff // gas
    call
}

Save the above code in a file name precompile.huff ( You can refer Installing Huff, if you don't have huff installed ).

The above code will call the precompile ripemd160 with calldata length of 0x37 or 55 bytes ( as 55 % 64 = 55 ).

The above code can be converted to bytecode using the following command:

huffc precompile.huff --bytecode

The output will be:

600e8060093d393df360205f60375f5f600362fffffff1

The runtime code is ( after removing the first few bytes which are responsible for deployment ):

60205f60375f5f600362fffffff1

Add the following cairo file named test_kakarot_precompile.cairo in kakarot/tests/src/kakarot folder:

%lang starknet

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

from kakarot.library import Kakarot
from kakarot.model import model

func eth_call{
    syscall_ptr: felt*, pedersen_ptr: HashBuiltin*, range_check_ptr, bitwise_ptr: BitwiseBuiltin*
}() -> (model.EVM*, model.State*, felt, felt) {
    tempvar origin;
    tempvar to: model.Option;
    tempvar gas_limit;
    tempvar gas_price;
    tempvar nonce;
    let (value_ptr) = alloc();
    tempvar data_len: felt;
    let (data) = alloc();
    tempvar access_list_len: felt;
    let (access_list) = alloc();

    %{
        from kakarot_scripts.utils.uint256 import int_to_uint256

        ids.origin = program_input.get("origin", 0)
        ids.to.is_some = int(bool(program_input.get("to") is not None))
        ids.to.value = program_input.get("to") or 0
        ids.gas_limit = program_input.get("gas_limit", int(2**63 - 1))
        ids.gas_price = program_input.get("gas_price", 0)
        ids.nonce = program_input.get("nonce", 0)
        segments.write_arg(ids.value_ptr, int_to_uint256(program_input.get("value", 0)))
        data = bytes.fromhex(program_input.get("data", "").replace("0x", ""))
        ids.data_len = len(data)
        segments.write_arg(ids.data, list(data))
        ids.access_list_len = 0
    %}

    let (evm, state, gas_used, required_gas) = Kakarot.eth_call(
        nonce=nonce,
        origin=origin,
        to=to,
        gas_limit=gas_limit,
        gas_price=gas_price,
        value=cast(value_ptr, Uint256*),
        data_len=data_len,
        data=data,
        access_list_len=access_list_len,
        access_list=access_list,
    );

    return (evm, state, gas_used, required_gas);
}

Also add the following python test file named test_kakarot_precompile.py in the same folder i.e kakarot/tests/src/kakarot folder:

from tests.utils.syscall_handler import SyscallHandler, parse_state

class TestKakarotPrecompile:           
        @SyscallHandler.patch("IAccount.is_valid_jumpdest", lambda addr, data: [1])
        @SyscallHandler.patch("IAccount.get_code_hash", lambda addr, data: [0x1, 0x1])
        def test_precompile(self, cairo_run):
            evm_address = "0xa94f5374fce5edbc8e2a8697c15331677e6ebf0b"
            origin = int(evm_address, 16)
            contract_address = "0x000000000000000000000000000000ca1100f022"
            initial_state = {
                contract_address: {
                    "code": "60205f60375f5f600362fffffff1",
                    "storage": {},
                    "balance": 0,
                    "nonce": 0,
                }
            }
            with SyscallHandler.patch_state(parse_state(initial_state)):
                res = cairo_run("eth_call",
                    origin=origin,
                    to=int(contract_address, 16),
                    gas_limit=int("0xfffffff", 16),
                    gas_price=int("0x80", 16),
                    value=0,
                    nonce=0,
                    )
                is_reverted = res[0]["reverted"] != 0
                assert is_reverted == 0

Now run the test using the following command:

cd kakarot/
uv run pytest -s "./tests/src/kakarot/test_kakarot_precompile.py::TestKakarotPrecompile::test_precompile"

The test will fail due Can only subtract two relocatable values of the same segment (235 != 232) error.

Tools Used

Python test suite

Recommended Mitigation Steps

It can be fixed by updating the ripemd160.cairo::finish function as follows:

// puts bytes from data into X and pad out; appends length
// and finally, compresses the last block(s)
// note: length in bits == 8 * (dsize + 2^32 mswlen).
// note: there are (dsize mod 64) bytes left in data.
func finish{range_check_ptr, bitwise_ptr: BitwiseBuiltin*}(
    buf: felt*, bufsize: felt, data: felt*, dsize: felt, mswlen: felt
) -> (res: felt*, rsize: felt) {
    alloc_locals;
    let (x) = default_dict_new(0);
    tempvar start = x;

    // put data into x.
    let (local len) = uint32_and(dsize, 63);
    absorb_data{dict_ptr=x}(data, len, 0);

    // append the bit m_n == 1.
    let (index_4, _) = unsigned_div_rem(dsize, 4);
    let (local index) = uint32_and(index_4, 15);
    let (old_val) = dict_read{dict_ptr=x}(index);
    let (local ba_3) = uint32_and(dsize, 3);
    let (factor) = uint32_add(8 * ba_3, 7);
    let (tmp) = pow2(factor);
    let (local val) = uint32_xor(old_val, tmp);
    dict_write{dict_ptr=x}(index, val);

    // length goes to next block.
    let (val) = uint32_mul(dsize, 8);
    let (pow2_29) = pow2(29);
    let (factor, _) = unsigned_div_rem(dsize, pow2_29);
    let len_8 = mswlen * 8;
    let (val_15) = uint32_or(factor, len_8);

    let next_block = is_nn_le(55, len);
    if (next_block == FALSE) {
        dict_write{dict_ptr=x}(14, val);
        dict_write{dict_ptr=x}(15, val_15);

        let (local arr_x: felt*) = alloc();
        dict_to_array{dict_ptr=x}(arr_x, 16);
        default_dict_finalize(start, x, 0);
        let (res, rsize) = compress(buf, bufsize, arr_x, 16);
        return (res=res, rsize=rsize);
    }
    let (local arr_x: felt*) = alloc();
    dict_to_array{dict_ptr=x}(arr_x, 16);
    let (buf, bufsize) = compress(buf, bufsize, arr_x, 16);
    // reset dict to all 0.
    let (x) = default_dict_new(0);
+    tempvar start = x;

    dict_write{dict_ptr=x}(14, val);
    dict_write{dict_ptr=x}(15, val_15);

    let (local arr_x: felt*) = alloc();
    dict_to_array{dict_ptr=x}(arr_x, 16);
    default_dict_finalize(start, x, 0);
    let (res, rsize) = compress(buf, bufsize, arr_x, 16);
    return (res=res, rsize=rsize);
}

Assessed type

Error

[ClementWalter]

Severity: Medium

Comment: Ok but asset are not directly at risks considering that the tx will revert.

[c4-judge]

dmvt changed the severity to 2 (Med Risk)

[c4-judge]

dmvt marked issue #120 as primary and marked this issue as a duplicate of 120

[c4-judge]

dmvt marked the issue as satisfactory