Flawed randomness when constructing winning ticket

[code423n4]

Lines of code

https://github.com/code-423n4/2023-03-wenwin/blob/main/src/TicketUtils.sol#L43:#L76

Vulnerability details

To generate a winning ticket, Wenwin gets one big random number from Chainlink, and manipulates it to generate the different number components of the winning ticket. This manipulation is flawed and breaks the randomness of the winning ticket.

Impact

Some numbers are more likely to be winners than others. The lottery is not fair, and being fair is the fundamental functionality of a lottery. As people might waste their money choosing tickets that have less chance of winning, we believe this is a high impact bug.

Proof of Concept

We'll start with an intuitive description of the problem, and then present a test demonstrating the flawed distribution. For a quick TLDR, you can jump straight ahead to the proof section.

Intuition

This is the first part of the algorithm - notice currentSelectionCount:

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

The random number is chosen by calculating randomNumber % currentSelectionCount, and currentSelectionCount is constantly decremented, and so the biggest possible number can only be selected in the first iteration. For example, if we're choosing 4 numbers out of 0-9, then 9 itself could only be chosen in the first round - as after that the random number would be modulo 9, then modulo 8, etc'.

So it seems that the last number has less chance of occuring.

Perhaps the next section was supposed to fix the problem:

        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));
        }

We see it increases the numbers, but on the surface there's no apparent reason as to why this will fix the distribution. Additionally, we can see this algorithm is not symmetrical - it depends on the order that the numbers were chosen. For example, if in the first section "4,3,2,1" were selected, the inner loop in the second section would not increment anything and the winning ticket will remain "4,3,2,1". But if "1,2,3,4" were chosen, the inner loop in the second section would make the ticket be "1,3,5,6". This again is a hint that the algorithm is flawed.

Proof of flawed distribution

To test this, we created a Python script to test the distribution of numbers chosen using this algorithm. We're choosing 4 numbers out of 0-9, and we're doing this 100000 times, in the end printing the number of occurrences of each number. You can find the script here. This is it's output for the currently implemented algorithm:

digit   occurences
0   40167
1   41140
2   41371
3   40938
4   41032
5   41280
6   41135
7   41062
8   40540
9   31335

We see that the last digit has only 31% of occurring, while the rest have roughly 41%. This proves that indeed the winning ticket is not chosen uniformly and fairly.

Recommended Mitigation Steps

Change the function so it will not decrement currentSelectionCount in the first loop, And in the second loop, to get rid of duplicates, increment the chosen number (modulo selectionMax) until you reach a new number. (Note that in the following snippet you can also substitute currentSelectionCount for selectionMax.)

        uint8[] memory numbers = new uint8[](selectionSize);
        uint256 currentSelectionCount = uint256(selectionMax);

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

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

        for (uint256 i = 0; i < selectionSize; ++i) {
            uint8 currentNumber = numbers[i];
            while (selected[currentNumber]) {
                currentNumber = (currentNumber + 1) % currentSelectionCount;
            }
            selected[currentNumber] = true;
            ticket |= ((uint120(1) << currentNumber));
        }
    }

While we can not mathematically prove this script provides a fully uniform distribution, we have tested it in Python (see same script), and we can see that indeed the distribution looks uniform, and every number has a 40% of appearing.

digit   occurences
0   39874
1   40074
2   39962
3   40097
4   39962
5   39973
6   40028
7   39957
8   40176
9   39897

[c4-judge]

thereksfour marked the issue as duplicate of #475

[c4-judge]

thereksfour marked the issue as satisfactory

[c4-judge]

thereksfour marked the issue as unsatisfactory: Invalid