AI Arena - niser93's results

raymondfam marked the issue as sufficient quality report

raymondfam marked the issue as duplicate of #33

raymondfam marked the issue as duplicate of #1626

HickupHH3 marked the issue as satisfactory

raymondfam marked the issue as insufficient quality report

raymondfam marked the issue as duplicate of #15

HickupHH3 changed the severity to 2 (Med Risk)

HickupHH3 marked the issue as duplicate of #1191

HickupHH3 marked the issue as not a duplicate

HickupHH3 marked the issue as duplicate of #1979

HickupHH3 marked the issue as satisfactory

Hi @HickupHH3. First of all, thank you for your judgment. I would like to point your attention to a few considerations on this finding, and why I consider it a high-severity issue:

• This issue is strongly related to #366 reported by Abdessamed and others (and also by me, #736 ). It's also related to #1017 reported by Aslanbek (and also by me, #519). The former is a high-severity issue, the latter a medium one. The point is that these two issues can be exploited very easily thanks to the wrong math behind the computation of physical attributes. The brute force exploit can be done with less effort by the attacker. But this issue doesn't just represent something complementary to those two issues. We should consider that even if developers increase the space of physical attributes thinking to make those attacks infeasible, they wouldn't become so hard, thanks to the wrong math that I showed here.
• According to the high severity definition, assets are compromised. In this DApp, the assets are the NFT of fighters. They would have a value based on their attributes. Without this finding, developers, players, and the market, in general, would give a very wrong value to fighters based on math that doesn't work correctly. The percentages proposed by developers and hard-written on the contract wouldn't represent anything but will be a reference on which the market will compute NFT values. A player with a fighter that should be found with the probability of 1/10000 and has a huge amount of value will see the value decrease suddenly without any reason if somebody makes public the wrong math when this DApp is in the wild.
• This issue is a Math issue, like I said before. So, I think it needs a POC that explains the math behind the problem and gives the possibility to developers to improve their code. In my POC, I deeply explore the implications of the pseudo-random technique and modulus operation. For this reason, my problem should be selected for the report. In my mitigation proposal, I don't just suggest a random algorithm using an oracle. I like the will of developers to avoid a fully random approach and I think some methods can work. For this reason, and thanks to my math analysis, I proposed an alternative to developers. A math finding like this should have an extensive POC to explain mathematical steps.
• In other related findings, #1979 and #440, wardens correctly report the lack of combinations, but they are just talking about rarityRank that doesn't represent the physical attribute. For this reason, I think it is a bit different finding from mine, and I would like to show why. They explain that 2,427,000 combinations are possible, far from 100⁶. Those combinations are used by the dnaToIndex function to compute the attribute value. Let's see dnaToIndex() like a black box, and let's consider that we have 6 physical attributes from 1 to 10, i.e., 10⁶ possibilities (they are less than 2,427,000). This means that every combination of physical attributes has two rarityRank combinations to obtain it. From this point of view, the math behind physical attributes seems correct and #1979 and #440 are invalid. The problem isn't inside the lack of combinations of rarityRank, but the usage by the dnaToIndex function of rarityRank and the distributions of rarityRank combinations over the space of possibilities. For this reason, #1979 and #440 report a very partial view of this finding, and it needs more sophisticated math to understand it.

In conclusion, I hope I was able to explain my point of view. I think that my finding will have a strong impact on developers and their reasoning about the math behind physical attributes. Furthermore, I think that my finding was the only one that reported this kind of issue that isn't just related to the space of probabilities, but to the usage of modular arithmetic. For these reasons, I'm asking you to reconsider the severity of this issue and the correlation of it with #1979 and #440.

Thank you!

HickupHH3 marked the issue as selected for report

HickupHH3 changed the severity to 3 (High Risk)

I agree with the above comment in that the impact is High since it is on the valuation of fighters which are - or are directly related to - the assets of the protocol. But since the comment then also contests some aspects of the duplicate issues, I feel I need to respond to those points.

Lest there be any misunderstanding, I am not trying to invalidate anything, and I believe #1456, #1979 and #440 are all valid and duplicate of each other.

The comment claims that focussing on the rarityRank is insufficient since the problem rather lies in some combinations of attributes being impossible (rather than simply non-uniformly distributed). However, this entirely depends on the probabilities, which are unknown (the test is not a source of truth). And this is just a trivial special case of the more general lack of uniformity. This report only discusses at length an example of this, but does not arrive at a general quantification of it, and is thus ultimately of little added value.

The suggested mitigation in this report is incorrect. I'm assuming what was meant is rather (((dna/2) % 101) * 100) / 101, to avoid the obvious rounding issue. But even then we have the problem of duplicate values. This does obviously not return values uniformly in the range [0,99] since e.g. 101 values are being squeezed into 100. E.g. ((0 * 100) / 101 = ((1 * 100) / 101 = 0, which is thus the twice as likely value. In fact this changes very little from the original distribution issue, and pairs of DNAs (0, 1), (16, 17), and (22, 23) still give the same result (cf. the examples given in #1979). Only the period of 3,003,000 has increased to 1.6041e12 (the non-uniformity remains essentially the same). The warden has misunderstood the mathematical reason for this issue, thinking the problem lies in the usage of mod 100 whereas it really is in the use of divisors to extract small random numbers from a big random number.

#1979 and #440, on the other hand, both propose the same correct mitigation. This alone I think should be sufficient to disqualify #1456 from being selected as the report.

