Hash Collision in the flow of `Router:redeemPositions` function

[hats-bug-reporter[bot]]

Github username: -- Twitter username: -- Submission hash (on-chain): 0xe45102ec2d1ceb4c0b78a18db1973bb45ff9ee7963d22aff4e4a1ea80547a081 Severity: medium

Description: Description\ The Router contract allows users to redeem conditional token positions. When a user calls Router:redeemPositions, it eventually calls ConditionalTokens:redeemPositions to handle the redemption of collateral based on the outcome of a condition. In the redeemPositions function, the getCollectionId function from the CTHelpers library is called to construct a collectionId. This collectionId identifies a unique outcome collection for a specific condition. If parentCollectionId is zero, the collection ID is generated based solely on the conditionId and indexSet. Here is where potential risks of collision arise.

The function getCollectionId takes three inputs:

• parentCollectionId: Represents the collection from which this outcome was derived. If this is zero, it indicates that the outcome is based directly on the original condition.
• conditionId: The ID of the condition, representing a specific market (e.g., the outcome of a soccer match, financial forecast, etc.).
• indexSet: A bitmask representing the specific outcome slots for this condition.

The function generates an initial value x1 using keccak256(abi.encodePacked(conditionId, indexSet)). This combination of the condition and outcome is supposed to uniquely identify an outcome collection.

The process involves elliptic curve cryptography (ECC) to ensure the resulting value (or collection ID) is on a valid elliptic curve, which allows for unique identification of outcome collections under most circumstances.

If parentCollectionId is zero, the collectionId relies solely on two variables:

• conditionId
• indexSet

If two different conditions are created where the conditionId values are similar or happen to hash to a similar value, and they use the same indexSet, the resulting collectionId could end up being the same. For instance, two unrelated prediction markets, one for sports and one for finance, might happen to use the same indexSet (which is a small bitmask, often quite limited in values) and similar conditionIds, leading to a collision in the collectionId.

Example:

Condition A: Sports Prediction Market

• Condition ID: keccak256("Premier League Match: Team A vs Team B")
• Outcomes: Team A wins, Team B wins, Draw
• The indexSet for Team A wins and Team B wins might be 0b110 (or 6 in decimal), representing these two outcomes combined.

Condition B: Financial Market

• Condition ID: keccak256("Stock ABC Performance: Rise or Fall")
• Outcomes: Price Rises, Price Falls
• The indexSet for Price Rises and Price Falls could also be 0b110.

Even though these are completely different conditions, they might end up having the same collectionId if the conditionId for both markets happens to hash similarly. The indexSet for both conditions happens to be the same (like 0b110 representing a combination of two outcomes).

Impact\ The outcome collection for one market (e.g., sports) could be mixed with the outcome collection of another market (e.g., financial). If users are attempting to redeem positions in one market, they might inadvertently redeem positions in the other.

Because positions in different markets might be represented by the same collectionId, users could potentially redeem funds that don't belong to them. For example, if the sports market resolves but the financial market hasn’t, users might redeem payouts for the financial market prematurely or incorrectly.

An attacker who understands how to manipulate condition IDs and index sets could deliberately create collisions across markets. By creating similar conditions and reusing certain index sets, they might be able to manipulate the outcome collection to claim rewards from multiple markets with a single position.

Recommendation\ One way to reduce collisions is to ensure that conditionIds are constructed using as much unique information as possible. This could include additional parameters such as timestamps, contract addresses, or other metadata. If the parentCollectionId is zero, it is suggested to add further validation to ensure no unintended collisions in the derived collectionId.

[PlamenTSV]

"could", "might", "possible to happen"