code423n4 commented 2 years ago

Lines of code

https://github.com/code-423n4/2022-09-artgobblers/blob/d2087c5a8a6a4f1b9784520e7fe75afa3a9cbdbe/src/ArtGobblers.sol#L638-L646

Vulnerability details

Impact

As more and more gobblers get minted, the emissionMultiples get more predictable.

By definition, randomness implies zero correlation between two or more generated random numbers. In other words, generation of the i_th random number should not influence at all the generation of the i+1_th random number. In reality there is no such thing as true randomness but we can assume this to be true for pseudorandom numbers since its the best we can do. Random numbers are used in 3 places in this contract.

Chainlink VRF: The number obtained from the chainlink VRF can be assumed to be truly random. We can assume that generation of the i_th random number bears no correlation with the generation of the i+1_th random number
Gobbler id: The gobbler id, is not truly random. This is because it is an outcome of the Knuth shuffle, and if a gobbler has already been minted with an id of x, another gobbler cannot be minted with the same id. So the generation of a gobbler DOES change the generation of future gobblers and their ids. This is however by design and is an accepted fact.
Gobbler Emission Rates: Gobbler emission rates are also NOT truly random, which is the main cause of this issue. This is because the result of the Knuth shuffle (value of swapIndex) is used to generate emissionMultiple.

This can be proven with a simple edge case consideration. Consider the situation where the last gobbler is going to be minted. All 9999 gobblers have already been minted. No matter what the chainlinkVRF returns, the gobbler id is fixed (since all other possible ids have already been assigned). Similarly, the value of distance from the statement

uint256 distance = randomSeed % remainingIds;

is also fixed and equal to 0 (since remainingIds = 1 for the last gobbler). So even before the generation of the random seed, the emission multiple can be determined.

For the case when only 2 gobblers are remaining, the variable distance can have only two values, with equal probabilities. So the emission multiple will also similarly have 2 possible values each with a probability of 0.5.

Extending this hypothesis to other values, the probability distribution function (PDF) of the emission multiple for the next gobbler to be minted can be easily calculated based on the state of the blockchain (data about the gobblers already minted). And with each subsequent mint, the probability distribution will change slightly since the emission multiple isn't random, but dependent on a conditional probability. A statistical model can be easily derived and gobblers can be minted at "opportune" moments when the emission multiple probabilities are skewed towards higher values.

(Note: If the PDFs of emissionMultiple are not of importance to the developers, this issue can be ignored. However, due to the existence of hardcoded numerical bounds in the code (linked code), the developers are forcing a PDF incorrectly which makes it more predictable as time goes on.)

Proof of Concept

No POC provided since this is a mathematical issue with PDFs.

https://github.com/carrotsmuggler/RandomnessPOC

A jupyter notebook can be found here with an implementation of the recommended fix, showing visualizations of the PDFs.

Tools Used

Jupyter, Foundry

Recommended Mitigation Steps

Use chainlinkVRF seed for generating emissionMultiple as well.

Use (swapIndex *randomSeed )%10000 to generate the emissionMultiplier

uint256 randomEmission = (swapIndex * randomSeed)%10000;
assembly {
                    // prettier-ignore
                    newCurrentIdMultiple := sub(sub(sub(
                        newCurrentIdMultiple,
                        lt(randomEmission, 7964)),
                        lt(randomEmission, 5673)),
                        lt(randomEmission, 3055)
                    )
                }

This has a number of benefits:

randomEmission is bounded between 0 and 10000, just like swapIndex. So the hardcoded numbers dont need to be changed.
True (pseudo)-randomness is used to generate emissionMultiple. Removes the conditional probabilities introduced by the KnuthShuffle.
Even the last gobbler is guaranteed to have a random emissionMultiple which will only be determined when revealed.

Shungy commented 2 years ago

Superb analysis. The impact is real and it justifies the severity.

FrankieIsLost commented 2 years ago

We disagree with this finding. Gobbler emission values are meant to be tied to specific gobbler ids at the specified cutoffs in the function. Additionally, we want a fixed number of gobblers to have each possible emission multiple. The suggestion in the issue would make the final gobbler counts with each emission multiple non-deterministic

GalloDaSballo commented 2 years ago

I believe that given the additional detail of a proper distribution, knowing the commit-reveal system of having to purchase N gobblers and then revealing them, we must agree that the distribution was deterministic as intended and while attempts on similar systems can be performed, in this system no leak of value or predictable exploit was shown

code-423n4 / 2022-09-artgobblers-findings