Wining a challenge by engineering time

[howlbot-integration[bot]]

Lines of code

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/main/src/challengeV2/EdgeChallengeManager.sol#L511

Vulnerability details

Impact

If the difference between challengePeriodBlocks and the total unrivaled time of a malicious assertion claim is less than the delay between sending a transaction and mining that transaction, the malicious assertion claim will always win regardless of the total unrivaled time of the valid assertion claim.

Proof of Concept

Please have a look at the following time demonstration for better understanding:

 ---- t1 ---- t1 + k ---- t1 + tH ---- t1 + tH + tA ---- t1 + k + tH ---- t1 + tH + tA + k ---- t1 + k + tH + k ----> t

    Honest    Honest       Evil         Evil               Honest               Evil                  Honest
    Create    Create       Rival &      Confirm            Confirm              Confirm               Confirm
                           Create
    Send      Mined        Send         Send               Send                 Mined                 Mined

                                                           Evil
                                                           Rival &
                                                           Create
                                                           Mined

• challengePeriodBlocksInTime: challengePeriodBlocks in time.
• t1: the time that an honest party sends a tx of creating an edge (whether creating a layer zero edge or bisecting an edge at any level)
• k: the delay between a tx is sent and being mined on Ethereum.
• t1 + k: the time that the honest party's tx of creating an edge is mined
• tH: the remaining unrivaled time that the honest party requires to win by confirming the valid assertion claim by time. totalUnriveledTimeInTime(valid assertion claim) = challengePeriodBlocksInTime - tH
• t1 + tH: the time that the evil party sends the tx of rivaling the honest party's edge as well as creating a new edge. This will be mined at t1 + k + tH.
• tA: the remaining unrivaled time that the evil party requires to win by confirming the malicious assertion claim by time. totalUnriveledTimeInTime(malicious assertion claim) = challengePeriodBlocksInTime - tA
• t1 + tH + tA: the time that the evil party sends the confirmation tx by calling confirmEdgeByTime to confirm the malicious assertion claim.
• t1 + k + tH: the time that the honest party sends the confirmation tx by calling confirmEdgeByTime to confirm the valid assertion claim, also the time that the evil party's rivaling and the new edge creation is mined.
• t1 + k + tH + tA: the time that the evil party's confirmation tx is mined.

• t1 + k + tH + k: the time that the honest party's confirmation tx is mined.

  function confirmEdgeByTime(bytes32 edgeId, AssertionStateData calldata claimStateData) public {
      ChallengeEdge storage topEdge = store.get(edgeId);
      if (!topEdge.isLayerZero()) {
          revert EdgeNotLayerZero(topEdge.id(), topEdge.staker, topEdge.claimId);
      }
  
      uint64 assertionBlocks = 0;
      // if the edge is block level and the assertion being claimed against was the first child of its predecessor
      // then we are able to count the time between the first and second child as time towards
      // the this edge
      bool isBlockLevel = ChallengeEdgeLib.levelToType(topEdge.level, NUM_BIGSTEP_LEVEL) == EdgeType.Block;
      if (isBlockLevel && assertionChain.isFirstChild(topEdge.claimId)) {
          assertionChain.validateAssertionHash(
              topEdge.claimId,
              claimStateData.assertionState,
              claimStateData.prevAssertionHash,
              claimStateData.inboxAcc
          );
          assertionBlocks = assertionChain.getSecondChildCreationBlock(claimStateData.prevAssertionHash)
              - assertionChain.getFirstChildCreationBlock(claimStateData.prevAssertionHash);
      }
  
      uint256 totalTimeUnrivaled = store.confirmEdgeByTime(edgeId, assertionBlocks, challengePeriodBlocks);
  
      emit EdgeConfirmedByTime(edgeId, store.edges[edgeId].mutualId(), totalTimeUnrivaled);
  }

  https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/main/src/challengeV2/EdgeChallengeManager.sol#L511

Happy Scenario:

Suppose the total unriveled time of the valid assertion claim is challengePeriodBlocksInTime - tH, so if the evil party delays only tH seconds in rivaling an edge, the honest party will win and can confirm the valid assertion claim by time by calling confirmEdgeByTime.

• The honest party sends an tx to create an edge (whether creating a layer zero edge or bisecting an edge at any level) at time t1.
• This tx is mined k seconds later. So, this tx is mined at t1 + k.
• The evil party does not rival this edge, so the timer of this edge will tick in favor of the honest party.
• When delay in rivaling this edge reaches to tH, the honest party interprets that the total unrivaled time of the valid assertion claim is now challengePeriodBlocksInTime - tH + tH, so he is able to win by confirming it by time. So, the honest party sends confirmEdgeByTime tx at t1 + k + tH to confirm the valid assertion claim.
• This tx is mined at t1 + k + tH + k. So, the valid assertion claim is confirmed, and the honest party wins.

