ImmutableSimulator is breaking contract immutability axiom

[c4-submissions]

Lines of code

https://github.com/code-423n4/2023-10-zksync/blob/1fb4649b612fac7b4ee613df6f6b7d921ddd6b0d/code/system-contracts/contracts/ImmutableSimulator.sol#L41

Vulnerability details

Impact

Theoretical discussion

On Ethereum (L1 EVM), immutables become part of the stored contract's bytecode which makes their immutability and therefore the contract's immutability an absolute mathematical certainty. Except for the known selfdestruct pattern which is not possible on zkSync Era.

On zkSync Era (L2 EVM), the immutables of all contracts that are ever going to be deployed there share one contract storage for all their immutables using the ImmutableSimulator contract.
The immutables are stored within a 2-dimensional mapping, see setImmutables(...):

    function setImmutables(address _dest, ImmutableData[] calldata _immutables) external override {
        require(msg.sender == address(DEPLOYER_SYSTEM_CONTRACT), "Callable only by the deployer system contract");
        unchecked {
            uint256 immutablesLength = _immutables.length;
            for (uint256 i = 0; i < immutablesLength; ++i) {
                uint256 index = _immutables[i].index;
                bytes32 value = _immutables[i].value;
                immutableDataStorage[uint256(uint160(_dest))][index] = value;
            }
        }
    }

Even though the chance of storage collisons is astronomically low due to the mapping's underlying keccak256 hashing, it is not 0. As a consequence, contract immutability is not an absolute mathematical certainty anymore on zkSync Era which should be a fundamental property of any EVM-equivalent implementation.

Fortunately, this can be solved in an efficient & straightforward way by using an unique storage slot for each immutable of each contract ever going to be deployed on zkSync Era:

    function _getSafeStorageSlot(address _dest, uint256 _index) internal pure returns (uint256) {
        require(_index <= type(uint96).max, "Immutable index cannot exceed 96 bits");
        return (uint256(uint160(_dest)) << 96) | _index;
    }

As a result, contract immutability is now also a fundamental property with absolute mathematical certainty on zkSync Era.

Attack vector

Currently, the following is true:

• The storage slot of any immutable of any contract on zkSync Era is deterministic and therefore known.
• There is no protection in the ImmutableSimulator contract that requires the value of a storage slot to be 0 before being (over-)written. Assuming 0 means uninitialized.
• One can freely choose an immutable index by manipulating a contract's bytecode before deployment. Someone with LLVM IR skills could create a contract with constant bytecode that fetches the immutable index from a pre-defined contract address.

As a result, a potential attacker has 2 variables to play with:

1. The deployed address of his immutable overwriter contract can be varied using create2 with a salt.
2. The immutable index can be chosen arbitrarily without altering the contract's deployed address.

At this point it is only a question of time, computational power and economical incentives to overwrite an existing contract's immutable value.
Using the storage slot computation, which was proposed above, would completely close this attack vector.

Conclusion

Irrespective of technical feasibility of an exploit, contract immutability can be considered as an asset of an EVM-equivalent implementation and therefore deserves to be preserved with absolute mathematical certainty.

Additional reference

Concerning collisions, there is an interesting discussion about them in EIP-3607. As a result, EIP-3607 was merged into the Ethereum yellow paper and the Geth execution client, which further supports the validity of the current concern.

Proof of Concept

The following PoC demonstrates, that an immutables index can be arbitrarily chosen.

The following contract has 3 immutables with the values 1, 1 and 2 which the compiler places at index 0, 32 and 64.

object "ImmutableWriter" {
  code {
    mstore(128, 1)                                   // write the 1st value to the heap
    mstore(160, 2)                                   // write the 2nd value to the heap

    let _2 := mload(64)
    let _3 := datasize("ImmutableWriter_deployed")              // returns 0 in the deploy code
    codecopy(_2, dataoffset("ImmutableWriter_deployed"), _3)    // no effect, because the length is 0

    // the 1st argument is ignored
    setimmutable(_2, "a", mload(128))                // write the 1st value to the auxiliary heap array at index 0
    setimmutable(_2, "b", mload(128))                // write the 1st value to the auxiliary heap array at index 32
    setimmutable(_2, "c", mload(160))                // write the 2nd value to the auxiliary heap array at index 64

    return(_2, _3)                                   // returns the auxiliary heap array instead
  }
  object "ImmutableWriter_deployed" {
    code {
    }
  }
}

The following test shows how the index of the 3rd immutable is changed from 64 (0x40) to 0xFFFF by manipulating the bytecode (the easy way).
Apply the diff to the existing ImmutableSimulator test suite and run bash quick-setup.sh from ./code/system-contracts/scripts to execute the PoC test case:

diff --git a/code/system-contracts/test/ImmutableSimulator.spec.ts b/code/system-contracts/test/ImmutableSimulator.spec.ts
index 3ba7b03..a92085c 100644
--- a/code/system-contracts/test/ImmutableSimulator.spec.ts
+++ b/code/system-contracts/test/ImmutableSimulator.spec.ts
@@ -1,13 +1,19 @@
 import { expect } from 'chai';
-import { ImmutableSimulator } from '../typechain-types';
+import { ImmutableSimulator, ImmutableSimulator__factory } from '../typechain-types';
 import { DEPLOYER_SYSTEM_CONTRACT_ADDRESS } from './shared/constants';