Both #1979 and #440 show that the number of possible combinations is far too small. But #1979 is the only report that provides a quantification of the lack of uniformity, namely that there are exactly 2,427,000 possible combinations of which 576,000 (24%) are twice as likely. I think this merits selecting #1979 for the report.

This report and its duplicates provide a very clever proof that the rarityRank generated are not uniformly random. Mainly that there exists two rarity ranks $r_1, r_2 \in R$, where $R$ is the set of all possible rarity ranks such that probability of obtaining rarity rank $r_1$ is not equal to the probability of obtaining the rarity rank $r_2$. To that I say kudos!

However, I am not sure whether this would qualify as High severity.

Firstly, the attacker does not have control over the random generation process, which is one of the reasons cited for upgrading this to a high severity.

This issue is strongly related to https://github.com/code-423n4/2024-02-ai-arena-findings/issues/366 reported by Abdessamed and others (and also by me, https://github.com/code-423n4/2024-02-ai-arena-findings/issues/736 )

Secondly, the reports consider the non-uniformness of the rarityRank but do not consider how this affects the attribute indices. So let me explain it simply,

• Let us consider two parts of the fighter, the eyes and the head.
• Suppose that probability of generating a Diamond Eyes is $\frac{1}{100}$
• And the probability of generating a Diamond Head is $\frac{1}{100}$
• Intuitively you might think that the probability of generating a fighter with Diamond Head and Diamond Eyes is $\frac{1}{100}*\frac{1}{100}=\frac{1}{10000}$
• But these reports and its duplicates show that that may not be true, that the probability of generating a fighter with Diamond Head and Diamond Eyes may not be in fact $\frac{1}{10000}$ and in some cases, it may be impossible.

However, this does not consider the probabilities of generating these items individually are still correct. More specifically, the probability of generating a fighter with a Diamond Head is still $\frac{1}{100}$ and the probability of generating a fighter with a Diamond Eyes is still $\frac{1}{100}$.

Whether or not this warrants a High is up to the judge @HickupHH3 , but I would just like to state the facts here.

And if this is a high, I would also like you to consider upgrading https://github.com/code-423n4/2024-02-ai-arena-findings/issues/112 to a high considering that it affects the probabilities (of the first and last indices) of each individual item by skewing them by $\frac{1}{100}$.

@d3e4 Thank you for your comment. What you wrote is the reason why I proposed to judge to divide my finding from #1979 and #440 : we reported two different issues. While my finding is about the impossibility having all combinations of physical attributes, #1979 and #440 report the lack of uniform distribution of rarityRank array. Like I said above, they aren't the same thing: even if we had a uniform distribution of rarityRank, we can have the impossibility having all combinations of physical attributes.

I would to go deeper into your mitigation proposal to understand together if there could be a better approach:

#1979

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

In this proposal, the rarityRank value isn't based on i anymore. This means you are computing the rarityRank vector in this form: [n,n,n,n,n,n], where n is the last two digits of the dna value. I want to show why this kind of solution doesn't solve the issue I reported, and why for this reason, #1979 is a different finding from mine. Let's think you are using the AttributeProbabilities proposed in Deployer.s.sol#L25-L32: I want to show that is not possible to obtain head=1 and eyes=2 (i.e. there exists a pair that is infeasible). To obtain head=1, you should have a dna that has the last two digits in the range [0:13]. To obtain eyes=2, you should have a dna that has the last two digits in the range [16:31]. Of course, these two ranges are not compatible. In this case, I want to underline that the issue isn't related to the AttributeProbabilities vector. Whatever AttributeProbabilities vector you choose, there will be a counterexample with a pair of physical attributes that is infeasible.

#440

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

This solution is quite similar to #1979:

i = 0; rarityRank = dna_digits[-2:]
i = 1; rarityRank = dna_digits[-3:-1]
i = 2; rarityRank = dna_digits[-4:-2]
and so on

In this case, this approach could work with many AttributeProbabilities vectors, but there are AttributeProbabilities vectors where this approach can fail. Let's do an example:

25      function getProb() public {
26          probabilities.push([79, 10, 11]); //head
27          probabilities.push([7, 2, 91]); //eyes
32      }

I want to show that head=1 and eyes=2 is infeasible. Let's consider the last 3 digits of dna: ABC

for i=1 (head) we have rarityRank = BC for i=2 (eyes) we have rarityRank = AB

To have head = 1, BC must be less than 80, i.e., B must be in the range [0:7] To have eyes = 2, AB must be 8 or 9, i.e. B must be in the range [8:9]

These two ranges are clearly not compatible.

The mitigation proposals of #1979 and #440 don't solve my finding because they aren't developed for it. They try to solve a different problem: the uniform distribution of rarityRank over the space of probabilities. And considering this, they work and are good. Because dna can be every number from 0 to 2²⁵⁵ - 1, the computation of rarityRank just based on the dna value must work. However, the computation of rarityRank must be not reversible. In the solutions proposed above, it is easy to find a dna to obtain some combination of physical attributes (if that combination is feasible).

My finding is a bit different and reports a different issue: even if the element of rarityRank for each attribute is well distributed, if its computation isn't done using coprime numbers and avoiding mod 100, the set of combinations for each physical attribute will not overlap, leading to the incompatibility of some values of physical attributes with each other. My mitigation proposal tries to solve it (it doesn't try to make every combination of rarityRank reachable, but it tries to make every combination of physical attributes reachable). Furthermore, it uses an unreversible function. This means that an attacker must iterate, in the worst case, over 1.6041e12 combinations to obtain the wanted combination of physical attributes.

