CALL_STIPEND is injected in gas left directly when a call has value

[c4-bot-10]

Lines of code

https://github.com/kkrt-labs/kakarot/blob/7411a5520e8a00be6f5243a50c160e66ad285563/src/kakarot/interpreter.cairo#L820-L1040
https://github.com/kkrt-labs/kakarot/blob/7411a5520e8a00be6f5243a50c160e66ad285563/src/kakarot/instructions/system_operations.cairo#L339-L466
https://github.com/kkrt-labs/kakarot/blob/7411a5520e8a00be6f5243a50c160e66ad285563/src/kakarot/interpreter.cairo#L820-L1040

Vulnerability details

Impact

This leads to wrong estimates as the gas required ends up being lower than what's really needed.

Proof of Concept

Interpreter

    func execute{
        syscall_ptr: felt*,
        pedersen_ptr: HashBuiltin*,
        range_check_ptr,
        bitwise_ptr: BitwiseBuiltin*,
    }(
        env: model.Environment*,
        address: model.Address*,
        is_deploy_tx: felt,
        bytecode_len: felt,
        bytecode: felt*,
        calldata_len: felt,
        calldata: felt*,
        value: Uint256*,
        gas_limit: felt,
        access_list_len: felt,
        access_list: felt*,
    ) -> (model.EVM*, model.Stack*, model.Memory*, model.State*, felt, felt) {
        // ...

        with stack, memory, state {
            let evm = run(evm);
        }

        let required_gas = gas_limit - evm.gas_left; <@udit
        let (max_refund, _) = unsigned_div_rem(required_gas, 5);
        let is_max_refund_le_gas_refund = is_nn(evm.gas_refund - max_refund);
        tempvar gas_refund = is_max_refund_le_gas_refund * max_refund + (
            1 - is_max_refund_le_gas_refund
        ) * evm.gas_refund;

        let total_gas_used = required_gas - gas_refund; <@udit

        // ...

        return (evm, stack, memory, state, total_gas_used, required_gas); <@udit
    }

