If random number is too low, the lottery not completely random

---

<https://github.com/code-423n4/2023-03-wenwin/blob/91b89482aaedf8b8feb73c771d11c257eed997e8/src/TicketUtils.sol#L43-L76&gt;

---

Summary

Random numbers below a certain limit will always return at least one rightmost bit, while numbers above this limit will return random bits.

Explanation:

1. The winning ticket is generated based on an array of numbers generated by module randomNumber to selectionMax-n.:

• src/TicketUtils.sol:57-61

  for (uint256 i = 0; i < selectionSize; ++i) {
  numbers[i] = uint8(randomNumber % currentSelectionCount);
  randomNumber /= currentSelectionCount;
  currentSelectionCount–;
  }

2. The randomNumber is provided by the chainlink and may be any number between 0 and type(uint256).max

3. If the randomNumber is too low, the last elements of the numbers array become 0,0,…

4. The winning ticket is the result of shifting 1 bit to each of the numbers array, if the numbers element is greater than one of the previous selected elements, it is incremented by 1. So that […, 0, 0, 0, 0] becomes […, 0, 1, 2, 3]

for (uint256 i = 0; i < selectionSize; ++i) {
    uint8 currentNumber = numbers[i];
    // check current selection for numbers smaller than current and increase if needed
    for (uint256 j = 0; j <= currentNumber; ++j) {
        if (selected[j]) {
            currentNumber++;
        }
    }
    selected[currentNumber] = true;
    ticket |= ((uint120(1) << currentNumber));
}

5. Which results in the winning ticket having the four(In this particular example) most rights bits.

NOTE: Later in the report, I call the ticket number with the most right bits Unfair Number. NOTE: The smallest number that makes a winning ticket truly random, I call the Safe Random Number.

Calculations:

1. If randomNumber <= selectionMax: the winning number will consist of selectionSize most right bits.
2. If randomNumber <= (selectionMax * (selectionMax - 1)): wining number will consist of selectionSize - 1 rights bits
3. To be safe randomNumber must be greater than (selectionMax * (selectionMax - 1) * (selectionMax - 2) * … * (selectionMax - (selectionSize-2))).

Impact:

A user who selects a ticket with the Unfair Number always has a better chance of winning than a user who selects any not right bits. ( Because every number below the Safe Random Number will return at least one most right bit, But any number above the Safe Random Number will return completely random bits. ).

But because of the probabilities, I think the problem is medium, if not low.

Probabilities:

1. By default, as I understand from .env.example and Documentation, selectionSize will be set to 7 and selectionMax will be set to 35.
   Assuming randomNumber has an equal chance of being any positive number between 0 and type(uint256).max, the probability of getting Unfair number if equal to (3534333231*30)/(2**256-1) == 1.0092876e-68

2. The maximum value of selectionMax is 119 and the maximum value of selectionSize is 16. Probability of getting “Unfair Number” if equal:

(119118117116115114113112111110109108107106105)/(2**256-1) == 4.67453e-47

As I said before, the probability is too small to use this vulnerability as a way to drain the lottery, but enough to conclude that the lottery is not entirely fair in its current state.

PoC:

NOTE: Run with -vvvvv if you want to see logs in fuzzing mode

// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.19;

import "forge-std/console2.sol";
import {WenwinPoC} from "../src/Wenwin-predict.sol";
import "forge-std/Test.sol";

