Overflow in Router `getPartition `Function for Large Outcome Sets

[hats-bug-reporter[bot]]

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

Description:

• Description: The getPartition function in the Router contract is vulnerable to overflow when used with Conditional Tokens markets that have more than 256 outcome slots. This situation can occur in Multiscalar markets or other complex market structures.

• Bug scenario:

  1. A Multiscalar market or a complex nested market is created with more than 256 possible outcomes.
  2. The splitPosition, mergePositions, or redeemPositions function is called for this market.
  3. These functions internally call getPartition(conditionalTokens.getOutcomeSlotCount(conditionId)).
  4. If getOutcomeSlotCount returns a value greater than 256, the getPartition function will attempt to create an array larger than 256 elements.
  5. The bitwise left shift operation 1 << i will overflow for i >= 256, resulting in unexpected values in the partition array.
  6. This could lead to incorrect splitting, merging, or redeeming of positions, potentially causing loss of funds or other unintended behaviors.

• Attachment:

1. Proof of Concept (PoC) file:

Outcome Index	Binary Representation	Decimal Value
254	0100000...0000000000	2^254
255	1000000...0000000000	2^255
256	0000000...0000000000	0 (Overflow occurs here)
257	0000000...0000000000	0
258	0000000...0000000000	0
259	0000000...0000000000	0
...	...	...

Explanation: │ | │ Safe range (0-255) │ Overflow range (256+) │ │ │ Each bit shifts left │ Bits is out of bound in bytes32 slot │ 1, 2, 4, 8, ..., 2^255 │ 0, 0, 0, 0, ... (repeats) │ │ └─────────────────────────────┴───────────────────────────────────────── 256-bit uint256 value

$ Overflow: When i >= 256, (1 << i) wraps around to small values, repeating the pattern of powers of 2 from the beginning.

// SPDX-License-Identifier: MIT
pragma solidity 0.8.20;

contract VulnerableRouter {
    function getPartition(uint256 size) public pure returns (uint256[] memory) {
        uint256[] memory partition = new uint256[](size);
        for (uint256 i = 0; i < size; i++) {
            partition[i] = 1 << i; // Overflow occurs when i >= 256
        }
        return partition;
    }

    function demonstrateOverflow(uint256 size) public pure returns (uint256[] memory) {
        require(size > 256, "Size must be greater than 256 to demonstrate overflow");
        return getPartition(size);
    }
}

2. Revised Code File:

// SPDX-License-Identifier: MIT
pragma solidity 0.8.20;

contract SafeRouter {
    function getPartition(uint256 size) public pure returns (uint256[] memory) {
+       require(size <= 256, "Outcome count exceeds maximum safe limit");
        uint256[] memory partition = new uint256[](size);
        for (uint256 i = 0; i < size; i++) {
            partition[i] = 1 << i;
        }
        return partition;
    }
}

• Recommendation:
  1. Implement a size check in the getPartition function to ensure it never processes more than 256 outcomes.
  2. Update the contract to handle markets with more than 256 outcomes differently, possibly by splitting them into multiple sub-markets or using a different representation for large outcome spaces.
  3. Add explicit checks in splitPosition, mergePositions, and redeemPositions to verify that the number of outcomes is within safe limits before calling getPartition.
  4. Consider using a more scalable approach for representing outcomes in markets with a very large number of possible outcomes.

[Rassska]

there will not be more than 256 outcomes

[greenlucid]

https://github.com/seer-pm/demo/blob/4e56254cbd071b6f678a108ccdb8660951636d27/contracts/src/interaction/conditional-tokens/ConditionalTokens.sol#L75

[clesaege]

Yeah, this limit is enforced by ConditionalTokens.