Unhappy Scenario:

Suppose the total unriveled time of the valid assertion claim is challengePeriodBlocksInTime - tH, so if the evil party delays only tH seconds in rivaling an edge, the honest party will win and can confirm the valid assertion claim by time by calling confirmEdgeByTime.

Moreover suppose that total unriveled time of the malicious assertion claim is challengePeriodBlocksInTime - tA, so if the honest party delays only tA seconds in rivaling an edge, the evil party will win and can confirm the malicious assertion claim by time by calling confirmEdgeByTime.

• The honest party sends an tx to create an edge (whether creating a layer zero edge or bisecting an edge at any level) at time t1.
• This tx is mined k seconds later. So, this tx is mined at t1 + k.
• The evil party does not rival this edge, so the timer of this edge will tick in favor of the honest party.
• The evil party sends a tx to rival this edge as well as creating a new edge at t1 + tH.
• The evil party sends a tx of confirmEdgeByTime at t1 + tH + tA to confirm the malicious assertion claim.
• When delay in rivaling this edge reaches to tH, the honest party interprets that the total unrivaled time of the valid assertion claim is now challengePeriodBlocksInTime - tH + tH, so he is able to win by confirming it by time. So, the honest party sends confirmEdgeByTime tx at t1 + k + tH to confirm the valid assertion claim.
• The evil party's edge creation tx is mined at t1 + tH + k. This tx rivals the honest party's edge as well as creating a new edge.
• The evil party's confirmEdgeByTime tx is mined at t1 + tH + tA + k erlier than the honest party's confirmation tx to be mined. So, the malicious assertion claim is confirmed, and the evil party wins.
• The honest party's confirmEdgeByTime tx is mined at t1 + k + tH + k, but it is reverted because its rival is already confirmed.

Even if the honest party rivals the evil party's edge at time t1 + k + tH, it will be mined at t1 + k + tH + k which is too late because the evil party's confirm tx is mined at t1 + k + tH + tA.

The only condition is that tA <= k.

Example 1 (where tA < tH):

 -- 604000 -- 604048 ---- 604100 ------- 604124 ---------- 604148 -------- 604172 ----------------- 604196 ----> t

 ---- t1 ---- t1 + k ---- t1 + tH ---- t1 + tH + tA ---- t1 + k + tH ---- t1 + tH + tA + k ---- t1 + k + tH + k ----> t

    Honest    Honest       Evil         Evil               Honest               Evil                  Honest
    Create    Create       Rival &      Confirm            Confirm              Confirm               Confirm
                           Create
    Send      Mined        Send         Send               Send                 Mined                 Mined

                                                           Evil
                                                           Rival &
                                                           Create
                                                           Mined   

• challengePeriodBlocksInTime = 604800 (7 days)
• tH: 100
• tA: 24
• k: 48

Honest party creates an edge at time 604000, and it is mined at 604000 + 48 = 604048. The total unrivaled time of the valid assertion claim is 604700, so if the evil party makes delay of 100 seconds, the honest party can confirm the valid assertion claim. Moreover, the total unrivaled time of the malicious assertion claim is 604776, so if honest party makes delay of 24 seconds, the evil party can confirm the malicious assertion claim.

Evil party sends a tx at 604000 + 100 = 604100 to rival the honest party's edge and also creates a new edge. Then the evil party sends a tx at 604000 + 100 + 24 = 604124 to confirm the malicious assertion claim.

The honest party notices at 604000 + 48 + 100 = 604148 that the total unrivaled time of valid assertion claim is now 604700 + (604148 - (604000 + 48)) = 604800 which is equal to challengePeriodBlocksInTime. So, he sends the tx to confirm the valid assertion claim.

The evil party's rival and new edge creation tx is mined at 604000 + 48 + 100 = 604148.

The evil party's confirmation tx is mined at 604000 + 48 + 100 + 24 = 604172. This tx will be successful because the time this tx is mined, the total unrivaled time of malicious assertion claim is increased by 24 which makes the total equal to 604800 = challengePeriodBlocksInTime. So, the malicious assertion claim is confirmed, and the evil party wins.

The honest party's confirmation tx will not be successful at 604800 + 48 + 100 + 48 = 604196, because its rival is already confirmed.

