RIPEMD-160 precompile yields wrong hashes for large set of inputs due to off-by-one error

[c4-bot-6]

Lines of code

https://github.com/kkrt-labs/kakarot/blob/a4c45215f7fd5cdd9fbbfd11196a9a787c6468df/cairo_zero/kakarot/precompiles/ripemd160.cairo#L455

Vulnerability details

The RIPEMD-160 digest integrates the input data with one additional block including the message length.

If we look at the Cairo code that achieves this:

File: ripemd160.cairo
455:     let next_block = is_nn_le(55, len);
456:     if (next_block == FALSE) {
457:         dict_write{dict_ptr=x}(14, val);
458:         dict_write{dict_ptr=x}(15, val_15);
459: 
460:         let (local arr_x: felt*) = alloc();
461:         dict_to_array{dict_ptr=x}(arr_x, 16);
462:         default_dict_finalize(start, x, 0);
463:         let (res, rsize) = compress(buf, bufsize, arr_x, 16);
464:         return (res=res, rsize=rsize);
465:     }
466:     let (local arr_x: felt*) = alloc();
467:     dict_to_array{dict_ptr=x}(arr_x, 16);
468:     let (buf, bufsize) = compress(buf, bufsize, arr_x, 16);

... we see that the if (next_block == false) executes one block of code in case len >= 55, and the other otherwise.

If we compare this check with the equivalent implementation in Go (used by Geth), for example:

	if tc%64 < 56 {
		d.Write(tmp[0 : 56-tc%64])
	} else {
		d.Write(tmp[0 : 64+56-tc%64])
	}

we see that this time, the selection is made with len < 56 as discriminator; if we imagine swapping the if and the else blocks of the Go implementation, the condition becomes len >= 56.

So for the edge case of len == 55, Kakarot and Geth will take different actions, which, as shown in the PoC, results in differing hashes. len here represents the length of the input modulo 64, hence the RIPEMD-160 precompile will yield wrong outputs for inputs of length 55 + k*64.

Because this precompile is a cryptographic hash function, it can be used in many ways by EVM applications, including access control on funds.

Proof of Concept

To prove the point, the following test can be added to the test_ripemd160.py unit test suite:

    async def test_ripemd160_on_55_length_input(self, cairo_run):
        msg_bytes = bytes("abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmomnopnopq", "ascii")
        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()

... which yields the following output:

>       assert expected_hash.rjust(64, "0") == bytes(precompile_hash).hex()
E       AssertionError: assert '000000000000...65c8fd54fbafd' == '000000000000...169718d24abaf'
E         
E         - 000000000000000000000000578b4715e07320701e0715dc640169718d24abaf
E         + 000000000000000000000000df3166bed54ffac595c474af28465c8fd54fbafd

tests/src/kakarot/precompiles/test_ripemd160.py:19: AssertionError

Recommended Mitigation Steps

Change the check at L455 to is_nn_le(56, len).

Assessed type

Other

[ClementWalter]

Severity: High

Comment: Ok dup #35

[c4-judge]

dmvt marked the issue as selected for report