System Operations

    func exec_call{
        syscall_ptr: felt*,
        pedersen_ptr: HashBuiltin*,
        range_check_ptr,
        bitwise_ptr: BitwiseBuiltin*,
        stack: model.Stack*,
        memory: model.Memory*,
        state: model.State*,
    }(evm: model.EVM*) -> model.EVM* {
        // ...

        // 2. Gas
        // Memory expansion cost
        let memory_expansion = Gas.max_memory_expansion_cost(
            memory.words_len, args_offset, args_size, ret_offset, ret_size
        );

        if (memory_expansion.cost == Gas.MEMORY_COST_U32) {
            let evm = EVM.out_of_gas(evm, memory_expansion.cost);
            return evm;
        }

        // Access gas cost. The account is marked as warm in the `generic_call` function,
        // which performs a `get_account`.
        let is_account_warm = State.is_account_warm(to);
        tempvar access_gas_cost = is_account_warm * Gas.WARM_ACCESS + (1 - is_account_warm) *
            Gas.COLD_ACCOUNT_ACCESS;

        // Create gas cost
        let is_account_alive = State.is_account_alive(to);
        tempvar is_value_non_zero = is_not_zero(value.low) + is_not_zero(value.high);
        tempvar is_value_non_zero = is_not_zero(is_value_non_zero);
        let create_gas_cost = (1 - is_account_alive) * is_value_non_zero * Gas.NEW_ACCOUNT;

        // Transfer gas cost
        let transfer_gas_cost = is_value_non_zero * Gas.CALL_VALUE;

        // Charge the fixed cost of the extra_gas + memory expansion
        tempvar extra_gas = access_gas_cost + create_gas_cost + transfer_gas_cost;
        let evm = EVM.charge_gas(evm, extra_gas + memory_expansion.cost); <@udit (1)

        let gas = Gas.compute_message_call_gas(gas_param, evm.gas_left);

        // Charge the fixed message call gas
        let evm = EVM.charge_gas(evm, gas);
        if (evm.reverted != FALSE) {
            // This EVM's stack will not be used anymore, since it reverted - no need to pop the
            // last remaining 2 values ret_offset and ret_size.
            return evm;
        }

        // Operation
        tempvar memory = new model.Memory(
            memory.word_dict_start, memory.word_dict, memory_expansion.new_words_len
        );
        if (evm.message.read_only * is_value_non_zero != FALSE) {
            // No need to pop
            let (revert_reason_len, revert_reason) = Errors.stateModificationError();
            let evm = EVM.stop(evm, revert_reason_len, revert_reason, Errors.EXCEPTIONAL_HALT);
            return evm;
        }
        
        tempvar gas_with_stipend = gas + is_value_non_zero * Gas.CALL_STIPEND; <@udit

        let sender = State.get_account(call_sender);
        let (sender_balance_lt_value) = uint256_lt([sender.balance], [value]);
        tempvar is_max_depth_reached = Helpers.is_zero(
            Constants.STACK_MAX_DEPTH - evm.message.depth
        );
        tempvar is_call_invalid = sender_balance_lt_value + is_max_depth_reached; <@udit
        if (is_call_invalid != FALSE) { <@udit
            // Requires popping the returndata offset and size before pushing 0
            Stack.pop_n(2);
            Stack.push_uint128(0);
            let (return_data) = alloc();
            tempvar evm = new model.EVM(
                message=evm.message,
                return_data_len=0,
                return_data=return_data,
                program_counter=evm.program_counter,
                stopped=FALSE,
                gas_left=evm.gas_left + gas_with_stipend, <@udit
                gas_refund=evm.gas_refund,
                reverted=FALSE,
            );
            return evm;
        }

        let child_evm = CallHelper.generic_call(
            evm,
            gas=gas_with_stipend, <@udit
            value=value,
            caller=call_sender,
            to=to,
            code_address=to,
            is_staticcall=FALSE,
            args_offset=args_offset,
            args_size=args_size,
            ret_offset=ret_offset,
            ret_size=ret_size,
        );
        // ...
    }
    
    func exec_callcode{
        syscall_ptr: felt*,
        pedersen_ptr: HashBuiltin*,
        range_check_ptr,
        bitwise_ptr: BitwiseBuiltin*,
        stack: model.Stack*,
        memory: model.Memory*,
        state: model.State*,
    }(evm: model.EVM*) -> model.EVM* {
        // ...
        // Gas
        let memory_expansion = Gas.max_memory_expansion_cost(
            memory.words_len, args_offset, args_size, ret_offset, ret_size
        );

        if (memory_expansion.cost == Gas.MEMORY_COST_U32) {
            let evm = EVM.out_of_gas(evm, memory_expansion.cost);
            return evm;
        }

        // Access gas cost. The account is marked as warm in the `is_account_alive` instruction,
        // which performs a `get_account`.
        let is_account_warm = State.is_account_warm(code_address);
        tempvar access_gas_cost = is_account_warm * Gas.WARM_ACCESS + (1 - is_account_warm) *
            Gas.COLD_ACCOUNT_ACCESS;

        tempvar is_value_non_zero = is_not_zero(value.low) + is_not_zero(value.high);
        tempvar is_value_non_zero = is_not_zero(is_value_non_zero);
        let transfer_gas_cost = is_value_non_zero * Gas.CALL_VALUE;

        let extra_gas = access_gas_cost + transfer_gas_cost;
        let evm = EVM.charge_gas(evm, extra_gas + memory_expansion.cost); <@udit
        if (evm.reverted != FALSE) {
            return evm;
        }

        let gas = Gas.compute_message_call_gas(gas_param, evm.gas_left);
        let evm = EVM.charge_gas(evm, gas);
        if (evm.reverted != FALSE) {
            return evm;
        }
        
        tempvar gas_with_stipend = gas + is_value_non_zero * Gas.CALL_STIPEND;

        // Operation
        tempvar memory = new model.Memory(
            memory.word_dict_start, memory.word_dict, memory_expansion.new_words_len
        );
        let sender = State.get_account(call_sender);
        let (sender_balance_lt_value) = uint256_lt([sender.balance], [value]);
        tempvar is_max_depth_reached = Helpers.is_zero(
            Constants.STACK_MAX_DEPTH - evm.message.depth
        );
        tempvar is_call_invalid = sender_balance_lt_value + is_max_depth_reached; <@udit
        if (is_call_invalid != FALSE) { <@udit
            // Requires popping the returndata offset and size before pushing 0
            Stack.pop_n(2);
            Stack.push_uint128(0);
            let (return_data) = alloc();
            tempvar evm = new model.EVM(
                message=evm.message,
                return_data_len=0,
                return_data=return_data,
                program_counter=evm.program_counter,
                stopped=FALSE,
                gas_left=evm.gas_left + gas_with_stipend, <@udit
                gas_refund=evm.gas_refund,
                reverted=FALSE,
            );
            return evm;
        }
        
        let child_evm = CallHelper.generic_call(
            evm,
            gas=gas_with_stipend, <@udit
            value=value,
            caller=call_sender,
            to=call_sender,
            code_address=code_address,
            is_staticcall=FALSE,
            args_offset=args_offset,
            args_size=args_size,
            ret_offset=ret_offset,
            ret_size=ret_size,
        );
        
        // ...
    }

