https://github.com/privacy-scaling-explorations/zkevm-chain/blob/master/contracts/templates/mpt.yul#L24
During verification, the mpt library walks down the inclusion proof to verify that hashes match as expected. However, when encountering an extension node in the account of storage proof, the library incorrectly computes the depth by adding the length in bytes to the depth, which is counted as the number of nibbles (half-bytes), as well as not accounting for the path length parity.
For example, if the extension node ['13 f4 a7', next_hash] was encountered, the 1 would indicate that it is an extension node with an odd path length. The correct path length to be added to the depth would be 5, but the library incorrectly adds 3 to the depth by getting the length in bytes. More concretely, due to an extension node in the account or storage proof, it is impossible to prove that the storage slot 0 of address 0x0068cf6ef4fdf5a95d0e2546dab76f679969f3f5 contains the value 2 on Ethereum mainnet.
This error leads to valid proofs not being accepted by the mpt library. An attack can make use of this behavior by forcing an extension node in the account or storage proof and thereby DoS-ing the system. An attacker can take advantage of this by brute-forcing an address on L1 via CREATE2 that has a hash collision in the first nibbles with the hash of the L1 contract address. Hence, an extension node is forced to appear in the state trie, thereby preventing any message to be replayed on L2 - a denial-of-service attack - potentially locking users' funds until the contract is upgraded.
Consider fixing the length calculation for extension nodes to accept valid proofs. It is advised to test the library and integration more thoroughly, for instance with a differential fuzzing approach and integration tests.
0xmp Analyst
Artifex1 Analyst
andresbach Analyst
https://github.com/privacy-scaling-explorations/zkevm-chain/blob/master/contracts/templates/mpt.yul#L24
During verification, the mpt library walks down the inclusion proof to verify that hashes match as expected. However, when encountering an extension node in the account of storage proof, the library incorrectly computes the depth by adding the length in bytes to the depth, which is counted as the number of nibbles (half-bytes), as well as not accounting for the path length parity.
For example, if the extension node ['13 f4 a7', next_hash] was encountered, the 1 would indicate that it is an extension node with an odd path length. The correct path length to be added to the depth would be 5, but the library incorrectly adds 3 to the depth by getting the length in bytes. More concretely, due to an extension node in the account or storage proof, it is impossible to prove that the storage slot 0 of address 0x0068cf6ef4fdf5a95d0e2546dab76f679969f3f5 contains the value 2 on Ethereum mainnet.
This error leads to valid proofs not being accepted by the mpt library. An attack can make use of this behavior by forcing an extension node in the account or storage proof and thereby DoS-ing the system. An attacker can take advantage of this by brute-forcing an address on L1 via CREATE2 that has a hash collision in the first nibbles with the hash of the L1 contract address. Hence, an extension node is forced to appear in the state trie, thereby preventing any message to be replayed on L2 - a denial-of-service attack - potentially locking users' funds until the contract is upgraded.
Consider fixing the length calculation for extension nodes to accept valid proofs. It is advised to test the library and integration more thoroughly, for instance with a differential fuzzing approach and integration tests.