Almost all rarity rank combinations cannot be, and are not uniformly, generated

[c4-bot-7]

Lines of code

https://github.com/code-423n4/2024-02-ai-arena/blob/cd1a0e6d1b40168657d1aaee8223dc050e15f8cc/src/AiArenaHelper.sol#L107

Vulnerability details

Impact

Only a tiny fraction, $0.0002427 \%$, of all rarity rank combinations are possible. The probability distribution of the possible combinations (assuming the DNA is uniformly random) is not uniform: $24 \%$ of combinations are twice as likely as the rest.

Proof of Concept

AiArenaHelper.createPhysicalAttributes() may set six finalAttributeProbabilityIndexes using the following calculation.

uint256 rarityRank = (dna / attributeToDnaDivisor[attributes[i]]) % 100;
uint256 attributeIndex = dnaToIndex(generation, rarityRank, attributes[i]);
finalAttributeProbabilityIndexes[i] = attributeIndex;

attributeToDnaDivisor is by default [2, 3, 5, 7, 11, 13]. Each rarityRank by itself is in the range 0..99, and ostensibly the total number of combinations of the six rarityRanks should then be $100^6$. However, only $2,427,000$ different combinations are possible, which is only $0.0002427 \%$ of all combinations that should be possible.

As a function of dna the vector of the six rarityRanks repeats every $3,003,000$ integers ($=2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 100$). But it turns out that $576,000$ of these appear twice. For example, a dna of 0 or 1 yield the same combination of rarityRanks ($[0,0,0,0,0,0]$), as do 16 and 17 ($[8,5,3,2,1,1]$), and 22 and 23 ($[11,7,4,3,2,1]$), etc. That is, about $24 \%$ of the combinations are twice as likely as the rest.

The rarityRanks are input to dnaToIndex() which then will also be biased and restricted in output (depending on the attribute probabilities).

Recommended Mitigation Steps

Extract multiple small random numbers by repeatedly taking the modulo and dividing. I.e.

- uint256 rarityRank = (dna / attributeToDnaDivisor[attributes[i]]) % 100;
+ uint256 rarityRank = dna % 100;
+ dna /= 100;

Assessed type

Math

[c4-pre-sort]

raymondfam marked the issue as insufficient quality report

[c4-pre-sort]

raymondfam marked the issue as duplicate of #440

[c4-judge]

HickupHH3 marked the issue as selected for report

[HickupHH3]

agree that rarityRank determination isn't uniformly random.

[c4-judge]

HickupHH3 marked issue #1456 as primary and marked this issue as a duplicate of 1456

[c4-judge]

HickupHH3 changed the severity to 3 (High Risk)

[c4-judge]

HickupHH3 marked the issue as satisfactory

[c4-judge]

HickupHH3 changed the severity to 2 (Med Risk)

[c4-judge]

HickupHH3 marked the issue as not a duplicate

[c4-judge]

HickupHH3 marked the issue as primary issue

[c4-judge]

HickupHH3 marked the issue as selected for report