ETH RPC

@view
func eth_estimate_gas{
    syscall_ptr: felt*, pedersen_ptr: HashBuiltin*, range_check_ptr, bitwise_ptr: BitwiseBuiltin*
}(
    nonce: felt,
    origin: felt,
    to: model.Option,
    gas_limit: felt,
    gas_price: felt,
    value: Uint256,
    data_len: felt,
    data: felt*,
    access_list_len: felt,
    access_list: felt*,
) -> (return_data_len: felt, return_data: felt*, success: felt, required_gas: felt) {
    alloc_locals;

    Helpers.assert_view_call();

    let fp_and_pc = get_fp_and_pc();
    local __fp__: felt* = fp_and_pc.fp_val;
    let (evm, state, _, gas_required) = Kakarot.eth_call( <@udit
        nonce,
        origin,
        to,
        gas_limit,
        gas_price,
        &value,
        data_len,
        data,
        access_list_len,
        access_list,
    );
    let is_reverted = is_not_zero(evm.reverted);
    return (evm.return_data_len, evm.return_data, 1 - is_reverted, gas_required); <@udit
}

When a CALL / CALLCODE transfer value, a call stipend is added to guarantee that the fallback function of the receiver can be called.

The problem here is how it is added, directly injected in the gas left and making it seem like the operation requires less gas than what's actually need.

For instance, if we consider a simple CALL where an existing sender account doesn't have enough balance to cover the value of the transfer for example and assuming an initial gas limit of 11600 :

• 11600 gas will be charged in (1) (.i.e WARM_ACCESS + CALL_VALUE = 2600 + 9000)
• Since the call is not valid, 2300 (.i.e CALL_STIPED gas) will be injected directly into the gas left
• The gas_required will be equal to gas_limit - gas_left = 11600 - 2300 = 9300
• And the gas_used will be equal to gas_required - gas_refund = 9300 = 9300

So if we were to use the estimate that will be provided for this call (.i.e 9300, the gas_required) to execute it, the execution will fail because it will be short 2300 gas when charging gas in (1) since it requires 11600.

Bytecode

Try deploying the following bytecode :
5f5f5f5f600160ff5af1

Transaction Results

❯ cast receipt 0xfcd430c15a66603aecb929e9dfc4ef588b1f5bde5bcae6b366d50856532e018e --rpc-url localhost:3030

blockHash               0x06c8784dec65dc81448194cf0037fcf708286503b0074e2736fa183176b851cf
blockNumber             1262
contractAddress         0x21432F2F86d056D1F4Ee99eC81758042C9588D03
cumulativeGasUsed       87496
effectiveGasPrice       2
from                    0xf39Fd6e51aad88F6F4ce6aB8827279cffFb92266
gasUsed                 87496
logs                    []
logsBloom               0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
root
status                  0 (failed)
transactionHash         0xfcd430c15a66603aecb929e9dfc4ef588b1f5bde5bcae6b366d50856532e018e
transactionIndex        0
type                    2
blobGasPrice
blobGasUsed
authorizationList
revertReason            out of gas

Recommended Mitigation Steps

The call stipend needs to be treated as a refund but logic to handle refunds at the end of calls will be needed.

Assessed type

Other

[ClementWalter]

Severity: Invalid

Comment: Invalid; the gas estimation is done by the RPC in all cases. While gas_required does not fully reflect the actual required gas for the execution, it returns a heuristic corresponding to gas_limit - gas_left. No funds at risk, no exploit path possible

