winning ticket odds are not distributed equally amongst users

[code423n4]

Lines of code

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

Vulnerability details

Impact

some users will be able to game the system and get optimal odds of winning both jackpot and non jackpot rewards. Making the entire protocol unfair for users.

Proof of Concept

The way Wenwin is intended to function is every combination has equal odds of winning. For example if the lotto was match 3 out of 4 possible numbers. there would be 4 winning combinations. However that is not the case. this table shows what the protocol expects the chance of winnig to be vs what I have found to be the acutal chance of winning.

Link to POC: https://gist.github.com/zouvier/8072a8f12bdfc5472652b14d25255b4f 20,000 iteration for POC: https://drive.google.com/file/d/1EfL_2Lar3Wj1NqVGm5unzV0HtDFnG-O_/view?usp=sharing

Expected Chance of winning					Actual chance of winning
25% (1/4)	1	1	1		25% (6/24)
25% (1/4)	1	1		1	8.3% (2/24)
25% (1/4)	1		1	1	12.5% (3/24)
25% (1/4)		1	1	1	54.16% (13/24)

The reason the odds are so skewed is because of two factors.

1. Decrementing current selection count numbers[i] = uint8(randomNumber % currentSelectionCount); randomNumber /= currentSelectionCount; currentSelectionCount--;

   The issue with decrementing current selection count is that it causes some numbers to have a higher chance of being called than others. For example if currentSelectionCount started at 4. Then on the first itteration of the loop randomNumber % currentSelectionCount will be randomNumber % 4. Making the possible return value 0,1,2,3. Once currentSelectionCount is decremented the possible return values are 0,1,2. And again, the options will be 0,1. As you can see the lower numbers have a higher probability of being selected.

2. Incrementing on duplicates if (selected[j]) { currentNumber++; } The problem will incrementing whenever there is a duplicate is it makes clumped numbers more likely to be chosen than numbers that are spread apart. For example given the same match 3 out of 4 numbers there is a 1/4 chance randomNumber % currentSelectionCount returns 0. Now on the second randomNumber % currentSelectionCount if it returns 0 that number will be changed to 1. and it could also just return 1. Meaning out of the 3 possible numbers 0,1,2. 2 of them will result in the number being 1, so 2/3. Now on the next itteration there is only two options 0 and 1. however both of these options will end up setting the number to 2 so 2/2. So now we have 1/4 2/3 2/2 = 1/6 chance of this sequence (0,1,2) beign selected. v.s. the exact oppisite scenario (3,2,1) which would be 1/4 1/3 1/2 = 1/24 chance of this sequence being selected.

Below I will show you how I found the odds for the best sequence. This can be applied to the other winning tickets and you will get the percentages I showed you in the table.

getting this winning ticket can happen in a variety of ways	0	1	1	1

Each of these is the order of which the ticket is created and the chance if each order happening.		3	2	1	1/4 2/3 2/2 = 1/6
	2	3	1	1/4 1/3 2/2 = 1/12
	2	1	3	1/4 2/3 1/2 = 1/12
	3	1	2	1/4 1/3 2/2 = 1/12
	1	2	3	1/4 1/3 1/2 = 1/24
	1	3	2	1/4 1/3 2/2 = 1/12

• 1/12 + 1/12 + 1/12+ 1/12+ 1/6 + 1/24 = 13/24 = 54.16%

You can repeat this for any and every sequence of numbers with parameters as small as match 3 of 4 to as large as the protocol allows. In every instance the winning ticket is always more likely to be the lowest numbers in the highest sequence.

If you look at the table it demonstrates this the lowest numbers with the highest sequence has the best chance to win (54.16%) while the biggest numbers that are the most spread apart have the lowest (8.3%).

Tools Used

Manual Analysis Forge test

Recommended Mitigation Steps

We reccomend not incrementing on duplicates. or recycling the same random number for the whole winning ticket.

One option would be to rertieve multiple random numbers from chainlink.

[c4-judge]

thereksfour marked the issue as satisfactory

[c4-judge]

thereksfour marked the issue as primary issue

[d3e4]

This is invalid. The ticket reconstruction algorithm is misunderstood by the wardens.

The ticket is reconstructed from the random number in two steps. First the random number is mapped to a representation of an ordered selection of numbers (numbers), then this selection is used to pick the numbers (which eliminates the selection order). numbers[i] is the numbers[i]-th (starting with 0) number picked from the list of numbers which have not yet been picked (they are counted one by one and the index (currentNumber) incremented by one for each encountered already picked). This means that the elements in numbers must sequentially decrement by one, as one number is picked each time. Thus numbers is effectively a representation of an integer with a varying base, and this is indeed how the random number is converted, by modulating by decrementing values. So the random number is effectively modulated by the total number of tickets and converted to this new base.

Let's see this with selectionSize = 3 and selectionMax = 4. The mapping from the random number to numbers is a follows: $0 \mapsto [0,0,0]$ $1 \mapsto [1,0,0]$ $2 \mapsto [2,0,0]$ $3 \mapsto [3,0,0]$ $4 \mapsto [0,1,0]$ $5 \mapsto [1,1,0]$ $...$ $21 \mapsto [1,2,1]$ $22 \mapsto [2,2,1]$ $23 \mapsto [3,2,1]$ $24 \mapsto [0,0,0]$ $25 \mapsto [1,0,0]$ $26 \mapsto [2,0,0]$ $...$

It cycles through the $24$ different numbers over and over, which implies a uniform distribution. Now this is used to pick numbers. selected starts with all unpicked: [0,0,0,0]. Note that selected is the same as ticket in binary. For the numbers $[0,1,1]$ we first pick the 0th index and get [1,0,0,0], then the 1st index of those remaining is picked and we get [1,0,1,0] and finally the 1st index of those now remaining is picked and we have the ticket [1,0,1,1], i.e. the picked numbers 1, 3 and 4 (in that order). Note that different selection representations can result in the same final selection through a different selection order. For example, we can pick the same numbers by instead picking the 2nd index, then the 2nd index of those remaining, then the 0th index of those remaining, i.e. the numbers 3, 4 and 1 (in that order). Thus $[0,1,1]$, $[0,2,1]$, $[2,0,1]$, $[2,2,0]$, $[3,0,1]$, $[3,2,0]$ represent the ordered picks $(1,3,4)$, $(1,4,3)$, $(3,1,4)$, $(3,4,1)$, $(4,1,3)$, $(4,3,1)$, which are all the same ticket [1,0,1,1].

In the duplicates of this issue, the wardens who have provided a Python implementation have incorrectly translated the dynamic for-loop in TicketUtils.sol#L68-L72, except #131 which uses inadmissible parameters.

[c4-judge]

thereksfour marked the issue as nullified

[c4-judge]

thereksfour marked the issue as not nullified

[c4-sponsor]

rand0c0des marked the issue as sponsor disputed

[c4-judge]

thereksfour marked the issue as unsatisfactory: Invalid