Element and weight correlation when `numElements` is multiple of 31

[c4-bot-2]

Lines of code

https://github.com/ArenaX-Labs/2024-02-ai-arena-mitigation/blob/1192a55963c92fb4bd9ca8e0453c96af09731235/src/FighterFarm.sol#L516-L517

Vulnerability details

Impact

When numElements is a multiple of 31 the DNA only generates 1/31 of all intended combinations of element and weight.

Proof of Concept

numElements maps to a uint8, i.e up to 255. In FighterFarm._createFighterBase() element and weight are set as

uint256 element = dna % numElements[generation[fighterType]];
uint256 weight = dna % 31 + 65;

This means that if numElements[generation[fighterType]] is multiple of 31, say k*31 then only k*31 different combinations are possible instead of k*31 * 31, since (n + k*31) % (k*31) == (n + k*31) % 31.

Recommended Mitigation Steps

Divide by the first mod to extract multiple smaller random numbers from one big random number.

uint256 weight = dna % 31 + 65;
dna = dna/31;
uint256 element = dna % numElements[generation[fighterType]];

Assessed type

Math

[c4-judge]

jhsagd76 marked the issue as satisfactory

[jhsagd76]

True, n will be [0,31)

[c4-judge]

jhsagd76 marked the issue as selected for report

[niser93]

My 2 cents on this issue:

The problem:

a = x mod(e)
b = x mod(31) + 65

The general solution:

a = x + e*k
b = x + 65 + 31*k

x = a - e*k
x = b - 65 - 31*k

a - e*k = b - 65 - 31 * k

b - a = 65 - (e-31) * k

As described by @d3e4, when n=31, there are only 31 reachable tuples (element, weight): (0, 65), (1, 66), ..., (30, 95). In the other cases, there is not a degenerate case.

The lack of combinations due to the multiple uses of the dna value with different moduli was already described in the original contest. @d3e4 reported this issue in #1979 describing rarityRank. I reported it in #1456.

For the reason above, we think the only right mitigation is to avoid having numElements[generation[fighterType]] = 31 and it could be a check in the FighterFarm.setNumElements() function:

FighterFarm.sol#L141-L144

  function setNumElements(uint8 newNumElements, uint8 generation_) external {
      require(msg.sender == _ownerAddress);
+     require(newNumElements != 31);
      numElements[generation_] = newNumElements;
  }

[d3e4]

@niser93 Any multiple of 31 is problematic:

This means that if numElements[generation[fighterType]] is multiple of 31, say k*31 then only k*31 different combinations are possible instead of k*31 * 31, since (n + k*31) % (k*31) == (n + k*31) % 31.

Also, summarily disallowing the problematic values is not fixing the problem. The randomness extraction should be correct to begin with.

[brandinho]

The number of elements will never be 31. Our current plans in fact are for less than 10, but if we're really pushing it then it might go as high as 16. We just used uint8 because it's the smallest uint that we're able to use. As such, this is not actually a risk to our project.

[jhsagd76]

Yep, if you do not use more than 30 elements, then of course this issue will not be triggered. But the max of uint8 is 255, here has never been a maximum value check in the code. Moreover, the issue related to the value 31 also appeared in the original contest such as https://github.com/code-423n4/2024-02-ai-arena-findings/issues/1456 and https://github.com/code-423n4/2024-02-ai-arena-findings/issues/1979 . No comments have ever mentioned this condition. In summary, this condition is neither in the code context nor in the context of this contest.