[c4-judge]

dmvt marked the issue as unsatisfactory:
Invalid

[imsrybr0]

Hi @dmvt,

I believe this is a valid issue.

Comment: Invalid; the gas estimation is done by the RPC in all cases. While gas_required does not fully reflect the actual required gas for the execution, it returns a heuristic corresponding to gas_limit - gas_left. No funds at risk, no exploit path possible

• Yes, gas estimation is done by the RPC in all cases.
• However, the RPC (Out Of Scope) calls the eth_estimate_gas on the Kakarot contract (In Scope)
• Yes, the eth_estimate_gas returns the gas_required which is the gas_limit - gas_left
• That estimate is incorrect as gas left includes the CALL_STIPEND which makes it seem like less gas was consumed by the operation.

For the bytecode mentioned in this report :

Gas estimate

• EVM : 89794n
• Kakarot EVM : 87496n

Gas Consumed using respective estimates

• EVM : 87496n
• Kakarot EVM : 87496n

Transaction Status using respective estimates

• EVM : Success
• Kakarot EVM : Reverted (Out of Gas)

Trace Diff using EVM estimate for both

EVM on the left, Kakarot EVM on the right

[								[
  {								  {
    "pc": 0,							    "pc": 0,
    "op": "PUSH0",						    "op": "PUSH0",
    "gas": 36616,						    "gas": 36616,
    "gasCost": 2,						    "gasCost": 2,
    "depth": 1,							    "depth": 1,
    "stack": []							    "stack": []
  },								  },
  {								  {
    "pc": 1,							    "pc": 1,
    "op": "PUSH0",						    "op": "PUSH0",
    "gas": 36614,						    "gas": 36614,
    "gasCost": 2,						    "gasCost": 2,
    "depth": 1,							    "depth": 1,
    "stack": [							    "stack": [
      "0x0"							      "0x0"
    ]								    ]
  },								  },
  {								  {
    "pc": 2,							    "pc": 2,
    "op": "PUSH0",						    "op": "PUSH0",
    "gas": 36612,						    "gas": 36612,
    "gasCost": 2,						    "gasCost": 2,
    "depth": 1,							    "depth": 1,
    "stack": [							    "stack": [
      "0x0",							      "0x0",
      "0x0"							      "0x0"
    ]								    ]
  },								  },
  {								  {
    "pc": 3,							    "pc": 3,
    "op": "PUSH0",						    "op": "PUSH0",
    "gas": 36610,						    "gas": 36610,
    "gasCost": 2,						    "gasCost": 2,
    "depth": 1,							    "depth": 1,
    "stack": [							    "stack": [
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x0"							      "0x0"
    ]								    ]
  },								  },
  {								  {
    "pc": 4,							    "pc": 4,
    "op": "PUSH1",						    "op": "PUSH1",
    "gas": 36608,						    "gas": 36608,
    "gasCost": 3,						    "gasCost": 3,
    "depth": 1,							    "depth": 1,
    "stack": [							    "stack": [
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x0"							      "0x0"
    ]								    ]
  },								  },
  {								  {
    "pc": 6,							    "pc": 6,
    "op": "PUSH1",						    "op": "PUSH1",
    "gas": 36605,						    "gas": 36605,
    "gasCost": 3,						    "gasCost": 3,
    "depth": 1,							    "depth": 1,
    "stack": [							    "stack": [
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x1"							      "0x1"
    ]								    ]
  },								  },
  {								  {
    "pc": 8,							    "pc": 8,
    "op": "GAS",						    "op": "GAS",
    "gas": 36602,						    "gas": 36602,
    "gasCost": 2,						    "gasCost": 2,
    "depth": 1,							    "depth": 1,
    "stack": [							    "stack": [
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x1",							      "0x1",
      "0xff"							      "0xff"
    ]								    ]
  },								  },
  {								  {
    "pc": 9,							    "pc": 9,
    "op": "CALL",						    "op": "CALL",
    "gas": 36600,						    "gas": 36600,
    "gasCost": 36600,					      |	    "gasCost": 34300,
    "depth": 1,							    "depth": 1,
    "stack": [							    "stack": [
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x0",							      "0x0",
      "0x1",							      "0x1",
      "0xff",							      "0xff",
      "0x8ef8"							      "0x8ef8"
    ]								    ]
  },								  },
  {								  {
    "pc": 10,							    "pc": 10,
    "op": "PC",							    "op": "PC",
    "gas": 2300,						    "gas": 2300,
    "gasCost": 2,						    "gasCost": 2,
    "depth": 1,							    "depth": 1,
    "stack": [							    "stack": [
      "0x0"							      "0x0"
    ]							      <
  },							      <
  {							      <
    "pc": 11,						      <
    "op": "STOP",					      <
    "gas": 2298,					      <
    "gasCost": 0,					      <
    "depth": 1,						      <
    "stack": [						      <
      "0x0",						      <
      "0xa"						      <
    ]								    ]
  }								  }
]								]

