RIPEMD160 precompile crashes with a Cairo exception for some input lengths

[howlbot-integration]

Lines of code

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

Vulnerability details

Calling the RIPEMD160 precompile with certain input lengths results in a Cairo exception. As a result, some L2 smart contracts that use this precompile cannot be executed.

The bug seems to occur in line 477 of the precompile. The relevant code:

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;

    (...)
    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 lower part of the code is reached for some input lengths. Note that x is redefined with the line:

    let (x) = default_dict_new(0);

However, start still points to the first element of the original dict x initialized at the start of the function. Consequently, squashing the dict with default_dict_finalize(start, x, 0) will fail because start and x point to different segments.

Proof of Concept

The issue can be verified by running the following Solidity contract as an e2e-test.:

contract RIPEMDTest {

    function computeRipemd160(bytes memory data) public view returns (bytes20) {
        bytes20 result;
        assembly {
            // Load the free memory pointer
            let ptr := mload(0x40)

            // Get the length of the input data
            let len := mload(data)

            // Call the RIPEMD-160 precompile (address 0x03)
            let success := staticcall(
                gas(),           // Forward all available gas
                0x03,            // Address of RIPEMD-160 precompile
                add(data, 32),   // Input data starts after the length field (32 bytes)
                len,             // Length of the input data
                ptr,             // Output will be written to ptr
                32               // The precompile writes 32 bytes (even though RIPEMD-160 outputs 20 bytes)
            )

            // Check if the call was successful
            if iszero(success) {
                revert(0, 0)
            }

            // Read the first 20 bytes of the output (RIPEMD-160 outputs 20 bytes)
            result := mload(ptr)
        }
        return result;
    }

    function hashInputLength20() external view returns (bytes20) {
        bytes memory inputData = new bytes(20);

        for (uint256 i = 0; i < 20; i++) {
            inputData[i] = 0x61;
        }

        return computeRipemd160(inputData);
    }

    function hashInputLength32() external view returns (bytes20) {
        bytes memory inputData = new bytes(55);
        for (uint256 i = 0; i < 32; i++) {
            inputData[i] = 0x61;
        }
        return computeRipemd160(inputData);
    }
}

While calling hashInputLength20() returns the correct result, hashInputLength32() will result in a failed test:

FAILED tests/end_to_end/Berndt/test_berndt.py::TestBerndt::Test1::test_berndt - starknet_py.net.client_errors.ClientError: Client failed with code 40. Message: Contract error. Data: {'revert_error': "Error at pc=0:1034:\nOperation failed: 714:54 - 711:0, can't subtract two relocatable values with different segment indexes\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:23352)\nUnknown location (pc=0:22085)\nUnknown location (pc=0:21859)\nUnknown location (pc=0:18006)\nUnknown location (pc=0:20890)\nUnknown location (pc=0:1172)\nUnknown location (pc=0:1158)\n"}

In the ordinary EVM, the same function returns the result:

bytes20: 0x0000000000000000000000004a6747d1c9fe21fc

Additionally, the following Cairo test reproduces the issue:

import pytest
from Crypto.Hash import RIPEMD160
from hypothesis import given, settings
from hypothesis.strategies import binary


@pytest.mark.asyncio
@pytest.mark.slow
class TestRIPEMD160:
    @given(msg_bytes=binary(min_size=56, max_size=63))
    @settings(max_examples=3)
    async def test_ripemd160_should_return_correct_hash(self, cairo_run, msg_bytes):
        precompile_hash = cairo_run("test__ripemd160", msg=list(msg_bytes))

        # Hash with RIPEMD-160 to compare with precompile result
        ripemd160_crypto = RIPEMD160.new()
        ripemd160_crypto.update(msg_bytes)
        expected_hash = ripemd160_crypto.hexdigest()

        assert expected_hash.rjust(64, "0") == bytes(precompile_hash).hex()

This will crash with the exception:

E           Exception: /Users/bernhardmueller/Library/Caches/pypoetry/virtualenvs/kakarot-UuVS5Smv-py3.10/lib/python3.10/site-packages/starkware/cairo/common/squash_dict.cairo:29:5: Error at pc=0:1428:
E           Can only subtract two relocatable values of the same segment (16 != 13).

Recommended Mitigation Steps

Set the pointer start to the correct value. It is also very important to finalize the previously initialized dict x as the prover can cheat otherwise.

Double-check the invocation path of the precompile exec_precompile exec_precompile(), and add end-to-end tests for all precompiles to make sure that they work as expected when called from L2.

Assessed type

Error

[ClementWalter]

Severity: Medium

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

[c4-judge]

dmvt changed the severity to 2 (Med Risk)

[c4-judge]

dmvt marked the issue as selected for report