incorrect assertion can be confirmed by abusing confirmEdgeByOneStepProof function

[howlbot-integration[bot]]

Lines of code

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/6f861c85b281a29f04daacfe17a2099d7dad5f8f/src/challengeV2/libraries/EdgeChallengeManagerLib.sol#L817-L818

Vulnerability details

incorrect assertion can be confirmed by abusing confirmEdgeByOneStepProof function

Impact

An attacker can create in one transaction an enough deep level of Edges for his own assertion to have the lower part of the commit history be confirmed by calling confirmEdgeByOneStepProof and in doing so have the entire non correct assertion, that is an assertion where the upper history commitment is manipulated by the attacker, approved which is a disaster for the protocol.

Proof of Concept

When Edges are created to contest an assertion and when we reach the level of NUM_BIGSTEP_LEVEL + 1 we are in small step mode where we can provide a single proof of inclusion to have our entire chain of edges be confirmed as the correct one.

On every edge creation the edges are split or bisected with bisectEdge method :

we get a lower and an upper edge child. In the begining we have a chain of (last approved assertion) -> (our assertion) by the first bisection we roughly get two child edge

the lower one Lower_step_1(last approved assertion + middle point)

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/6f861c85b281a29f04daacfe17a2099d7dad5f8f/src/challengeV2/libraries/EdgeChallengeManagerLib.sol#L633-L635

and the upper one Upper_step_1(middle point to our assertion)

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/6f861c85b281a29f04daacfe17a2099d7dad5f8f/src/challengeV2/libraries/EdgeChallengeManagerLib.sol#L646-L648

The attacker can drill till NUM_BIGSTEP_LEVEL + 1 by stepping on the lower part of the commitment history and finally create a valid lower child that represents only the lower part of commitment history which will pass the validation trough oneStepProofEntry.proveOneStep.

But the history commitment for the upper side can be a changed/manipulated one by the attacker. Having only the lower part correct we practically have our entire assertion confirmed as the correct one.

By providing a valid proof for a history commitment inclusion to this lower part we have our edge set as confirmed and also the totalTimeUnrivaledCache set to maximal uint64 value which signals that we have a correct history.

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/6f861c85b281a29f04daacfe17a2099d7dad5f8f/src/challengeV2/libraries/EdgeChallengeManagerLib.sol#L826-L830

All other rival edges (even the valid one) are now reverted with 'RivalEdgeConfirmed'.

By calling enough time updateTimerCacheByChildren and updateTimerCacheByClaim like is done in the test function updateTimers we can have our wrong assertion be the one included as the next correct assertion.

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/6f861c85b281a29f04daacfe17a2099d7dad5f8f/src/challengeV2/libraries/EdgeChallengeManagerLib.sol#L506-L511

The correct assertion cannot be approved becouse we can have only one chosen assertion (from the last one confirmed plus a fixed height/number of inbox messages) the other rival assertion are discarded (as a rival edge is reverted with RivalEdgeConfirmed) when the first one is approved. And by using confirmEdgeByOneStepProof we can have this done by a malicious user in one transaction.

Note: The POC as a code sample can be used the one from the test testCanConfirmByOneStep as the two main points here are to have all needed Edges constructed in one transaction in such way that will have lower history commitment included/confirmed on the last edge. And proveOneStep doesn't revert for the last small step Edge that checks the correct virtual machine is used from bytes32 cursor = edgeId;:

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/6f861c85b281a29f04daacfe17a2099d7dad5f8f/src/challengeV2/libraries/EdgeChallengeManagerLib.sol#L798

to store.edges[edgeId].endHistoryRoot

https://github.com/code-423n4/2024-05-arbitrum-foundation/blob/6f861c85b281a29f04daacfe17a2099d7dad5f8f/src/challengeV2/libraries/EdgeChallengeManagerLib.sol#L822

Tools Used

Manual review

Recommended Mitigation Steps

One recommendation for solving this problem is to not allow one single account to play the "game" of rivaling edges by having a require that the rival edge is created by another account. This will enforce that playing this "game" is done in turns not just by one account. Something like this :

// for this to work we need a new `createdByStaker` ChallengeEdge attribute for all edges level not just the zero one (edge.staker)
 function add(EdgeStore storage store, ChallengeEdge memory edge) internal returns (EdgeAddedData memory) {
    ...
            if (firstRival == 0) {
            store.firstRivals[mutualId] = UNRIVALED;
        } else if (firstRival == UNRIVALED) {
+           require(store.edges[eId].createdByStaker != msg.sender, "not allowed")
            store.firstRivals[mutualId] = eId;
        } else {
            // after we've stored the first rival we dont need to keep a record of any
            // other rival edges - they will all have a zero time unrivaled
        }
    ...
 }

If this is not enough and the financial gain of the attacker is greater then loosing the bound for creating edges with two accounts. Trying to limit the amount of rival edges that can be created in one transaction could be also used to prevent one attacker (with two different accounts) to resolve the last edge in one transaction. Other non malicious stakers would monitor such behavior and interfere with the attacker intention. Something like (in the same add function as before):

uint created = store.createdIn[block.number][edgeId];
created += 1;
if (created > LIMIT_NUMBER_OF_EDGES_IN_ONE_TRANSACTION) {
    revert("number of max rival in block");
}
store.createdIn[block.number][edgeId] = created;

Assessed type

Other

[gzeoneth]

One step proving a single edge in a malicious tree is not sufficient for confirming a layer zero edge in that tree because updateTimerCacheByChildren takes the min of the two children. The honest party would be able to bisect to rival invalid edges before they accumulate enough time.

[c4-judge]

Picodes marked the issue as unsatisfactory: Invalid