Example 2 (where tA > tH):

 -- 604000 -- 604005 ------- 604029 -------- 604048 ------ 604053 -------- 604077 ------------------ 604101 ----> t

 ---- t1 ---- t1 + tH ---- t1 + tH + tA ---- t1 + k ---- t1 + k + tH ---- t1 + tH + tA + k ---- t1 + k + tH + k ----> t

    Honest    Evil          Evil            Honest            Honest              Evil                  Honest
    Create    Rival &       Confirm         Create            Confirm             Confirm               Confirm
              Create             
    Send      Send          Send            Mined             Send                Mined                 Mined

                                                              Evil
                                                              Rival &
                                                              Create
                                                              Mined  

• challengePeriodBlocksInTime = 604800 (7 days)
• tH: 5
• tA: 24
• k: 48

Honest party creates an edge at time 604000. The total unrivaled time of the valid assertion claim is 604795, so if the evil party makes delay of 5 seconds, the honest party can confirm the valid assertion claim. Moreover, the total unrivaled time of the malicious assertion claim is 604776, so if honest party makes delay of 24 seconds, the evil party can confirm the malicious assertion claim.

Evil party sends a tx at 604000 + 5 = 604005 to rival the honest party's edge (which is not still mined) and also creates a new edge. Then the evil party sends a tx at 604000 + 5 + 24 = 604029 to confirm the malicious assertion claim.

The honest party's edge creation is mined at 604000 + 48 = 604048.

The honest party notices at 604000 + 48 + 5 = 604053 that the total unrivaled time of valid assertion claim is now 604795 + (604053 - (604000 + 48)) = 604800 which is equal to challengePeriodBlocksInTime. So, he sends the tx at 604000 + 48 + 5 = 604053 to confirm the valid assertion claim.

The evil party's rival and new edge creation tx is mined at 604000 + 48 + 5 = 604053.

The evil party's confirmation tx is mined at 604000 + 48 + 5 + 24 = 604077. This tx will be successful because the time this tx is mined, the total unrivaled time of malicious assertion claim is increased by 24 which makes the total equal to 604800 = challengePeriodBlocksInTime. So, the malicious assertion claim is confirmed, and the evil party wins.

The honest party's confirmation tx will not be successful at 604800 + 48 + 5 + 48 = 604101, because its rival is already confirmed.

Example 3 (where tA < tH & evil party is not precise):

So far, I was assuming that the evil party's rival and new edge creation is mined exactly at the time the honest party's confirmation tx is sent. This was just for simplicity, and it is not necessary. So, here I assume that the evil party has x seconds delay where x <= k.

 -- 604000 -- 604048 ------ 604112 ---------- 604136 ------------- 604148 ---------- 604160 ------------- 604184 --------------- 604196 ----> t

 ---- t1 ---- t1 + k ---- t1 + tH + x ---- t1 + tH + tA + x ---- t1 + k + tH -- t1 + tH + x + k -- t1 + tH + tA + x + k --- t1 + k + tH + k ----> t

    Honest    Honest       Evil             Evil                    Honest          Evil               Evil                  Honest
    Create    Create       Rival &          Confirm                 Confirm         Rival &            Confirm               Confirm
                           Create                                                   Create
    Send      Mined        Send             Send                    Send            Mined              Mined                 Mined

• challengePeriodBlocksInTime = 604800 (7 days)
• tH: 100
• tA: 24
• k: 48
• x: 12

Honest party creates an edge at time 604000, and it is mined at 604000 + 48 = 604048. The total unrivaled time of the valid assertion claim is 604700, so if the evil party makes delay of 100 seconds, the honest party can confirm the valid assertion claim. Moreover, the total unrivaled time of the malicious assertion claim is 604776, so if honest party makes delay of 24 seconds, the evil party can confirm the malicious assertion claim.

Evil party sends a tx at 604000 + 100 + 12 = 604112 to rival the honest party's edge and also creates a new edge. Then the evil party sends a tx at 604000 + 100 + 24 + 12 = 604136 to confirm the malicious assertion claim.

The honest party notices at 604000 + 48 + 100 = 604148 that the total unrivaled time of valid assertion claim is now 604700 + (604148 - (604000 + 48)) = 604800 which is equal to challengePeriodBlocksInTime. So, he sends the tx to confirm the valid assertion claim.

The evil party's rival and new edge creation tx is mined at 604000 + 48 + 100 + 12 = 604160.

The evil party's confirmation tx is mined at 604000 + 48 + 100 + 24 + 12 = 604184. This tx will be successful because the time this tx is mined, the total unrivaled time of malicious assertion claim is increased by 24 which makes the total equal to 604800 = challengePeriodBlocksInTime. So, the malicious assertion claim is confirmed, and the evil party wins.

The honest party's confirmation tx will not be successful at 604800 + 48 + 100 + 48 = 604196, because its rival is already confirmed.