-import { Wallet } from 'zksync-web3';
-import { getWallets, deployContract } from './shared/utils';
+import { Wallet, Contract } from 'zksync-web3';
+import { getWallets, deployContract, deployContractRaw } from './shared/utils';
 import { network, ethers } from 'hardhat';
+import { BigNumber } from 'ethers';
 
 describe('ImmutableSimulator tests', function () {
     let wallet: Wallet;
     let immutableSimulator: ImmutableSimulator;
+    let immutableWriter: Contract;
+    let realImmutableSimulator: ImmutableSimulator;
+
+    const IMMUTABLE_SIMULATOR_ADDRESS = '0x0000000000000000000000000000000000008005';
+    const IMMUTABLE_WRITER_BYTECODE = '0x0000000101200190000000040000c13d0000000001000019000000000001042d0000000101000039000000800010043f0000000201000039000000a00010043f000000800100043d00000140000004430000016000100443000000800100043d00000020020000390000018000200443000001a0001004430000004001000039000000a00300043d000001c000100443000001e0003004430000010000200443000000030100003900000120001004430000000701000041000000190001042e0000001800000432000000190001042e0000001a0001043000000000000000000000000200000000000000000000000000000100000001000000000000000000de3d869d26c3f16037fb4df28bceab71cf0ec8373d74e445cfbb3842ee0a5a8f';
 
     const RANDOM_ADDRESS = '0xdeadbeefdeadbeefdeadbeefdeadbeefdeadbeef';
     const IMMUTABLES_DATA = [
@@ -24,9 +30,28 @@ describe('ImmutableSimulator tests', function () {
     before(async () => {
         wallet = getWallets()[0];
         immutableSimulator = (await deployContract('ImmutableSimulator')) as ImmutableSimulator;
+
+        realImmutableSimulator = ImmutableSimulator__factory.connect(IMMUTABLE_SIMULATOR_ADDRESS, wallet);
     });
 
     describe('setImmutables', function () {
+        it.only('set at compiler-defined index', async () => {
+            immutableWriter = await deployContractRaw(IMMUTABLE_WRITER_BYTECODE);
+
+            expect(BigNumber.from(await realImmutableSimulator.getImmutable(immutableWriter.address, 0x00))).to.be.equal(1);
+            expect(BigNumber.from(await realImmutableSimulator.getImmutable(immutableWriter.address, 0x20))).to.be.equal(1);
+            expect(BigNumber.from(await realImmutableSimulator.getImmutable(immutableWriter.address, 0x40))).to.be.equal(2);
+        });
+
+        it.only('set at user-defined index', async () => {
+            // changed sequence in bytecode to change 3rd immutable index from 0x40 to 0xFFFF
+            immutableWriter = await deployContractRaw(IMMUTABLE_WRITER_BYTECODE.replace("004001", "FFFF01"));
+
+            expect(BigNumber.from(await realImmutableSimulator.getImmutable(immutableWriter.address, 0x00))).to.be.equal(1);
+            expect(BigNumber.from(await realImmutableSimulator.getImmutable(immutableWriter.address, 0x20))).to.be.equal(1);
+            expect(BigNumber.from(await realImmutableSimulator.getImmutable(immutableWriter.address, 0xFFFF))).to.be.equal(2);
+        });
+
         it('non-deployer failed to call', async () => {
             await expect(immutableSimulator.setImmutables(RANDOM_ADDRESS, IMMUTABLES_DATA)).to.be.revertedWith(
                 'Callable only by the deployer system contract'
diff --git a/code/system-contracts/test/shared/utils.ts b/code/system-contracts/test/shared/utils.ts
index 79cdf6d..9ffea49 100644
--- a/code/system-contracts/test/shared/utils.ts
+++ b/code/system-contracts/test/shared/utils.ts
@@ -85,6 +85,24 @@ export async function deployContractYul(codeName: string, path: string): Promise
     );
 }
 
+export async function deployContractRaw(bytecode: string): Promise<Contract> {
+    return await deployer.deploy(
+        {
+            bytecode,
+            factoryDeps: {},
+            sourceMapping: '',
+            _format: '',
+            contractName: '',
+            sourceName: '',
+            abi: [],
+            deployedBytecode: bytecode,
+            linkReferences: {},
+            deployedLinkReferences: {}
+        },
+        []
+    );
+}
+
 export async function publishBytecode(bytecode: BytesLike) {
     await wallet.sendTransaction({
         type: 113,

Tools Used

Manual review

Recommended Mitigation Steps

See above.

Assessed type

Other

[c4-pre-sort]

bytes032 marked the issue as primary issue

[c4-pre-sort]

bytes032 marked the issue as sufficient quality report

[miladpiri]

Invalid. It is a Hash collision issue.

[c4-sponsor]

miladpiri (sponsor) disputed

[c4-judge]

GalloDaSballo marked the issue as unsatisfactory:
Invalid

[GalloDaSballo]

Due to hypotheticals I must close

I think if you do find a way to break some immutables, the sponsor will be very responsive

[MarioPoneder]

I agree with the judgement due to the enormous off-chain computational effort and strong economical incentives in order to perform this attack.
However, I still recommend the following @miladpiri:

1. Compute storage slots in a way that avoid collisions in the first place (code suggestion in report).
2. And/or restrict the usage of arbitrary immutable indices (see PoC). This could be enforced within the ImmutableSimulator.setImmutables(…) method.

[miladpiri]

Thanks @MarioPoneder for the recommendation.