Three valid signatures for the same message

[c4-bot-10]

Lines of code

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

Vulnerability details

Impact

On Ethereum, it's possible to create two different valid signatures for the same message (known as ECDSA Signature Malleability). However, on Kakarot, you can create three different valid signatures for the same message. This happens because, on Ethereum, if the value of s is higher than the maximum valid range, it returns address(0). On Kakarot, in this case, it returns a valid address.

Proof of Concept

If r and v are in the valid range, and s is between 1 and secp256k1n, the ecrecover function behaves the same on both Ethereum and Kakarot.

• On Ethereum, if the value of s is higher than secp256k1n, it returns address(0).
• On Kakarot, if the value of s is higher than secp256k1n, it returns an address equivalent to s + secp256k1n.

Here's an example for better clarity. The ecrecover function for the following inputs will return the same result 0x992FEaf0E360bffaeAcf57c28D2a3F5059Fe0982:

• On Ethereum:

  • input1: r = 1, v = 27, s = 2
  • input2: r = 1, v = 28, s = secp256k1n - 2 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD036413F

• On Kakarot:

  • input1: r = 1, v = 27, s = 2
  • input2: r = 1, v = 28, s = secp256k1n - 2 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD036413F
  • input3: r = 1, v = 27, s = secp256k1n + 2 = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364143

While inputs 1 and 2 behave as expected, input 3 highlights the problem. With input 3, Ethereum's ecrecover returns address(0), but Kakarot returns the same result as input1 and input2.

This shows that a malleability attack on Kakarot can be done in two ways, whereas on Ethereum, it can only be done in one.

In simple terms, on Ethereum, a malleability attack can be done by changing the v from 27 to 28 (or vice versa) and swapping s with secp256k1n - s:

• r, s, v
• r, secp256k1n - s, v = {27 -> 28, 28 -> 27}

On Kakarot, the malleability attack can be done in two ways: either by changing s to secp256k1n + s (as long as it's not larger than 2**256 - 1) or using the same method as Ethereum by changing the v and swapping s with secp256k1n - s:

• r, s, v
• r, secp256k1n - s, v = {27 -> 28, 28 -> 27}
  OR:
• r, s, v
• r, secp256k1n + s, v

The value of s needs to be limited in the ec_recover::run function to make sure it's within the valid range.

    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

PoC

In the following test, three different combinations of (r, s, v) are provided as parameters to the ecrecover function, and the result for all of them is the same.

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

test-end-to-end14: deploy
	uv run pytest tests/end_to_end/Simple/test_ecrecover_wrong.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",
        "TestEcrecoverWrong",
    )

# 0xfffFFFFFFFFFFFFFFFFFFFFFFFFFFFFebaaedce6af48a03bbfd25e8cd0364140

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


    class TestEcrecoverWrong1:
        async def test_ecrecover_wrong1(self, target):
            # r = 1
            # s = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364143 = secp256k1n + 2
            # v = 27
            addr = await target.call1(1, 115792089237316195423570985008687907852837564279074904382605163141518161494339, 27)
            print("s is secp256k1n + 2, v is 27: " + str(addr)) 

            
    class TestEcrecoverWrong2:
        async def test_ecrecover_wrong2(self, target):
            # r = 1
            # s = 2
            # v = 27
            addr = await target.call1(1, 2, 27)
            print("s is 2, v is 27: " + str(addr)) 

    class TestEcrecoverWrong3:
        async def test_ecrecover_wrong3(self, target):
            # r = 1
            # s = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD036413F = secp256k1n - 2
            # v = 28
            addr = await target.call1(1, 115792089237316195423570985008687907852837564279074904382605163141518161494335, 28)
            print("s is secp256k1n - 2, v is 28: " + str(addr))             

pragma solidity ^0.8.0;

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

The output log is:

INFO:kakarot_scripts.utils.kakarot:⏳ Deploying TestEcrecoverWrong
INFO:kakarot_scripts.utils.kakarot:✅ TestEcrecoverWrong deployed at: 0x9fE46736679d2D9a65F0992F2272dE9f3c7fa6e0
s is secp256k1n + 2, v is 27: 0x992FEaf0E360bffaeAcf57c28D2a3F5059Fe0982
.s is 2, v is 27: 0x992FEaf0E360bffaeAcf57c28D2a3F5059Fe0982
.s is secp256k1n - 2, v is 28: 0x992FEaf0E360bffaeAcf57c28D2a3F5059Fe0982

Tools Used

Recommended Mitigation Steps

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

    //.......
    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 s_high = s.high;
+       let s_low = s.low;
+
+       if (is_not_zero(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF - s_high) == FALSE) {
+           let (output) = alloc();
+           return (0, output, GAS_COST_EC_RECOVER, 0);
+       } 
+
+       let is_s_high_not_big = is_not_zero(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE - s_high);
+       let is_s_low_big = is_nn(s_low - 0xBAAEDCE6AF48A03BBFD25E8CD0364141);
+       let is_s_not_valid = (1 - is_s_high_not_big) * is_s_low_big;
+       if ( is_s_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: High

Comment: Agreed

[c4-judge]

dmvt marked the issue as selected for report