Summary

An important component of this protocol is to be able to re-use order ids which have been filled/cancelled/etc. This prevents the system from getting bricked in the future, as the order ids are only uint16, meaning effectively ~65535 total orders (not exactly due to HEAD/TAIL management, etc). However, by abusing the cancelOrderFarFromOracle function of OrdersFacet, an attacker can prevent certain order ids from being re-used. This then increases the likelihood of the system to get bricked by running out of order ids to use, among other issues.

Vulnerability Details

Fundamentally the logic for re-using order ids is based on keeping track of used order ids sequentially starting from HEAD.prevId and going backwards: HEAD.prevId -> reuseId1.prevId -> reuseId2 -> ... This can be seen in the _reuseOrderIds function:

This means that if you can break this linked list starting at HEAD.prevId, then you can effectively prevent certain order ids from being re-used.

Let's now see how we can do this by abusing the cancelOrderFarFromOracle function of OrdersFacet. Lets consider the case where the protocol has a bunch of activity and the number of order ids being used surpassed 65_000. This then allows any user to call cancelOrderFarFromOracle, which will trigger the following code snippet for e.g. bid orders:

Before continuing, let's also consider the implementation of cancelOrder of LibOrders, as it is relevant to this attack, which is defined as:

Let's consider a starting state where there are 10_000 bid orders on the books and 10_000 bid order ids which are filled/cancelled & set to be re-used. Here those 10_000 bid ids to be re-used are stored as: HEAD.prevId -> reuseId1.prevId -> reuseId2.prevId -> ... -> reuseId10000. Lets also consider that the bid orders are currently ranked as: HEAD -> ... -> bidC -> bidB -> bidA -> TAIL.

We will perform the following txs:

(1) call cancelOrderFarFromOracle with the bid order id closest to TAIL (this will be bidA). This will then trigger a call to s.bids.cancelOrder(..);. Note that here the bidA.nextId == TAIL, which allows us to cancel it. The logic of cancelOrder will effectively make the following changes to our state:

1. re-use bids: HEAD.prevId -> bidA.prevId -> reuseId1.prevId -> ...

2. order-book bids: HEAD -> ... -> bidC -> bidB -> TAIL
   Also note that bidA.nextId is still TAIL, as this was not changed.

(2) call cancelOrderFarFromOracle with the bid order id closest to TAIL (which is now bidB). This will trigger a call to s.bids.cancelOrder(..);. Note that BidB.nextId == TAIL, which allows us to cancel it. The logic of cancelOrder will then make the following changes to our state:

1. re-use bids: HEAD.prevId -> bidB.prevId -> bidA.prevId -> reuseId1.prevId -> ...

2. order-book bids: HEAD -> ... -> bidC -> TAIL

(3) call cancelOrderFarFromOracle with the bid order id of bidA. Note that as mentioned earlier, bidA.nextId == TAIL still, meaning we can still call s.bids.cancelOrder(..);. There are additionally no checks to see whether the id we are canceling has already been cancelled. The logic of cancelOrder will then make the following changes to our state:

1. In _reuseOrderIds the line orders[asset][Constants.HEAD].prevId = id; results in the following changes: HEAD.prevId -> bidA

2. In _reuseOrderIds the line orders[asset][id].prevId = prevHEAD; results in the following changes: bidA.prevId -> bidB

In total these changes will look like: HEAD.prevId -> bidA.prevId -> bidB.prevId -> bidA.prevId -> bidB ... Essentially there is now a cyclical loop between bidA and bidB, which breaks the linked list which is used for the logic to re-use order ids.

Impact

By abusing the cancelOrderFarFromOracle function of OrdersFacet, an attacker can make certain order ids unusable and generally break the logic used for re-using ids. This, among other issues, can greatly increase the likelihood of bricking the market.

Tools Used

Manual review

Recommendations

In cancelOrderFarFromOracle, prior to cancelling an order, check whether that id is actually open (not cancelled/etc).