RIPEMD-160 fails when (input length & 63) is greater or equal to 55

[c4-bot-3]

Lines of code

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

Vulnerability details

Impact

This leads to the Starknet transaction reverting and can DoS contracts relying on RIPEMD-160.

Additionally, right now, it can be used to drain Kakarot Relayers by sending multiple transactions and making them pay the Starknet fees without any counterpart cost.

Proof of Concept

Root Cause

RIPEMD-160

    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
    ) {
        // ...

        // 3. finish hash
        let (res, _) = finish(res, rsize, new_msg, input_len, 0); <@udit
        // ...
    }
    
	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); <@udit
	    tempvar start = x; <@udit (1)
	
	    // put data into x.
	    let (local len) = uint32_and(dsize, 63); <@udit
	    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); <@udit
	    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); <@udit (2)
	
	    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); <@udit (3)
	    let (res, rsize) = compress(buf, bufsize, arr_x, 16);
	    return (res=res, rsize=rsize);
	}

When input_length & 63 >= 55 (.e.g 57, 125), RIPEMD-160 fails while finalizing the dictionary in (3) due to the start (1) and x (2) pointers being on different memory segments.

Unit Test

Modify the test_ripemd160 unit test :

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=56))
    @settings(max_examples=1)
    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()

Bytecode

Add an entry for the following bytecode in E2E tests
600060006038600060035afa

Test Results / Transaction Results

E           Exception: ./.venv/lib/python3.10/site-packages/starkware/cairo/common/squash_dict.cairo:29:5: Error at pc=0:162:
E           Can only subtract two relocatable values of the same segment (18 != 15).
E               local ptr_diff = dict_accesses_end - dict_accesses;
E               ^*************************************************^
E           Cairo traceback (most recent call last):
E           :20:43: (pc=0:5504)
E               let (hash_len, hash, gas, reverted) = PrecompileRIPEMD160.run(
E                                                     ^**********************^
E           ./src/kakarot/precompiles/ripemd160.cairo:70:24: (pc=0:1702)
E                   let (res, _) = finish(res, rsize, new_msg, input_len, 0);
E                                  ^***************************************^
E           ./src/kakarot/precompiles/ripemd160.cairo:477:5: (pc=0:4586)
E               default_dict_finalize(start, x, 0);
E               ^********************************^
E           ./.venv/lib/python3.10/site-packages/starkware/cairo/common/default_dict.cairo:27:64: (pc=0:300)
E               let (local squashed_dict_start, local squashed_dict_end) = dict_squash(
E                                                                          ^**********^
E           ./.venv/lib/python3.10/site-packages/starkware/cairo/common/dict.cairo:100:31: (pc=0:286)
E               let (squashed_dict_end) = squash_dict(
E                                         ^**********^
E           Falsifying example: test_ripemd160_should_return_correct_hash(
E               self=<test_ripemd160.TestRIPEMD160 object at 0x11b5c92a0>,
E               cairo_run=_factory,
E               msg_bytes=b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00',
E           )

{
	// ...
	  "execution_status": "REVERTED",
	  "revert_reason": "Transaction execution has failed:\n0: Error in the called contract (contract address: 0x00e29882a1fcba1e7e10cad46212257fea5c752a4f9b1b1ec683c503a2cf5c8a, class hash: 0x05400e90f7e0ae78bd02c77cd75527280470e2fe19c54970dd79dc37a9d3645c, selector: 0x015d40a3d6ca2ac30f4031e42be28da9b056fef9bb7357ac5e85627ee876e5ad):\nError at pc=0:4573:\nCairo traceback (most recent call last):\nUnknown location (pc=0:67)\nUnknown location (pc=0:1835)\nUnknown location (pc=0:2478)\nUnknown location (pc=0:3255)\nUnknown location (pc=0:3795)\n\n1: Error in the called contract (contract address: 0x01535b75314d7548981893332ad9bd07681dcd8086b954d479b58ca01a6b446c, class hash: 0x07b2de5e73ff7eb338d76c967dd5aa3f3004574d326b8c1402bb819d4983b8b6, selector: 0x007ec457cd7ed1630225a8328f826a29a327b19486f6b2882b4176545ebdbe3d):\nError at pc=0:22:\nCairo traceback (most recent call last):\nUnknown location (pc=0:273)\nUnknown location (pc=0:259)\n\n2: Error in a library call (contract address: 0x01535b75314d7548981893332ad9bd07681dcd8086b954d479b58ca01a6b446c, class hash: 0x01c8acbb634afbe8e494faba9ca2d8c6ad385372d5bfdd32a88506fffc709707, selector: 0x007ec457cd7ed1630225a8328f826a29a327b19486f6b2882b4176545ebdbe3d):\nError at pc=0:32:\nCairo traceback (most recent call last):\nUnknown location (pc=0:3247)\nUnknown location (pc=0:3180)\nUnknown location (pc=0:2614)\nUnknown location (pc=0:445)\n\n3: Error in the called contract (contract address: 0x079a9fe2bae4aa9585c83099a01fcec05b150d0c17b68055f19d2fbb8f7ed8df, class hash: 0x02b83b926ab0390b2884e99ded27a4cd1bba96cadcef47778d9050d4034dacf3, selector: 0x01df22f179266780b29ce26485abf97cbd909fd15ce74a37b793bcd261f84b14):\nError at pc=0:1034:\nCairo traceback (most recent call last):\nUnknown location (pc=0:26303)\nUnknown location (pc=0:26258)\nUnknown location (pc=0:26090)\nUnknown location (pc=0:24484)\nUnknown location (pc=0:24115)\nUnknown location (pc=0:23612)\nUnknown location (pc=0:23612)\nUnknown location (pc=0:23612)\nUnknown location (pc=0:23612)\nUnknown location (pc=0:23612)\nUnknown location (pc=0:23612)\nUnknown location (pc=0:23612)\nUnknown location (pc=0:23610)\nUnknown location (pc=0:22187)\nUnknown location (pc=0:21916)\nUnknown location (pc=0:18063)\nUnknown location (pc=0:20947)\nUnknown location (pc=0:1172)\nUnknown location (pc=0:1158)\n\nOperation failed: 255:54 - 252:0, can't subtract two relocatable values with different segment indexes\n"
	// ...
}

Recommended Mitigation Steps

Reassign the start pointer.

Assessed type

Error

[ClementWalter]

Severity: Medium

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

[c4-judge]

dmvt marked the issue as unsatisfactory:
Insufficient quality

[imsrybr0]

Hi @dmvt,

I'm not entirely sure why this was invalidated.

The report contains a correct Root Cause analysis outlining exactly when, why and where this is issue is rising as well as Tests to reproduce it and mitigation steps to fix it.

Can you please clarify what's missing ?

Thank you

[dmvt]

My apologies. Most of your comments were collapsed and for some reason I didn't see that. May have been a formatting issue with the extension.

[c4-judge]

dmvt changed the severity to 2 (Med Risk)

[imsrybr0]

Hi @dmvt,

My bad, will expand the code sections by default in future reports.

Thank you

[c4-judge]

dmvt removed the grade

[c4-judge]

dmvt marked the issue as duplicate of #120

[c4-judge]

dmvt marked the issue as satisfactory