I also want to point your attention to the @Haxatron point of view. The attacker does not have the control over random generation process. However the attacker could potentially modify the value of assets when he/she publicly discloses these two problems: if he/she discloses the problem of uniform distribution, the market will change accordingly with a new different probabilities vector. If he/she discloses the fact that some combinations of physical attributes are infeasible, the market will change removing the infeasible combinations from the supply, modifying the value of feasible combinations consequentially. In both cases, the attacker is able to directly impact the value of assets.

While my finding is about the impossibility having all combinations of physical attributes, #1979 and #440 report the lack of uniform distribution of rarityRank array.

I think you should take another look at #1979 and #440. I don't understand your point here. The impossibility of having all combinations of physical attributes is a special case of the impossibility of having all combinations of rarity rank.

First Impact section sentence of #1979: "Only a tiny fraction, $0.0002427%$, of all rarity rank combinations are possible". This is very clearly "about the impossibility having all combinations of physical attributes" as well.

From #440 Impact's section: "making certain combinations of attributes unattainable", which explicitly mentions attributes, not only rarity rank.

On the other hand, you wrote...

Let's consider the last 3 digits of dna: ABC

for i=1 (head) we have rarityRank = BC for i=2 (eyes) we have rarityRank = AB

Given that the recommended mitigation was to first divide by 100, not 10, shouldn't this be:

Let's consider the last 4 digits of dna: ABCD

for i=1 (head) we have rarityRank = CD for i=2 (eyes) we have rarityRank = AB

I think this isn't correct. I think that "the impossibility of having all combinations of rarity rank is a special case of the impossibility of having all combinations of physical attributes": we could have all combinations of physical attributes without having all combinations of rarity rank. Even if we have a tiny fraction of all rarity rank combinations that are possible, we could still have all combinations of physical attributes. Having tiny fraction of all rarity rank combinations don't prove that there are combination of physical attributes that are infeasible.

About #440 i'm sorry: my mistake. It cover all physical attributes with the mitigation proposal. It works correctly, in this way. This because the dna becomes just a sequence of pairs and of course this solution is able to cover all combinations of rarity rank (and so, all combinations of physical attributes). But in this way, it is very easy to build a dna to obtain the wanted physical attributes, i.e., it doens't need to bruteforce dna in order to obtain the wanted physical attributes

I think this isn't correct.

See https://en.wikipedia.org/wiki/Special_case. The root problem is missing rarity rank combinations. Depending on the probabilities of attributes, there are subsets of scenarios in which an entire bunch of rarity rank combinations mapping 100% to attribute combinations is missing. This is a special case (i.e. a subset of all possibilities) of missing rarity rank combinations.

i'm going to need some time to digest the arguments made here, but do continue the conversation, any final notes & comments (closing arguments) you'd like to make, kindly do so~

The value of a fighter NFT relies on its physical attributes. This means that the root problem is missing physical attributes combination. Rarity rank is just used to compute physical attributes.

Let's think you have 6 physical attributes from 1 to 10: 10⁶ combinations. If you have at least 10⁶ rarity rank combination, you can build a mapping between rarity rank and physical attributes and you can obtain every combination of physical attributes (maybe with wrong probabilities, as you reported, but you can write a mapping to have at least a link between each pair of rarity rank vector and physical attributes vector)

About special case, from Wikipedia: A is a special case or specialization of concept B [means] "If B is true, one can immediately deduce that A is true as well, and if B is false, A can also be immediately deduced to be false." This is wrong. The correct statement is "If A is true, one can immediately deduce that B is true as well, and if B is false, A can also be immediately deduced to be false." (the example of square and rectangle could help to understand). This means that: (A implies B) and (NOT(B) implies NOT(A))

You wrote "The impossibility of having all combinations of physical attributes is a special case of the impossibility of having all combinations of rarity rank".

Let's define B = having all combinations of physical attributes A = having all combinations of rarity rank

You wrote: NOT(B) is a special case of NOT(A), so

(NOT(A) implies NOT(B)) and (B implies A)

that is equivalent to

The impossibility of having all combinations of rarity rank implies the impossibility 
of having all combinations of physical attributes

and

having all combinations of physical attributes implies having all combinations of rarity rank

I think they are both false.

On the other hand

I wrote "the impossibility of having all combinations of rarity rank is a special case of the impossibility of having all combinations of physical attributes".

I wrote: NOT(A) is a special case of NOT(B), so

(NOT(B) implies NOT(A)) and (A implies B)

that is equivalent to

the impossibility of having all combinations of physical attributes implies the impossibility 
of having all combinations of rarity rank

and

having all combinations of rarity rank implies having all combinations of physical attributes

That I think are both correct.

Anyway, I don't want to formalize on this aspect. The meaning of "special case" and the logic behind can help to understand, but can also bring off the road. The main point is this: we can have a subset of rarity rank and still build a mapping to the whole space of physical attributes. The "tiny fraction of all rarity rank combinations" doesn't implies the "tiny fraction of all rarity rank physical attributes", that is the thing we care about.

I hope i was able to explain my point of view. I would like to thank @d3e4, @fnanni-0 and @Haxatron for their observation that for sure will help to improve Ai-Arena security. @HickupHH3 thank you for your work. We talked about many things in this comments. The fact that these arguments are so complex is the proof that this issue was hidden very well and we should be proud of our work.