In summary, although only 87496n gas is consumed in both cases, 89794n is required for the transaction to succeed. The main difference is that EVM treats the CALL_STIPEND (2300) as a refund, while Kakarot EVM doesn't and directly injects it in the gas left making it seem like the operation needs less gas than in reality (34300 instead of the full 36600).

Can you please check this again, thank you.

[c4-judge]

dmvt removed the grade

[c4-judge]

dmvt marked the issue as selected for report

[dmvt]

Thank you for the additional context and proof. In this case you are highlighting a denial of service that will impact protocol availability and cause annoyance for the user. It is effectively a self-griefing attack. Reinstated as a valid medium.

[imsrybr0]

Hi @dmvt,

I believe protocol availability will not be impacted, but yes users will need to bump the gas estimates given by Kakarot in those cases in other for their transaction to succeed.

Thanks 👍

[dmvt]

Hi @dmvt,

I believe protocol availability will not be impacted, but yes users will need to bump the gas estimates given by Kakarot in those cases in other for their transaction to succeed.

Thanks 👍

Correct. No direct impact. What I was trying (and failed) to communicate is that when a transaction fails because of a bad gas estimate, the impact is the same way as griefing attacks which cause an otherwise valid transaction to fail. There is a lot of precedent stating that these types of griefing attacks are medium risk, so it makes sense to me that this issue has the same severity.

[enitrat]

that EVM treats the CALL_STIPEND (2300) as a refund, while Kakarot EVM doesn't

In the EVM context "refund" only refers to the gas that is reimbursed for clearing storage, so I would say that in this case we cannot really say that the CALL_STIPEND in call opcodes is a refund.

Actually, we will use the eth_estimate_gas entrypoint as a lower-bound heuristic used by our RPC nodes to have a base value on how to compute the gas required by the transaction. It think it is actually impossible to get the actual required gas for the computation without adding an extra field in the EVM that tracks, for each call, the eventual non-used call stipend, and the 1/64 call buffer requirement. Tracking this would not be useful for the protocol functions

If you want, you can check the code of RETH and GETH. All EVM clients use a binary search to find an accurate gas estimation, because it is not predictible by simply analyzing the transaction simulation receipt

In this case you are highlighting a denial of service that will impact protocol availability and cause annoyance for the user.

I highly disagree with that; as there is nothing related to Kakarot that will make DoS attack possible that will impact protocol availability in any case. This is akin to saying that hosting an RPC service with a Geth node that returns wrong gas estimates is a risk for the Ethereum protocol.

when a transaction fails because of a bad gas estimate, the impact is the same way as griefing attacks which cause an otherwise valid transaction to fail.

I have an opposite view, I think it's not a griefing attack on the protocol, considering that what happens here is just a transaction that was submitted with an incorrect gas limit for it to complete successfully 🤔

To summarize things:

• eth_estimate_gas does not return the actual gas required to send this transaction (I agree)
• eth_estimate_gas is not a core function used in the protocol and is never invoked in the transaction execution flow; it only provides heuristics for RPC services
• the output of eth_estimate_gas is not the transaction's gas_limit.
• As such, I would not consider this as a valid issue

[dmvt]

Ok with the sponsor's comments, I'm in agreement. Appreciate the links to the GETH/RETH code, which helps with comparison. I was mistakenly under the impression that the fix to gas estimates had been at the node level in EVM, not at the client level. Back to invalid.

[c4-judge]

dmvt marked the issue as unsatisfactory:
Invalid