contract WenwinTEST is WenwinPoC, Test {
    uint120 private constant mostRightTicket = 127;
    uint120 private constant mostLeftTicket = 34091302912;
    uint8 private constant selectionSize = 7;
    uint8 private constant selectionMax = 35;
    uint256 private constant SAFE_NUMBER_BASE =
        35 * 34 * 33 * 32 * 31 * 30 * 29;
    uint256 private constant ALWAYS_1_MOST_RIGHT = SAFE_NUMBER_BASE / 29;
    uint256 private constant ALWAYS_3_MOST_RIGHT =
        SAFE_NUMBER_BASE / 29 / 30 / 31;
    uint256 private constant ALWAYS_5_MOST_RIGHT =
        SAFE_NUMBER_BASE / 29 / 30 / 31 / 32 / 33;

    uint256 private constant _1_MOST_RIGHT = 1;
    uint256 private constant _3_MOST_RIGHT = (1 << 2) + (1 << 1) + 1;
    uint256 private constant _5_MOST_RIGHT = (1 << 4) + (1 << 3) + (1 << 2) + (1 << 1) + 1;

    // uint256 private constant UNSAFE_NUMBER_BASE = 35 * 34 * 33;

    // @note Any random number below safe zone will always have a "static" bit/s (e.g. this fuzz should never fail)
    function test_log_wenwin_unsafe(
        uint256 _first,
        uint256 _third,
        uint256 _five
    ) public {
        _first = bound(_first, 0, ALWAYS_1_MOST_RIGHT);
        uint256 _predict1 = predict_ticket(_first, selectionSize, selectionMax);
        console2.log(toBinaryString(_predict1));
        assertEq((_predict1 & _1_MOST_RIGHT), _1_MOST_RIGHT);

        _third = bound(_third, 0, ALWAYS_3_MOST_RIGHT);
        uint256 _predict3 = predict_ticket(_third, selectionSize, selectionMax);
        console2.log(toBinaryString(_predict3));
        assertEq((_predict3 & _3_MOST_RIGHT), _3_MOST_RIGHT);

        _five = bound(_five, 0, ALWAYS_5_MOST_RIGHT);
        uint256 _predict5 = predict_ticket(_five, selectionSize, selectionMax);
        console2.log(toBinaryString(_predict5));
        assertEq((_predict5 & _5_MOST_RIGHT), _5_MOST_RIGHT);
    }

    // @note Any random number above safe zone will always have a trully random bits (e.g. this fuzz should fail)
    function test_log_wenwin_safe(
        uint256 _first,
        uint256 _third,
        uint256 _five
    ) public {
        _first = bound(_first, ALWAYS_1_MOST_RIGHT, type(uint256).max);
        uint256 _predict1 = predict_ticket(_first, selectionSize, selectionMax);
        console2.log(toBinaryString(_predict1));
        assertEq((_predict1 & _1_MOST_RIGHT), _1_MOST_RIGHT);

        _third = bound(_third, ALWAYS_3_MOST_RIGHT, type(uint256).max);
        uint256 _predict3 = predict_ticket(_third, selectionSize, selectionMax);
        console2.log(toBinaryString(_predict3));
        assertEq((_predict3 & _3_MOST_RIGHT), _3_MOST_RIGHT);

        _five = bound(_five, ALWAYS_3_MOST_RIGHT, type(uint256).max);
        uint256 _predict5 = predict_ticket(_five, selectionSize, selectionMax);
        console2.log(toBinaryString(_predict5));
        assertEq((_predict5 & _5_MOST_RIGHT), _5_MOST_RIGHT);
    }

    function toBinaryString(uint256 n) private pure returns (string memory) {
        string memory buffer = new string(7);
        uint256 ptr;

        assembly {
            ptr := add(buffer, add(32, 7))
        }

        for (uint i = 0; i < 7; ++i) {
            ptr--;
            assembly {
                mstore8(ptr, byte(mod(n, 2), "01"))
            }

            n /= 2;
            if (n == 0) break;
        }

        return buffer;
    }
}

NOTE: - “…/src/Wenwin-predict.sol” Just copy of project function:

// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.19;

import "forge-std/console2.sol";

contract WenwinPoC {
    function predict_ticket(
        uint256 randomNumber,
        uint8 selectionSize,
        uint8 selectionMax
    ) internal returns (uint256 ticket) {
        /// Ticket must contain unique numbers, so we are using smaller selection count in each iteration
        /// It basically means that, once x numbers are selected our choice is smaller for x numbers
        uint8[] memory numbers = new uint8[](selectionSize);
        uint256 currentSelectionCount = uint256(selectionMax);

        for (uint256 i = 0; i < selectionSize; ++i) {
            numbers[i] = uint8(randomNumber % currentSelectionCount);
            randomNumber /= currentSelectionCount;
            currentSelectionCount--;
        }

        bool[] memory selected = new bool[](selectionMax);

        for (uint256 i = 0; i < selectionSize; ++i) {
            uint8 currentNumber = numbers[i];
            // check current selection for numbers smaller than current and increase if needed
            for (uint256 j = 0; j <= currentNumber; ++j) {
                if (selected[j]) {
                    currentNumber++;
                }
            }
            selected[currentNumber] = true;
            ticket |= ((uint120(1) << currentNumber));
        }
    }
}

Mitigation:

1. Reject randomNumber below Safe Random Number OR
2. Increase the randomNumber if it is too low:

uint256 internal immutable SAFETY_ZONE;

constructor(uint8 selectionSize, uint8 selectionMax) {
    uint256 safety_cap = selectionMax;
    for (uint i = 1; i < selectionSize; ++i) {
        safety_cap *= selectionMax - i;
    }
    SAFETY_ZONE = safety_cap
}


for (uint256 i = 0; i < selectionSize; ++i) {
    numbers[i] = uint8(randomNumber % currentSelectionCount);
    randomNumber /= currentSelectionCount;
    currentSelectionCount--;
    if (randomNumber < SAFETY_ZONE) {
        randomNumber <<= 2;
    }
}  

---

The text was updated successfully, but these errors were encountered:

All reactions