@niser93 I understand your point, but it is still just a special case. Maybe you misunderstood that this non-uniformity extends to the entire range of $100^6$ rarity rank combinations. These can have any of three different probabilities: $\frac{1}{2427000}$, $\frac{2}{2427000}$ and $0$. $0$ of course means they are impossible, which is what leads to your special case. But we cannot say anything specific about this without knowing the attribute probabilities. It could be that all attribute combinations still are possible, but with different probabilities. You delve into an example of how it could happen that some are impossible, but don't even discuss the difference in probabilities among those that are possible. Thus your report actually misses the root cause, but since your example (which is good) is indeed merely a trivial consequence of the root cause, and so one can easily reason backwards to find it, I think that's ok.

About my mitigation proposal, it was perhaps not clear that this was intended to be inside a for-loop, so it would depend on i, dividing by 100 for each i. Go rather by the description: "Extract multiple small random numbers by repeatedly taking the modulo and dividing.". Your example with AB and BC is incorrect. My mitigation (and #440) would return disjoint consecutive pairs of digits, i.e. if ABCD are the last four digits of the DNA, it would use CD and then AB. These numbers are all independent and uniformly distributed in the range [0, 99].

Since your mitigation extends the range much more than 3,003,000, it would indeed be more likely to cover all rarity rank combinations (but would probably still have some gaps since we only cover it 1.6041 times), but the root issue of non-uniformity remains. Also, brute-forcing a range of 1.6041e12 for a reverse image is not hard to do (except perhaps for Python...), but not even necessary since your mitigation is not a cryptographic hash function. And this argument is irrelevant anyway because we only need to brute-force a modest multiple (e.g. $-\ln{(1-0.99)} \approx 4.6$ for a 99% chance) of $100^6$ to expect to find a specific $1$ in $100^6$ attribute combination, if they are uniformly distributed.

@HickupHH3 Here is a summary:

Fundamental Issue: Not all rarity rank combinations are possible, and some are more likely than others.

Trivial Corollary: Impossible rarity rank combinations implies impossible attribute combinations.

It is trivial because the rarity rank sets the attribute combinations. There is nothing wrong with the function from rarity ranks to attributes itself; it is perfectly legitimate if an attribute combination could be set only by one or a few rarity rank combinations. If these specific rarity rank combinations cannot be obtained, then the attribute combination cannot be obtained. Therefore this corollary is not by itself an issue at all.

#1979 and #440 directly discuss the Fundamental Issue. #1456 only discusses the Trivial Corollary. But since it follows trivially, such that one should realise the Fundamental Issue as well when reading the corollary, I think #1456 should be considered sufficient as a duplicate.

Mitigation: The correct mitigation is the one offered by #1979 and #440. The one in #1456 is invalid.

More valuable information in #1979 #1979 and #440 are basically the same. But #1979 adds a precise quantification of how many rarity rank combinations are possible (2,427,000), and what the distribution is (24% twice as likely as the rest). #440 only gives an upper bound for the possible rarity rank combinations (3,003,000) and says that some appear more than once (without quantifying). I think this extra information provided by #1979 is valuable, because e.g. had only single combination been more likely the issue would not have been nearly as severe.

For these reasons I think #1979 should be selected for the report.

Fundamental Issue:
Not all rarity rank combinations are possible, and some are more likely than others.

Trivial Corollary:
Impossible rarity rank combinations implies impossible attribute combinations.

It is trivial because the rarity rank sets the attribute combinations

I want to stress this: the goal isn't to reach all rarity rank combinations. The goal is to reach all physical attributes combination. A method to reach all physical attributes combinations is a solution of the problem and a valid mitigation. The fact that there are rarity rank combinations that are not reachable doesn't imply that there are physical attributes that are not reachable.

Severity

Decided on medium.

Firstly, the attacker does not have control over the random generation process, which is one of the reasons cited for upgrading this to a high severity.

Unlike #366 and #736, while the user can influence uint256 dna generation, they need to fight the right ingredients that hashes together to obtain the desired value instead of direct selection. This is just the first step: there's also figuring out what's the best value that can map to the rarest rank combination.

In other words, there's significant brute force effort needed.

Duplication

Since some fancy math broke out in the discussion, I gotta match it with my applied math major, but I'll keep it simple =)

Issues #1979 and #440 argue that the function mapping DNA to rarity rank combinations $f: X -> Y$ is non-injective: $\exists y \in Y s.t. \exists x_1 \neq x_2 \in X, f(x_1) = f(x_2) = y$.

this issue (#1456) is arguing that the function mapping rarity rank combinations to physical attributes combinations $g: Y -> Z$ is non-surjective: $\exists z \in Z s.t. \forall y \in Y, g(y) \neq z$.

From this, it's clear that #1456 and #1979 + #440 should be bucketed into 2 different groups.

HickupHH3 changed the severity to 2 (Med Risk)

@HickupHH3 Thanks a lot for judging and taking the time to thoroughly review this discussion. I agree with medium severity. However, I’d like to bring Code4rena duplicate guidelines to the table, because I can't understand the argument for splitting this issue. The math discussion might have deviated the topic from what matters most in this decision:

Similar exploits under a single issue

Findings are duplicates if they share the same root cause.

More specifically, if fixing the Root Cause (in a reasonable manner) would cause the finding to no longer be exploitable, then the findings are duplicates.

The argument you provided for de-duplicating these issues seems to be about impact, not root cause. The root cause is that not all rarity rank combinations are possible. This affects (1) the probability distribution of the possible combinations of rarity ranks, and (2) often, depending on the probability arrays, attribute combinations might not be possible.

In my opinion (2) is trivial at least for some cases and I even mentioned it in #440 although I didn't provide proof for it. Also note that #1456 proposes a change in the rarity rank calculation as mitigation and the mitigations proposed in #440 and #1979 solve both (1) and (2).

I think that what should be discussed is just the following, not de-duplication:

when similar exploits would demonstrate different impacts, the highest, most irreversible would be the one used for scoring the finding. Duplicates of the finding will be graded based on the achieved impact relative to the Submission Chosen for Report.

I'd appreciate if you could further explain your reasoning and possibly review the de-duplication decision.

With all due respect that is wrong, all 3 issues are arguing that the mapping from DNA to attribute index is non-surjective. That there exists a vector of attribute indices that are not possible from the DNA generation process. @HickupHH3

Let me just add on the my previous point we have 2 functions

$f_1: DNA → rarityRank$ $f_2: rarityRank → attributes$

And we have a function $g$: $g = f_2(f_1(x))$

For context, here, we know that the function $f_2$ is always surjective and is therefore working fine, that for all attributes there exists a rarityRank that can be mapped to it. There is nothing wrong with $f_2$.

The issue is $f_1$ is non-surjective, that there exists a set of rarity ranks which are impossible, which all 3 reports have argued.

Here are where the reports differ:

Both https://github.com/code-423n4/2024-02-ai-arena-findings/issues/440 and https://github.com/code-423n4/2024-02-ai-arena-findings/issues/1979, prove that $f_1$ is non-surjective, and conclude that since $f_1$ is non-surjective then $g$ may also be non-surjective and as such there exists a vector of attribute indices cannot occur. (Note that may is used because it is still possible for $g$ to be surjective even if $f_1$ is non-surjective, however if $f_1$ and $f_2$ were both surjective then $g$ must be surjective - composition of two surjective functions must be surjective)

This report looks at the entire function $g$ itself and proves that the entire $g$ is non-surjective for certain set of values.

The end goal of all the reports is to show that $g$ might be non-surjective in certain cases which means some attribute indices cannot occur and therefore it should be grouped together.

Issues #1979 and #440 argue that the function mapping DNA to rarity rank f:X−>Y is non-injective: ∃y∈Ys.t.∃x1≠x2∈X,f(x1)=f(x2)=y.

this issue (#1456) is arguing that the function mapping rarity rank to physical attributes g:Y−>Z is non-surjective: ∃z∈Zs.t.∀y∈Y,g(y)≠z.

From this, it's clear that #1456 and #1979 + #440 should be bucketed into 2 different groups.

@HickupHH3 The DNA to rarity ranks mapping is by necessity non-injective. #1979 and #440 argue that the mapping is both non-surjective and non-uniform (not equidistributed), the latter of which is perhaps what you had in mind when thinking "non-injective". It is non-surjective because $3,003,000 < 100^6$, and non-uniform because $0$ and $1$, $16$ and $17$, etc., map to the same rarity rank combination. #1456 argues (implicitly) only that the mapping is non-surjective. It does so by considering the next mapping from rarity ranks to attributes, which may (or may not) impart this non-surjectivity of the DNA to rarity ranks mapping to the rarity ranks to attributes mapping.

Maths: We have two functions. A mapping from DNA to rarity rank combinations, $R: [0, 2^{256}-1] \to [0,99]^6$, and a mapping from rarity rank combinations to attribute combinations, $A: [0,99]^6 \to [0,9]^6$ (assuming 10 of each attribute).

$R$ clearly cannot be injective, but should be surjective and equidistributed, so that $R(X)$, where $X$ is a uniformly distributed random DNA, is uniformly distributed.

$A$ is also non-injective. It may be non-surjective if a probability is set to $0$, but is otherwise surjective. NOTE: $A$ is not the issue here, and it is correct (except for the issue reported by #112). If $R$ is surjective and equidistributed then, if $A$ is also surjective, $A \circ R$ is surjective. In order for the distribution of $(A \circ R)(X)$ to be as intended, $R$ must be surjective and equidistributed. This is what the issue is about.

#1979 and #440 argue that $R$ is non-surjective, the proof of which is that the range of $R$ is only $3,003,000$ which is less than the size of the domain, $100^6$. Furthermore, they argue that even within its range it is not equidistributed.

#1456 only argues that $A \circ R$ is non-surjective. From this it doesn't strictly follow that $R$ is non-surjective, but in the example it gave $A$ was surjective, in which case it does follow. #1456 fails to note that it is not equidistributed within its range.

Summary: The issue is that $R$ is non-surjective and non-uniform. #1979 and #440 argue for both of these, while #1456 implicitly argues only for non-surjectivity. #1456 is definitely not a separate issue. Rather it sets itself apart only by being a partial duplicate of #1979 and #440.

Unlike https://github.com/code-423n4/2024-02-ai-arena-findings/issues/366 and https://github.com/code-423n4/2024-02-ai-arena-findings/issues/736, while the user can influence uint256 dna generation, they need to fight the right ingredients that hashes together to obtain the desired value instead of direct selection. This is just the first step: there's also figuring out what's the best value that can map to the rarest rank combination.

In other words, there's significant brute force effort needed.

I would like to show you a vector attack that can be used in order to exploit my finding without brute force usage or external requirements.

We have two phases: before and after this issue is disclosed. Furthermore we define the following NFT values and prices:

A: this NFT is the rarest that can be obtained due to the issue i've reported. The market doesn't know that no rarer NFT can be obtained.

Before this issue is disclosed

A₁ is the price of A. Nobody knows that A is the rarest NFT that can be obtained

After this issue is disclosed

A₂ is the price of A. Now, everyone knows that A is the rarest NFT that can be obtained.

Once everyone knows that A is the rarest NFT in the world, its price will increase. This means that A₂ > A₁

Now, let's think an attacker knows this issue. He/she can buy many NFT fighter of type A during the first phase. He/she doesn't need to mint them, i.e., he/she doesn't need to brute force and this vector attack doesn't exploit #366 or #736 vulnerabilities.

After the attacker bought n NFT fighter of type A with price A₁, he/she disclose this issue. After that, he/she can sell his/her NFTs with price A₂.

In this way, the attacker maliciously obtained a gain of n*(A₂-A₁) without any brute force effort.

According to the high severity official C4 definition,

3 — High: Assets can be stolen/lost/compromised directly (or indirectly if there is a valid attack path that does not have hand-wavy hypotheticals).

The attack vector above shows how an attacker can compromise the value of assets directly and obtain a profit without any assumption.

https://github.com/code-423n4/2024-02-ai-arena-findings/issues/1979 and https://github.com/code-423n4/2024-02-ai-arena-findings/issues/440 argue that is non-surjective, the proof of which is that the range of is only which is less than the size of the domain, . Furthermore, they argue that even within its range it is not equidistributed.

The size of domain is 10⁶, not 100⁶. You are just show the algorithm doesn't cover all rarity rank combinations. You don't show anything about the surjectivity from dna to physical attributes. And that's the point! Your POC just describe there are duplicates among rarity rank. It is not enough to prove surjectivity.

The size of domain is 106, not 1006. You are just show the algorithm doesn't cover all rarity rank combinations. You don't show anything about the surjectivity from dna to physical attributes. And that's the point! Your POC just describe there are duplicates among rarity rank. It is not enough to prove surjectivity.

You speak of the domain of $A$. There is nothing wrong with $A$ (except #112) and the [relevant] surjectivity onto attributes depends on the surjectivity of $R$. The domain of $R$ is $100^6$. The reason you find a lack of surjectivity onto attributes in your example is only because of the issue with $R$, not with $A$. Your report considers the function $A \circ R$, which you can only do by using an example of $A$, since the probabilities are unspecified. But the issue is only in $R$ itself.

Thanks for the correction, forgot to account for domain + ranges, bleh. I've been schooled ><

The range of A is $10^6$ $R: [0, 2^{256} - 1] -> [0, 99]^6$ $A: [0, 99]^6 -> [1, 10]^6$

I agree that A isn't the issue; it's non-injective and surjective.

#1979 says that the range of $R$ is $3,003,000$ - $576,000$ = $2,427,000$, but this exceeds the range of $A$ = $10^6 = 1,000,000$. Mapping $2,427,000$ points to $1,000,000$ points doesn't guarantee non-surjectivity, although it's more probable. That is, after accounting for the non-uniformity and non-surjectivity of $A$, we still have a non-zero probability of feasibly generating all attribute combinations.

Hence, I think it is slightly more important to prove that the composite function is non-surjective, ie. that there exists some combinations which are unattainable. Showing that $R$ is non-uniform in its range is great though, and increases the probability of non-surjectivity of the composite function.

There are 2 separate issues highlighted:

1: Non-uniformity of $R$ This exacerbates the non-injectivity of $R$, causing the probabilities of attribute generation to be distorted, ie. even though the probability array is for instance [13, 7, 7, 13, 10, 13, 13, 10, 10, 4], the actual probabilities will be different.

2. Non-surjectivity of composite function $R \circ A$. Certain attributes are not attainable, by definition.

By making $R$ uniform uniformly distributed, will it also solve the non-surjectivity of the composite function? Not necessarily. Yes. By making $R$ surjective, does it solve the skewing of the probabilities? No.

#1979 covers the first point, and a little on the second. This issue covers the 2nd the best. #440 covers the first, mentions the second. Not sure what the best way to de-duplicate this is. Will ponder on this, am open to suggestions.

I want to try to show you a different proof. Until now, I used logic inferences. Now I'm using functions and domain cardinality.

Let's define two functions:

f: dna -> rarityrank

In the code, it is implemented in the following line:

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

g: rarityrank -> physical attributes

In the code, it is implemented in the following line:

uint256 attributeIndex = dnaToIndex(generation, rarityRank, attributes[i]);

I hope you agree that in order to obtain the physical attributes, I have to perform the following operation:

g(f): dna -> physical attributes
physical attributes = g(f(dna))

The cardinalities of domains of the three functions are:

|dna| = 2^255 -1
|rarityrank| = 100^6
|physical attributes| = 10^6

g(f) is the only function we should care about: it return a physical attributes vector from a dna.

Now, you proved that |rarityrank| is less than 100⁶ and that there are many duplicate values. In particular, your POC showed that |rarityrank| is 2,427,000 ( only 2,427,000 different combinations are possible, from #1979 ). We can assume |rarityrank| < 2,427,000 (but it wasn't what you said). Anyway, from this statement we can just deduce that:

f is not monotonic: we can have f(dna_1) = f(dna_2). We already know that, because it is trivial when |dna| >> |rarityrank|

Based on your POC, we cannot say anything about the surjectiviy of f() or g(). You are just talking about duplicates and cardinalities. In order to show that a function is not surjective using just cardinalities, you have to show that the domain is smaller than codomain. Otherwise, you have to analyze the behavior of functions to understand if they are surjective or not: that is what I did in my POC.

In my POC, I proved that g(f) is not surjective. I showed that using those functions, you have elements inside the g's codomain that cannot be obtained starting from the f's domain. In order to do so, I didn't analyze the cardinalities of domains, because it is not enough: you have enough values in f's domain with respect to f's codomain and you could find a f() that is surjective (and you did that in #440 using a monotonic function). You have enough values in g's domain with respect to g's codomain and you could find a g() that is surjective. The tiny cardinalities isn't a proof: you have to analyze the developed f() and g() functions to prove that g(f) is not surjective.

I want to underline that #1979 never talk about physical attributes that cannot be: the title refers to rarityrank, and the POC is about rarityrank. It never shows or mentions that there are physical attributes that cannot be obtained, and the lack of surjectivity isn't a trivial consequence of his/her proof.

#1979 covers the first point, and a little on the second. This issue covers the 2nd the best. #440 covers the first, mentions the second. Not sure what the best way to de-duplicate this is. Will ponder on this, am open to suggestions.

Non-uniformity of R is not important. The important fact is the Non-uniformity of R∘A. And it is a trivial consequence of the non-surjectivity of composite function R∘A. For this reason I didn't explicity talk about the erroneous probability computation: if there are values in codomain that can be obtained with the wrong probability 0%, others values can be obtained with an higher probability than the correct one.

1: Non-uniformity of R This exacerbates the non-injectivity of R, causing the probabilities of attribute generation to be distorted, ie. even though the probability array is for instance [13, 7, 7, 13, 10, 13, 13, 10, 10, 4], the actual probabilities will be different.

2. Non-surjectivity of composite function R∘A. Certain attributes are not attainable, by definition.

I add that 1. cannot be attacked. The probabilities are distorted, but the attacker still have to manipulate the dna input and work around the input validation to exploit it.

2. can be attacked, and an attacker could exploit it to make an unfair profit and to broke the market, like i showed in the previous comment.

For this reason I think #440 and #1979 are quite similar to #112 and belong to Medium Severity, and my finding belongs to High severity

By making $R$ uniform, will it also solve the non-surjectivity of the composite function? Not necessarily.

Not true. By definition, uniformity of $R$ means that given any rarity rank $r_1, r_2 \in R$ where $R$ is the set of all rarityRank we are concerned about, the probability of obtaining $r_1$ is equally likely to the probability of obtaining $r_2$ and that implies that every rarity rank in $R$ is possible, so uniformity implies surjectivity.

@niser93

g(f) is the only function we should care about: it return a physical attributes vector from a dna.

g is an inverse transform sampling of the attributeProbabilites. That means that g has to take a uniformly distributed random variable as input. dna is too large, so f is used to downscale, which must therefore be done uniformly. You (and we) have shown no issue with g itself.

f is not monotonic: we can have f(dna_1) = f(dna_2). We already know that, because it is trivial when |dna| >> |rarityrank|

When we said that f(0) = f(1) we had already shown that f(x) = f(x + 3003000*k), so we are in fact talking about the entire domain of f.

Based on your POC, we cannot say anything about the surjectiviy of f() or g(). You are just talking about duplicates and cardinalities. In order to show that a function is not surjective using just cardinalities, you have to show that the domain is smaller than codomain. Otherwise, you have to analyze the behavior of functions to understand if they are surjective or not: that is what I did in my POC.

We showed that f is non-surjective. g and g(f) can be either surjective or not, depending on the attributeProbabilites. However, if f and g are surjective then g(f) is surjective. Therefore, if g(f) is non-surjective, but g is surjective, then f is non-surjective. This is what you showed an example of.

In my POC, I proved that g(f) is not surjective.

You showed an example of this. It is not true in general.

I want to underline that #1979 never talk about physical attributes that cannot be

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

You seem to insist on the cardinality of the attribute combinations. This is not the set we care about. Rather, we need to consider the set of all potential attribute combinations, which is defined by the rarity ranks, i.e. the range of f. The probabilities may be such that g(r) = a_0 for only one r_0, which may be any rarity rank combination. If r_0 is not in the range of f we cannot obtain a_0. And there are many missing r in the range of f so for many different g there would be some a for which g(f(r)) = a has no solution r. This concerns only the non-existence of a dna such that g(f(dna)) = a. The other [half of this] issue is the non-uniformity.

@HickupHH3

#1979 says that the range of $R$ is $3,003,000 - 576,000 = 2,427,000$, but this exceeds the range of $A = 10^6 = 1,000,000$. Mapping $2,427,000$ points to $1,000,000$ points doesn't guarantee non-surjectivity, although it's more probable.

This reasoning is misleading. It is not the set of attributes that is relevant but the set of all possible attributes, which is defined by the rarity ranks. See also my comment above where I try to explain this in response to @niser93's comment.

Hence, I think it is slightly more important to prove that the composite function is non-surjective, ie. that there exists some combinations which are unattainable.

We cannot prove this because it is not true in general. But it follows trivially that it is true for some $A$ if $R$ is non-surjective. $R$ must be uniform over the entire domain of $A$. It is already always possible to select an $A$ such that $A \circ R$ is surjective. This is why I think the numbers $2,427,000$ and $24\%$ provided in #1979 in to quantify lack of uniformity is important; it shows that this is an issue not just for a tiny subset of all possible $A$. We only need to consider $R$; the potential non-surjectivity of $A \circ R$ is a trivial consequence of the non-surjectivity of $R$.

Showing that $R$ is non-uniform in its range is great though, and increases the probability of non-surjectivity of the composite function.

By making $R$ uniform, will it also solve the non-surjectivity of the composite function? Not necessarily. By making $R$ surjective, does it solve the skewing of the probabilities? No.

The issue can be stated as $R$ must be uniform over the domain of $A$. This solves both the non-surjectivity of $A \circ R$ and the skewing of the intended probabilities.

#1979 covers the first point, and a little on the second. This issue covers the 2nd the best. #440 covers the first, mentions the second. Not sure what the best way to de-duplicate this is. Will ponder on this, am open to suggestions.

#1456 gives a thorough example of the second point, which only proves that $R$ is not always surjective. It does not prove that $R$ is always non-surjective. And it proves nothing about the cases where the composition actually is surjective.

#1456 proves that $R$ may be non-surjective. #1979 and #440 prove that $R$ is always non-surjective, as well as non-uniform.

This means that #1456 has, by some measure, shown less than half of what #1979 and #440 have shown, but the thorough example in #1456 may be counted to round this up. I suggest a partial duplicate to #1456, a full duplicate to #440, and #1979 to be selected for report (for the extra quantification).

we still have a non-zero probability of feasibly generating all attribute combinations.

@HickupHH3 it's trivial that for plenty of possible setups the "probability of feasibly generating all attribute combinations" is close to zero. And not being zero shouldn't matter much in this discussion, since the probabilities arrays are likely to change as the game evolves in ways we cannot predict.

Take for example the potential setup in which each physical category has a rare 1% attribute. The chances of randomly getting all the rare attributes simultaneously is $\frac{1}{100^6}$, but we only have $2,427,000$ possible combinations in $100^6$. Correct me if my math is wrong, in this case the probability of the combination of rare attributes being absent is $100\times\frac{100^6-1}{100^6}^{2427000} = 99.999757$%.

Repeat the example with not so rare attributes of 5% probability and the result is 96.2788%.

My point however, these examples aside, is that it is very intuitive that by having only 0.0002427% of rarity rank combinations there will be a lot of potential setups in which physical attribute combinations will be missing. Mathematically proving this for a particular setup is nice but secondary.

I think it's a big overkill to discuss surjection and make a fancy math debate about it. It's staggering how few rarity rank combinations are possible, therefore it's highly likely that there's a problem with uniformity and missing attribute combinations. That's it. There's an obvious problem with the default divisors and how they are used, which has unintended consequences that impact the rarity model. Fix the root cause and both problems are gone.

Regarding the cardinality of physical attributes, it's not necessarily 10^6. As far as I know there are no requirements on the length of probability arrays. Although unlikely, the cardinality could be 2, in which case all attributes would be possible but there would still be a problem with uniformity. Again I insist, the root problem is how rarity rank combinations are missing and duplicated, which is best described in #1979 and #440. Partial credit for #1456 seems the most reasonable to me.

The issue can be stated as R must be uniform over the domain of A. This solves both the non-surjectivity of and the skewing of the intended probabilities.

Yeap, thought about it, agree with this as the primary root cause.

After considering all arguments, have come to the conclusion that #1979 will be selected as the best report, the other 2 will be satisfactory. The reason why #1456 isn't partially duplicated is because the impact of non-attainable rank combinations is the clearest, and the root cause is sufficiently identified (the other 2 are of course slightly better in this regard).

HickupHH3 marked the issue as not selected for report

HickupHH3 marked the issue as duplicate of #1979

The issue can be stated as R must be uniform over the domain of A. This solves both the non-surjectivity of and the skewing of the intended probabilities.

Sorry @HickupHH3 but i'm not agree. I said from the beginning that the solution proposed by #440 solves also my issue. If A is surjective and R is surjective, R∘A must be surjective. But I think a finding should be selected and awarded basing on the issue which is reported, not the solution.

The solution of #440 solves also my problem, this is true. But the issue proposed by #1979 and #440 doesn't imply my problem. It was the point from the beginning. Even if we have not-uniform R, R∘A can be surjective. We don't care about the solution, but about the issue. And #440 and #1979 issue doens't imply this one.

we talked about many things, and I think we lose the focus on the initial disputed problem. @d3e4 and @fnanni-0 said that their findings imply mine. I show that is not true. Than they show their solutions solve mine. And it is true (for #440 , not for #1979).

Not true. By definition, uniformity of $R$ means that given any rarity rank $r_1, r_2 \in R$ where $R$ is the set of all rarityRank we are concerned about, the probability of obtaining $r_1$ is equally likely to the probability of obtaining $r_2$ and that implies that every rarity rank in $R$ is possible, so uniformity implies surjectivity.

Just to avert any potential confusion that this comment might easily cause. To be precise and more explicit it is the uniformity of $R$ over the domain of $A$ that implies surjectivity. $R$ could still be uniform over its own range, which may be a subset of the domain of $A$. But it is precisely the domain of $A$ ("the set of all rarityRank we are concerned about") we consider when we here speak of surjectivity (otherwise surjectivity is a moot point, since every function is by definition surjective over its image, and it makes no sense to talk here about some other intermediate codomain larger than the image of $R$, but smaller than the domain of $A$), so @Haxatron is correct, even though his statement may be misunderstood.

@niser93 acknowledged, won't be changing my decision.

raymondfam marked the issue as insufficient quality report

raymondfam marked the issue as duplicate of #226

HickupHH3 marked the issue as satisfactory

raymondfam marked the issue as sufficient quality report

raymondfam marked the issue as duplicate of #53

HickupHH3 marked the issue as satisfactory

HickupHH3 changed the severity to 2 (Med Risk)

HickupHH3 marked the issue as duplicate of #376