The root cause of this issue is that there is a delay between the time the honest party sends the confirmation tx and the time it is mined. If the evil party could engineer the time so that the confirmation of malicious assertion claim is mined between these two times, the evil party will always win the scenarios where tA <= k. In other words, the required total unrivaled time of malicious assertion claim to be confirmed should be equal or less than the delay between sending a tx and being mined.

In summary, when the honest party notices that total unrivaled time of valid assertion claim is meeting the threshold, he sends the confirmation tx. There is some delay to have this tx mined. If the evil party during this time delay could mine his confirmation of malicious assertion claim, he is the winner.

Some important notes:

• The attack is possible because when the honest party's confirmation tx is mined, the total unrivaled time of valid assertion claim is equal to challengePeriodBlocksInTime + k. In other words, k is the extra time that honest party wastes. And this extra waste of time is the time window that the evil party can confirm the malicious assertion claim. That is why the only condition for this attack is to have tA <= k.
• It is maybe assumed that if the honest party sends the confirmation tx k seconds earlier, it will be protected against this attack. Because, it will be mined k seconds earlier, so that the evil party's confirmation will not be mined earlier than the honest party's. But, this is not true, because the honest party sends the confirmation tx as soon as he notices that the total unrivaled time of valid assertion claim is equal to challengePeriodBlocksInTime. In other words, if the honest party sends the confirmation tx earlier (when the total unrivaled time of valid assertion claim is not equal to challengePeriodBlocksInTime), it is not guaranteed that during the time this tx is being mined the evil party does not rival the edge and stops the timer. So, it is reasonable that the honest party be patient until he notices that total unrivaled time of the valid assertion claim is equal to challengePeriodBlocksInTime and then sends the confirmation tx.
• There is maybe a question that why when the evil party rivals the honest party's edge and creates a new edge, the honest party does not rival this newly created edge. The answer is that the evil party's rival and new edge creation is mined at t1 + k + tH or after (explained in example 3). In other words, it is mined after the honest party's confirmation tx is sent. Even if the honest party rivals this newly created edge, it will be mined after k seconds which is too late, because it will be mined after the evil party's confirmation tx is mined.
• For simplicity I was using the time instead of block number. Even if using the block number, this attack is still valid. It is just needed to divide each time by 12 (assuming each block is mined every 12 seconds on Ethereum).
• This attack is possible because the evil party knows how the honest party reacts. That is why the evil party sends the confirmation tx at the time that the total unrivaled time of malicious assertion claim is not eqaul to challengePeriodBlocksInTime (so he is not eligible to confirm it). But, the evil party knows that when this tx is mined the total unrivaled time of malicious assertion claim is eqaul to challengePeriodBlocksInTime. Becuase, he knows that the honest party will react to an edge when it is mined. So, the evil party sends the tx of confirmation shortly (tA second) after the rival and new edge creation tx.
• So far I was showing the cases that both valid and malicious assertion claims are very close to be confirmed by time, just to demonstrate that in case the game is very challenging, the evil party is the winner with higher possibility. Looking at examples shows that the evil party's confirmation tx is sent always before the evil party's rival and new edge creation tx is mined. So, the honest party reacts to this newly created edge at the time it is mined. Even if the honest party immediately rivals after noticing this tx is mined, it will be mined k seconds later, and accumulating k seconds in favor of the evil party. Since the evil party's confirmation tx is sent before the evil party's rival and new edge creation tx, the evil party's confirmation tx is mined earlier than the honest user's reaction.

Tools Used

Recommended Mitigation Steps

It should be enforced that the confirmation tx should not be sent before the latest edge creation tx related to the assertion claim is mined.

uint256 public kInBlocks = 48 / 12; // The delay between sending a tx and being mined in blocks
function confirmEdgeByTime(bytes32 edgeId, AssertionStateData calldata claimStateData) public {
    //....
    ChallengeEdge storage topEdge = store.get(edgeId);

    // this is the block in which the last child edge creation related to this edge id is mined.
    uint lastCreatedEdgeInBlock = topEdge.latestCreatedEdge.createdAtBlock; 

    require(block.number - lastCreatedEdgeInBlock >= kInBlocks, "the confirmation is sent earlier than the edge creation is mined");
}

Assessed type

Context

[c4-sponsor]

gzeoneth (sponsor) disputed

[gzeoneth]

Invalid. Misconfigurations are out-of-scope; challengePeriodBlocks should be configured to the attacker censorship budget

Also in README:

It is assumed that off-chain computation costs are negligible, and honest validators can react to malicious action broadcasted on-chain immediately in the same block unless the malicious party spend their censorship budget.

[Picodes]

Flagging as Out-of-Scope as shown by the sponsor.

[c4-judge]

Picodes marked the issue as unsatisfactory: Out of scope