Closed sherlock-admin2 closed 3 weeks ago
1 comment(s) were left on this issue during the judging contest.
Audittens commented:
While the described vector for the attack is correct, its estimated cost is incorrect, because it relies on the blog post that shows only the cost of computing 2^{80} hashes. In order to find the collision among them a big overhead is required due to memory limitations and impossibility to calculate these hashes in parallel. The correct price estimation is shown in the https://eips.ethereum.org/EIPS/eip-3607, which is 10 billion USD. Here https://hackmd.io/Vzhp5YJyTT-LhWm_s0JQpA is the detailed explanation by the EIP-3607 author, why the cost of this attack is much bigger compared to only computing of 2^{80} hashes.
Escalate
Like mentioned in the judging comment, the cost of the attack is in billions (bitcoin hashrate has increased 4x from the info in the link since 2017, so it's 2.5 billion usd now). Note, that this is an estimate from the bitcoin mining hashpower, however it's next to impossible to simply "rent" this hashpower for something else (attacker has to incentivize them to switch to their attack and needs specialized hardware for this which increases costs by high multiples etc). So the link shows a theoretical minimum, the real attack cost is likely at least 100x of that.
So based on this, this issue might become valid in the future, and with current attack cost and hash power increase, likely very far in the future, certainly not the next 20 years or so, maybe not even 50 years, besides there is a physical hardware speed limit, so we can't expect unlimited exponential growth.
As it's a distant future issue, it shouldn't be valid. We can say that finding 160 bit address collision to steal all blockchain funds and render eth useless is also possible in the future, it doesn't make it a valid issue.
That said, this is the only issue describing how to steal all mkr funds from LSE using the collision, all dups have much smaller impact, making them possible even farther in the future. Still, this and all dups should be invalid as they're not exploitable in practice in the near future.
Escalate
Like mentioned in the judging comment, the cost of the attack is in billions (bitcoin hashrate has increased 4x from the info in the link since 2017, so it's 2.5 billion usd now). Note, that this is an estimate from the bitcoin mining hashpower, however it's next to impossible to simply "rent" this hashpower for something else (attacker has to incentivize them to switch to their attack and needs specialized hardware for this which increases costs by high multiples etc). So the link shows a theoretical minimum, the real attack cost is likely at least 100x of that.
So based on this, this issue might become valid in the future, and with current attack cost and hash power increase, likely very far in the future, certainly not the next 20 years or so, maybe not even 50 years, besides there is a physical hardware speed limit, so we can't expect unlimited exponential growth.
As it's a distant future issue, it shouldn't be valid. We can say that finding 160 bit address collision to steal all blockchain funds and render eth useless is also possible in the future, it doesn't make it a valid issue.
That said, this is the only issue describing how to steal all mkr funds from LSE using the collision, all dups have much smaller impact, making them possible even farther in the future. Still, this and all dups should be invalid as they're not exploitable in practice in the near future.
You've created a valid escalation!
To remove the escalation from consideration: Delete your comment.
You may delete or edit your escalation comment anytime before the 48-hour escalation window closes. After that, the escalation becomes final.
Adding to the above objections, the data from available market rates for keccak hashing:
In terms of both cost and time it's many orders of magnitude out of the realm of possibility.
Which is probably why none of the existing contracts using create2 were ever exploited in this way.
An
eoa11
can be replaced with a contract created byeoa3
. The address of the contract can be brute-forced in the same way aseoa11
. The contract performs step 2 instead ofeoa11
and self-destructs in the same transaction.
The paper describes a more expensive EOA-to-contract collision.
Please refer to this comment:
A large (2^11) multiplier in the above example is due to the increased difficulty of computing the elliptic point operations, which isn't needed in this attack – the attacker can simply deploy a wallet controlled by them using CREATE2. This will make the computational complexity around 2^81 and would require giga-terabytes of memory, which means this attack is possible to execute with ~34 minutes of the current Bitcoin's hashrate, assuming keccak256 is as easy to calculate as SHA-2. The current cost of this attack would be less than $1.5m with current prices.
Also, refer to this comment:
since we're looking for a contract-contract collision and not an EOA-contract collision, no EC multiplication is needed, making f 1 and f 2 purely keccak256 just with different inputs, and the cost of the attack is about 2^81 calls to f (which is, again, just keccak256).
Since both functions are of the same weight now, we can set m = 1 / θ = 2 ^ 40 and achieve the same execution time, but with ∼ 16 times lower processor count and memory cost than outlined. Of course, the real attack time would take longer depending on how many parallel processes you have, but taking 0.02% of this power for 5000x the duration (while also lowering the memory cost by 5000x) and it's still not unrealistically long. The total number of hashing calls across all processors is the same, so the attack cost is the same as outlined.
Under the assumption that a standard computer can perform 2^30 operations per second which is reasonable, @Czar102 's calculation is on point.
It proofs that the attack cost is in the millions, not billions. It may be helpful to revisit the discussion in the issue I'm referring to for additional context.
Regarding the timeline, the Sherlock rulebook does not specify a fixed timeframe within which an issue must occur for it to be considered valid.
The continuous development of available resources and the value at stake make this issue worth mitigating. This is the kind of issue that would have a critical impact if it were to occur. Note: The same point was previously shared by the head of judging, see here
We should also consider that Maker plans to significantly increase its Total Value Locked (TVL), as seen in the following references:
1
The Endgame plan marks a transformative phase for MakerDAO, with the intent on scaling the DAI supply to 100 billion and beyond.
Maker’s ‘Endgame’ readies launch, aims for 100B DAI to take on Tether
Even now, the DAI supply plus MKR value is nearing $10 billion: DAI ~5.5 and MKR ~1.8. All of this would be at risk if the attack were to occur.
The cost was estimated to be $10 billion over 3 years ago (and for EOA-contract collisions, which are much more expensive — see my point 1 above). The cost of computation decreases every year. Over the past 3 years, Bitcoin's hashrate has increased sixfold, doubling approximately every 14 months — see the graph here. This significantly impacts the cost of such an attack and highlights how rapidly computational feasibility is improving.
Quoting the sponsor's response regarding hash collision attacks:
While we consider hash collision attacks extremely unlikely for the foreseeable future, we intend to change the
VoteDelegateFactory
so as to make it future-proof. Considering the enormous resources required for this attack, and given that a collision with aVoteDelegate
could be use to grief (but not steal) funds deposited to aVoteDelegate
, or to avoid a liquidation (which is very unlikely to be worth the cost of the attack), we consider this an informational / low severity issue. This is consistent with our General Disclaimer that "Issues where there is damage to the protocol/users but the net attack cost exceeds the damage caused significantly (50%+ more) are considered low severity."
Firstly, as the sponsor and other escalators here have mentioned, the cost of executing the attacks is tremendous and does not meet the contest’s criteria/rules regarding net attack cost for this specific contest.
Secondly, the following are the contest rules extracted from the contest's README. As mentioned below, whether an issue qualifies as a Medium also depends on the constraints.
Any loss smaller than 0.5% can never be Medium. Any loss between 0.5% and 5% loss can be Medium at most. Any issue larger than 5% can be Medium or High (depending on constraints)
In one of my clarifications with the sponsor during the audit period, it was mentioned that meeting certain requirements for a Medium rating does not automatically confer a Medium risk rating. The existing constraints should be evaluated and taken into consideration (which is aligned with the contest rule above). Based on the existing constraints, hash collision-related issues do not qualify as a Medium or High issue under any circumstance in this contest. If this issue were genuinely a major concern that could be executed without much constraint, it would have already posed a significant threat to many protocols, as many use CREATE2 in various parts of their codebase. Therefore, the risk of a potential hash collision is being significantly overestimated here.
Thirdly, during judging, no one should attempt to predict the future development of the semiconductor industry or forecast the feasibility of hashing collision attacks in the coming years. If an issue is based on speculation and forecasts rather than the actual situation at this point in time, it remains a theoretical issue without a concrete proof of concept (POC) that can be executed. Issues should be judged based on existing technological capabilities, not on potential future advancements. Otherwise, in an extreme case, one could also argue with the advancement of quantum computing in the future, all private keys and encryption on the Blockchain are theoretically breakable and could steal all funds in the Blockchain and should deserve a High/Medium classification in the contest.
Lastly, past Sherlock judgments on similar issues do not automatically confer a similar risk rating to this issue. The judge is not entitled to do so. This has been reiterated numerous times by Sherlock’s judge. Specifically, this contest operates under more restrictive rules, where whether an issue qualifies as Medium depends on various constraints and the net attack cost.
Given these points, this issue does not qualify as a Medium, and should be Low/Informational at most.
I'd like you to refer to the new comment from the EIP author himself here
Having looked back at the text, it seems to me now that I had overestimated the EC operation cost. This makes the EC cost much smaller, thus being closer to the cost of Keccak. We would then end up with the total cost around 2^83 , as you write it for the contract-contract attack.
Which proves that the attack cost is lower than were expected in the paper
Regarding bb22ff:
Regarding xiaoming9090:
Replying to the 00xSEV comment: "I would like to highlight that in this issue, I mentioned the potential for contract-to-contract collisions."
Sorry, I didn't notice this statement during the judging contest. My comment referenced the "Summary" part of your report, stating that the cost of finding a collision between a new urn address and an EOA is about several million dollars, which is exactly the attack described in the paper.
The cost of finding a collision between a pair of contracts is indeed several orders of magnitude smaller due to the simple nature of $f_1$ and $f_2$ functions and I agree that for this issue it's possible to replace EOA with the contract while not changing anything else in the attack.
@00xSEV
Unfortunately, you didn't provide any calculations to support your estimate. A valid escalation generally carries the burden of proof.
The calculations also don't appear to have considered my first point, which reduces the attack cost by 10,000 times ($10bn vs $1.5m cost).
I did. I calculated just the bare minimum theoretical 2^81 keccak hashes.
Calculations:
- It seems you may not have taken into account the discussion in the paper about how an attacker could invest in ASICs to reduce the cost of the attack. The current public NiceHash market may be smaller than required, but it ignores investment in ASICs, which were estimated in the paper. It also ignores GPUs and markets outside of NiceHash.
First, it's hypothetical tech, not a valid precondition for a contest finding, as already mentioned.
Second, it's highly unlikely given the market data:
The 264M per year nearly free money for orders of magnitude higher efficiency is sufficient to refute the "easy ASIC" hypothetical, even if it were an admissible precondition.
I don't particularly have a horse in this race, but reading this discussion sent me off on a research quest. Here's some interesting information:
If an EOA performs step 2 of the attack:
2. Call
vat.hope(attacker)
andlsmkr.approve(attacker, max)
Then step 3.ii:
3.ii
LSUrn1
address ==eoa11
address.
Will fail because contracts cannot be deployed to addresses with nonzero nonce. The only way for this attack to succeed is by computing a contract-contract address collision and then having the first contract SELFDESTRUCT
(obeying EIP-6780, of course).
So the point about performing an EOA-contract collision and its attendant costs is moot.
EDIT: of course, if the attack could be performed in a different order, with the EOA's transaction's coming after the deployment of the urn, then it would still work due to the non-adoption of EIP-3607
Ref:
https://github.com/ethereum/execution-specs/blob/master/src/ethereum/cancun/vm/instructions/system.py#L104 https://ethereum.github.io/yellowpaper/paper.pdf (equation 118, first branch)
Ok but what is the algorithm that can find the collision between two separate random functions in a space time efficient way?
Pollard's rho algorithm. It has a trivial memory cost associated with it when applied here.
So yeah, geth create2 calls create which fails for non-zero nonce. So:
- contract->contract will fail because of non-zero code
~It's still possible for this to succeed if the first contract SELFDESTRUCT
s in the same transaction as its construction~ I see your edit
- contract->EOA fails because of codehash check (3607)
funky. Sounds like this would cause a chain fork and slashing issues unless all clients have quietly adopted 3607?
- contract->contract will fail because of non-zero code
~It's still possible for this to succeed if the first contract
SELFDESTRUCT
s in the same transaction as its construction~ I see your edit
- contract->EOA fails because of codehash check (3607)
funky. Sounds like this would cause a chain fork and slashing issues unless all clients have quietly adopted 3607?
all clients should have adopted 3607, otherwise they're non compliant with the yellow paper (4). This was merged back in 2021.
as mentioned by others above, this would only succeed if a contract was deployed -> approval granted -> contract self destructs all in the same tx.
So then you're looking for a contract to contract collision.
Historical decisions are not considered sources of truth.
Past decisions on similar issues have no weight here.
Let's refer back to some impartial sources to provide a more balanced perspective, as contest participants may have their own biases:
based on discussions with security leads in the space, the general perception is that anything below $1B should be considered a threat, just to have room for cryptographic or CPU advancements. There was also a comment around the fact that even the “thought” of this being possible with a medium-scale adversary might disincentivize some stablecoin, bridges, or asset providers from launching in the first place.
We can see that even "the thought of this being possible" is considered serious enough to deter leading cryptography minds from launching a susceptible project in the first place.
Assuming that SHA-2 has about 2^11 smaller latency that the f1 processor, we obtain that the total cost of the attack should be equivalent to 2^92 SHA-2 hashes. Note that the Bitcoin mining network computes 2^67 double SHA-2 hashes per second, so that the attack cost is equivalent to 2^25 seconds, or 1 year, of Bitcoin mining. This is $10 billion in June 2021.
Plus the author's (cryptographer from Ethereum foundation) current views:
Having looked back at the text, it seems to me now that I had overestimated the EC operation cost.
This makes the EC cost much smaller, thus being closer to the cost of Keccak.
gsWe would then end up with the total cost around 2^83, as you write it for the contract-contract attack.
Compare 2^92 vs 2^83, 2^9=512 decrease in the cost. The overestimated cost of the attack was $10 billion in June; the new estimate is 10^9/512 = $1.953 million. This can be considered a source of truth and sufficient proof, being an expert estimation.
The estimate from the judge in the previous issue
The current cost of this attack would be less than $1.5m with the current prices.
Under the assumption that a standard computer can perform 2^30 operations per second which is reasonable, @Czar102 's calculation is on point.
As we can see, all impartial parties agree that the cost of the attack is in single-digit millions and should be considered a significant threat.
Other contestants, except for bb22ff, didn't provide any calculations for their estimates, so it's essentially an unsubstantiated opinion from an interested party, contrasted with the impartial estimate of an expert.
bb22ff's estimate only takes into account a small part of the market: Keccak mining on NiceHash. This is a very niche field and highly unstable (involving few low market cap coins with low usage). It also only considers the current price, which may just be a short-term spike. This presents a high-risk, high-reward situation that may not accurately reflect the overall cost or feasibility of the attack.
After carefully reading the issue once again, I would like to add the following note. As discussed above, only a "contract-contract" collision can be found effectively and used for the attack (if not consider new optimization of the EIP-3607 author, which was not known before the end of the contest and therefore could not be used for the cost estimation). However, in fact "Other Variations" section doesn't provide a correct way to find a "contract-contract" collision due to the two following problems:
"An eoa11 can be replaced with a contract created by eoa3. The address of the contract can be brute-forced in the same way as eoa11"
. If eoa3 is fixed, then the address of the created contract cannot be brute-forced because eoa3 doesn't control a salt value for contract creation (consecutive nonce values are used instead). If eoa3 is not fixed, then brute force is applied for the private key of eoa3, which again has the same cost as in EIP-3607.index
which is consecutively increasing and therefore cannot be used to find the collision. If eoa12 is not fixed, then brute force is applied for the private key of eoa12, which again has the same cost as in EIP-3607.While in theory the attack can be modified into the "contract-contract collision" setup (e.g. by introducing intermediate contracts that will create analogs of eoa11 and eoa12 using the create2
opcode, i.e. "eoa3 -> contract11 -> analog of eoa11"), every variation described in the original issue in fact uses the "EOA collision" setup, that requires computationally-hard functions $f_1$ and $f_2$ (both require ecmul
operation for public key calculation and several keccak
-s applied later) and therefore has a much bigger cost.
After some thinking, this does satisfies the Medium severity criteria given the additional rules of the contest.
The impact of this as documented by the report is the total and complete destruction of the MakerDAO protocol. Technically, this means the loss is unbounded. Currently, with the market cap of DAI at $5.3B and MKR at $1.8B, the total loss would be $7.1B. Adding 50% more would be $10.65B.
Even if we consider the upper-bound of $10B presented here by the EIP-3607 author, this does fit the attack cost criteria as per the additional rules:
Issues where there is damage to the protocol/users but the net attack cost exceeds the damage caused significantly (50%+ more) are considered low severity.
If we use $2.5B to account for the quadrupling of the Bitcoin hash rate or include the fact that the market cap of MakerDAO will very much likely to increase in the future, then this attack is profitable.
Just by these facts alone, this report seems to satisfy the Medium severity criteria.
Thank you, Audittens, for taking the time to delve deep into the issue. I'd like to add some additional information:
If new facts emerge that demonstrate the validity of the issue, they should be considered even if they were discovered during PJQA.
I used EOAs to simplify the explanation of this complex attack. It's straightforward to replace EOAs with a contract created by another contract using create2.
In my report, I linked to this comment for the cost estimation. In that comment, we can see "the attacker can simply deploy a wallet controlled by them using CREATE2". So that possibility was also mentioned in my report.
Thanks to all the escalators who want to ensure that Maker remains safe and secure. I want to add some context to this finding.
If using EOAs as an example in this finding is the concern, #42 has described a contract-to-contract collision, which is a duplicate of this one.
The potential for compromising a protocol like Maker, causing bad debt, preventing collateral liquidation, and undermining the protocol's stability could have catastrophic consequences. It's important to address this now rather than wait until the attack becomes more feasible. The moment someone finds a collision, the whole protocol will be at high risk. That’s why the sponsor has confirmed and will fix it.
The comment that describes this issue as a “distant future problem” fails to address the importance of proactive security measures. Waiting until an attack becomes imminent is a poor strategy. It’s essential to recognize and address potential vulnerabilities early, rather than assuming they will remain unexploitable indefinitely.
This is indeed a valid medium finding.
Best regards
Firstly, I've hidden one comment because it was subjective and didn't bring any value.
Secondly, repeating again, historical decisions are not sources of truth, there's no point in quoting or sharing other issues to prove the validity of this issue. Also, note that the part where "the sponsor agrees with the HoJ" is not the sponsor's comment. It's a comment from one of the Watsons. Additionally, why not also share this comment where the additional cost is a quarter of a billion.
Thirdly, I'm not sure I understand the cost correctly:
Compare 2^92 vs 2^83, 2^9=512 decrease in the cost. The overestimated cost of the attack was $10 billion in June; the new estimate is 10^9/512 = $1.953 million. This can be considered a source of truth and sufficient proof, being an expert estimation
But isn't 1.953 only a decrease and the total cost is 2^83 = 9671406556917033397649408 and 10^83/9671406556917033397649408 = 1.0339757656912846e+58? I assume it's incorrect, so please correct me here.
Regarding @bb22ff calculations. I see @00xSEV says it's incorrect because it's based on NiceHash data, but can you please provide a more trusted source of data along with the calculations? For prices, I see you don't like them using current prices, please use any price from the time of the contest (not a spike, but from a period when the price was stable).
Note: I see there are many concerns, I'll answer them once I'm sure I understand the issue and its cost.
Not to comment on cost yet feasibility of 2**81, the Bitcoin network does that every hour (per my own estimations of this for my own disclosures, I did not submit any instance of this and I'm not a judge). Electricity costs are quickly calculable as less than a few mil from there.
Hardware costs is its own very wide question. I'd cite how Bitcoin developers estimated this attack to inevitably cost less than 10m USD within just a couple years IIRC. Obviously, one can create debates on SHA2 vs keccak256 and the ability to repurpose mining ASICs for cycle funding.
I'd personally argue this a valid loss of funds issue especially given protocol damage and projected timeline accordingly. Apologies if this doesn't contribute and feel free to hide this if it's too much of a hinderace.
@WangSecurity Thank you for reviewing my issue and for your comments/questions
I may need a couple of days to prepare the answer. I hope that's okay?
In addition to NiceHash data, there's vast.ai data from someone now crunching create2 addresses for leading zeros. They get 1.4 TH/s for 700 RTX 4090s. According to vast.ai's homepage this costs 700 0.35 = $245 per hour. That is 5880 per day for 120 PH (1.4 TH 86400 / 1000).
Using this data instead of NiceHash data, for 2^83 (assuming infinite supply), we get 473 Billion USD ( 5880 × 2^83/(120×10^15) / (10^9) ).
I'd like to add attack impact and threshold to consider for qualifying this as medium or not. The README states:
In the lockstake case, the maximal locked MKR is assumed at $250m and the maximal line is assumed as 100m dai.
and
Issues where there is damage to the protocol/users but the net attack cost exceeds the damage caused significantly (50%+ more) are considered low severity.
Attack impact (the one described in this issue): allows to steal all MKR locked in lockstake with VoteDelegate selected. In particular:
In order for this issue to qualify as a Medium, the attack cost should not exceed $225 * 1.5 = ~$340M.
Essentially, if it's proved that attack cost is below $340M, this issue is medium. Otherwise it's low/informational. The remarks about protocol having billions or that endgame plan includes growth to 100 billion and beyound is irrelevant, the contest README specifically assumes $250M amount at risk.
As pointed by several Watsons, the attack cost using present technology is at least in billions, thus doesn't qualify for a medium. All estimations with low millions are based on hardware or power not yet available. Using current bitcoin hashrate as an estimate of the attack cost is incorrect since it can not be used in such way, and setting up the hardware/incentives/gathering miners etc just to perform one-off task of finding a hash collision will have very high setup costs other than mining/hashing power itself. So either high cost (in billions or even trillions) of renting computing power using present available solutions (like NiceHash) or using custom hardware and custom solution (not yet available) with high setup cost and lower per hash cost (possibly billions to setup and possibly millions to find collision, but we can't be sure in any numbers here because such tech is not available yet and all costs are pure speculations depending on a lot of factors, thus I don't think we should speculate on the cost of setting up this non-existing tech).
One thing to note here: while it's true that such threat can be real in the future and that protocols might not start up purely on the thoughts of such attack being possible even if in billions, however in the context of this particular contest this is irrelevant.
Thanks for waiting for my reply.
Here are my calculations:
The cost can be estimated as follows. Assuming that SHA-2 has about $2^{11}$ smaller latency that the $f_1$ processor, we obtain that the total cost of the attack should be equivalent to $2^{92}$ SHA-2 hashes. Note that the Bitcoin mining network computes $2^{67}$ double SHA-2 hashes per second, so that the attack cost is equivalent to $2^{25}$ seconds, or 1 year, of Bitcoin mining. This is \$10 billion in June 2021.
Refer to the updated estimate that puts it at $2^{83}$ SHA-2 equivalents, as stated by the author here after HoJ confirmed them in that issue. To understand how we reached this optimization, it's best to read the thread. However, TLDR is that we use a cheaper version of address calculation, which is 2^9 times cheaper.
Feel free to ask for further details and steps to understand the number. I can delve deeper into it if it's required.
Note how we got the 1-year estimate: $2^{92} / 2^{67} = 2^{25}$ seconds = ~1 year.
If we substitute $2^{83}$ into the quote above: we obtain that the total cost of the attack should be equivalent to $2^{83}$ SHA-2 hashes. Note that the Bitcoin mining network computes $2^{67}$ double SHA-2 hashes per second, so that the attack cost is equivalent to $2^{16}$ seconds, or ~18 hours, of Bitcoin mining. This is \$10 billion/2^9=\$19.5mln in June 2021.
Also note that Bitcoin hashrate increased to $2^{69}$ in the last 3 years source 1, source 2. Furthermore, the price per hash dropped 2–20 times, depending on the starting point chosen source.
We can observe the rapid development of the ASIC industry in this graph. From August 2021, power consumption for large ASICs fell from \$57 to \$2.56 per TH, illustrating how quickly ASICs evolve and become cheaper when demand exists.
Let's calculate the investment needed in miners to achieve a 50% chance of finding a collision using retail-available technologies (ignoring memory for now):
9.6*10^9*1*0.02
= \$192 million.Estimated number of Bitcoin ASICs in the world:
Estimated number of GPUs in the world:
Memory optimization is necessary because storing $2^{80}$ hashes is not currently feasible. The method described in the paper utilizes shared memory. Runtime depends on the number of Keccak processors. We can have 1,000,000 Blackminer F1+, x 34.9 GH/s = 3.49 x 10^16 = ~2^55 H/s.
Let’s reduce $\theta$ (memory cost increases). See:
The expected number of distinguished points to be produced is $\theta 2^{81}$.
We may assume that every point stores about 60 bits about $x_0$ and $160 + \log_2 \theta$ bits about itself.
Setting $\theta$ to 2^-26 requires 60 + 160 - 26 = 194 bits of memory per point. We need $\theta 2^{81}$ points = $2^{55}$ points. $2^{55} 194$ bits = 776 PB. RAM prices are around \$1600/TB. So, 776k \$1600 = \$1.271 billion for memory.
RAM consume ~5W per module.
Using the formula from the paper: $\frac{2^{81}}{m}+\frac{2.5}{\theta}$
( 2^81/2^55 + (2.5/2^-26) ) / 60 /60/24/365 = ~7.4 years
.Cost: See my calculations here. You can make a copy of the spreadsheet to change different variables. E.g. increase memory to decrease the time required.
RAM electricity cost | $165,904,088 | |
ASICs electricity cost | $1,347,099,767 | |
RAM cost | $1,271,398,400 | |
ASICs cost | $1,548,515,631 | |
Total cost | $4,332,917,886 |
Using bloom filter, as mentioned in this comment, confirmed here will reduce the amount of RAM required to 1 bit per point. Than we can set $\theta$ to -20 and reduce the cost to $2.4 billion an 2.2 years (calculations are in the same spreadsheet).
Further cost reduction possibilities:
Additional arguments:
The attacker could reduce the cost of the attack to millions of dollars by developing their own ASICs, as previously estimated by HoJ and confirmed by the EIP author.
The use of current ASICs/GPUs, not optimized for keccak, serves as proof that this is feasible while still being cheaper than the potential profit from the attack.
Additionally, why not also share this comment where the additional cost is a quarter of a billion.
I didn’t cite it because, in the same comment, @Czar102 estimated the ASIC cost to be in the millions: "you would need to create your own ASIC just for this (millions)." I used the lowest possible attack cost, and ASICs seem to be the most relevant option here. That’s why I focused on buying/developing rather than renting.
The investment in hardware is also cited in EIP-3607: "in hardware and electricity."
We estimate that a collision between a contract and an EOA could be found in about one year with an investment of ca. US$10 billion in hardware and electricity.
Apologies if I made any mistakes in previous responses, such as "the sponsor agrees with the HoJ." The message sounded like it was from the sponsor, and I didn't recheck the thread to verify.
If the data or optimizations provided are insufficient, I can dive deeper into researching bulk prices, other ASIC options, other GPUs, and the latest optimization papers.
This is an unusual field of attack, and I believe we should review all available data carefully.
Regarding panprog's comment:
Please refer to the docs, which state that it’s required to lock MKR in order to vote via delegation.
"The locked-up MKR is required to participate in Maker Governance via delegation."
Yes, it does. Please review my issue, specifically point 17 and the PoC testAttack7SeveralLsUrnCollisionsStealFromLSE
.
We can’t ignore the fact that almost all votes are cast through vote delegates, while other votes are negligible. Both of these points are explained in point 18 of my issue.
__
the contest README specifically assumes $250M amount at risk
The stolen MKR is locked in both VoteDelegates and Lockstake. VoteDelegate is a separate module and repository, which can be found here: https://github.com/makerdao/sherlock-contest/blob/master/README.md#vote-delegate. We’re stealing from both VoteDelegates and Lockstake, and taking full control of the protocol, so the limit you mentioned isn’t relevant.
- Please refer to the docs, which state that it’s required to lock MKR in order to vote via delegation.
We audit the codebase we have now, and nothing in this codebase indicates a requirement to lock MKR in lockstake engine in order to vote: anyone can lock MKR into the VoteDelegate (or Chief) directly to vote without locking MKR in the Lockstake engine. Notice the text at the top of the linked doc:
This documentation describes planned functionality and processes that MakerDAO has not yet implemented. Be aware that parts may be inaccurate or out of date.
Also note the future issues Sherlock rule:
Future issues: Issues that result out of a future integration/implementation that was not mentioned in the docs/README or because of a future change in the code (as a fix to another issue) are not valid issues.
So based on this, either the doc is outdated or it means something different, or it is not implemented yet (in which case this if the future issue), from the contest codebase it's clear that anyone can vote directly via VoteDelegate/Chief without locking in lockstake engine.
Now, the contest clearly limits the lockstake engine to $250M worth of MKR locked. This means that only a certain percentage (11% as of now) of all MKR is assumed locked in lockstake engine and can be stolen, attacker can not be sure that his vote will pass as all MKR outside of lockstake can be used to vote against attacker.
I realized I made a mistake with the collision probability formula. It should be:
$P \approx 1 - \exp\left( \frac{-k^2}{2N} \right)$
(as approximated by Wikipedia), or the more accurate formula:
$P \approx 1 - \exp\left( \frac{-k(k-1)}{2N} \right)$
(as explained in this comment).
Using these formulas, we can see that with $2^{81}$ hashes, the probability of a collision is 86.47%, with $2^{82}$ hashes it's 99.97%, and with $2^{83}$ hashes it's 99.999999999999%. You can check the calculations here.
Regarding panprog's comment: 1. I believe the docs should at least give us an expected usage pattern. Otherwise, it’s impossible to understand what is meant by "locked on lockstake." Is it 1%? 11%? 100%? From reading the docs, "required" seems to suggest it’s close to 100% of all active voters.
For the sake of argument, let’s check your calculations: 250*10^6/(1892*10^6)
= 13.21%
Looking at 08/08 , we can see the market cap was $1.67B, and going back to last year, it was <$1B. (data from here)
250/1670 = 14.97%
250/1000 = 25%
Now, let’s check the last 100 executive votes, going back to 2021-10-31 13:30. First, we get the data from Dune here. Export it here. Convert it to Solidity and run forge test --match-path test/votes.sol -vvv
(this may take a minute). This way, we will get the number of votes for the hat
(proposal) that was lift
(selected to be executed):
The largest approvals (votes) are: 1.13809292130849020332844e23 = 113,809 MKR. Divide by the total supply and you get 113,809 / 930,366 = ~12.2%, or $231 million at current prices.
So, the biggest vote in history was smaller than the amount the attacker will acquire.
2. Let’s also take a look at the contest page: https://audits.sherlock.xyz/contests/333
Please discuss any design choices you made. Please refer to https://github.com/makerdao/sherlock-contest/blob/9a01337e8f82acdf699a5c1c54233636c640ca89/README.md, and the documentation present in the codebases.
Let’s check https://github.com/sherlock-audit/2024-06-makerdao-endgame/blob/main/endgame-toolkit/README.md, which directly references our context: https://endgame.makerdao.com.
A set of components for the SubDAO stack in the context of the MakerDAO Endgame.
To summarize, the contest page references "the documentation present in the codebases," which directly points to https://endgame.makerdao.com. We can't just ignore that.
Hi @00xSEV! As many I don't have a horse in the game, only is following out of curiosity and the importance of the subject...
I really enjoy your write-ups, massive kudos for the dedication! :raised_hands: My feeling is though that the explored options for the attack algorithm, specifically inspired by this paper got mixed with each other during discussions, leading to some confusion. For a bit more elaborate exposition of the same ideas as in the above paper, the paper Parallel Hash Collision Search by Rho Method with Distinguished Points can be used: it contains many more details and graphics, which makes following it easier.
First, what's important to emphasize, is that all of the below operate under the assumption of 50% probability of success (we'll return to that later). I believe these are the attack options (please correct me if I am wrong):
I believe in all your computations you follow the last, parallelized approach: this is natural, because only then can we employ the power of mining networks. But in this writeup, point 3, you employ for some reason $2^{80}$; I believe $2^{81}$ should be used instead (this is what executed on parallel processors), plus the part $\frac{2.5}{\theta}$ of total compute time should be also somehow accounted for.
Wrt. to your comment:
I realized I made a mistake with the collision probability formula. It should be: $P ≈ 1 − exp \big( \frac{−k^2}{ 2 N} \big)$ (as approximated by Wikipedia), or the more accurate formula: $P ≈ 1 − exp \big( \frac{−k(k-1)}{ 2 N} \big)$ (as explained in this comment).
Using these formulas, we can see that with $2^{81}$ hashes, the probability of a collision is 86.47%, with $2^{82}$ hashes it's 99.97%, and with $2^{83}$ hashes it's 99.999999999999%. You can check the calculations here.
I believe that all of the above estimates, as well as the ones used in your previous calculations employ the 50% probability of success as a baseline. The value of $2^{83}$ from this comment is related to the optimized cost of computing EC operations, and is totally irrelevant here if we consider contract-contract collisions... So in order to get to these higher probabilities, you'll have to additionally multiply the numbers by respective coefficients. Given the compute time requirements for 50% success probability being $X$, we'll have
Finally, I would like to express my general doubt wrt. birthday paradox based attacks, which is related to the above probabilities. For some reason, many are taking 50% success rate as good enough. It is true that you may hit the collision even earlier. But what happens if you don't? Let's put ourselves in the hypothetical attacker's shoes, who invested millions/billions upfront. They spend the $X$ compute time above, and don't get a collision. What do they do?
I hope you get me. For an attacker to invest such substantial resources beforehand, they have to be sure of success; but all that birthday paradox offers them is only probabilities of success.
@00xSEV A bottleneck that wasn't explored is the DB and network.
As far as I understand, the DB running on some gigantic cluster for 8 years, using the output of 1M ASICs needs to handle an impossible workload:
However, the numbers for the managed NoSQL DB services, like DynamoDB, have throughput numbers in millions of requests per second, not in quadrillions. That's 10 orders of magnitude less than needed, so is unlikely to be even possible within our lifetimes?
Thanks to all the Watsons for these extensive comments.
I agree that we have to consider Lockstake to have $250 million locked as correctly explained in this comment. Although, $100 billion supply of DAI is expected or anything else, it's only an expectation and speculation. Based on the contest README, we have to believe $250 million will be locked in Lockstake. Also, as correctly stated in the very same comment, currently the code doesn't require staking in Lockstake to vote and it's only a plan for the future. Hence, we should assume $250 million as a maximum loss.
I agree that calculating the cost for the 50% calculation is not sufficient to say that's the reliable cost of the attack. As correctly pointed out in this comment. It relies on probability and "getting lucky" while the cost to execute the attack "for sure" is significantly higher.
The best and the lowest cost we can get for at least a 50% success rate (which is not sufficient as stated above) is $2+ billion which doesn't qualify for the following rule:
Issues where there is damage to the protocol/users but the net attack cost exceeds the damage caused significantly (50%+ more) are considered low severity.
Additionally, I see that the "Risk matrixes" were mentioned, please don't use them as they don't play any role in judging Sherlock. The decisions are based on the README and judging rules.
Hence, I believe based on the calculated cost of the attack, this is indeed low severity since the attack cost indeed exceeds billions. Planning to accept the escalation and invalidate the issue.
@WangSecurity, thanks for the review. I would like to add some additional points to consider:
$250 million as the maximum potential loss
- I believe we should also consider the loss of all DAI and other Maker assets in the system. If the attacker can elect a new
hat
, they could potentially shut down the protocol or mint an unlimited amount of DAI (as mentioned in the Impact section). They would also be able to modify theline
.
@kuprumxyz, thank you for your review. While I don’t necessarily agree with all the points, I appreciate your input. Since this discussion is getting lengthy, I’ll only highlight the points the judge considered in his last comment:
The $2+ billion doesn't qualify under the following rule:
- Please note that these calculations weren't optimized; they primarily serve to demonstrate that the attack is possible today, even without using any new or unknown, but theoretically anticipated, technology.
- We can always reduce the attack cost by extending its duration. For example, let's use θ = 2^-23 and m = 52, and set electricity to the cheapest available rate of $0.002
My hope in showing that this attack is already feasible, albeit expensive, was to illustrate how close we are to making it even cheaper, especially when considering theoretical calculations that bring the cost down to the lower millions—particularly if we factor in ASIC optimization to the level of Bitcoin miners, as estimated in the paper.
The biggest impact: the entire protocol could be compromised, as an attacker could vote for their own hat
, allowing them to change sensitive protocol parameters to arbitrary values. Let me know if you'd like more concrete examples.
The $250 million is only in LSE, but there is more MKR in circulation. This wasn’t explicitly mentioned in the README, so I think it’s best to reference the current valuation, which is $1.9 billion.
We also need to add up to $100 million of DAI (as mentioned in readme) per collateral type because, by gaining control of the line
parameter, an attacker would be able to mint an indefinite amount of DAI, crashing the price. Please note that line
is different from Line
. See glossary for more details.
line: the debt ceiling for a specific collateral type. Line: the total debt ceiling for all collateral types.
There are 66 ilks in IlkRegistry.
I believe we should also consider the loss of all DAI and other Maker assets in the system. If the attacker can elect a new hat, they could potentially shut down the protocol or mint an unlimited amount of DAI (as mentioned in the Impact section). They would also be able to modify the line.
Still based on the above arguments, I believe we should account for $250 million as the maximum loss here.
We can always reduce the attack cost by extending its duration. For example, let's use θ = 2^-23 and m = 52, and set electricity to the cheapest available rate of $0.002
As I understand it's still the cost to get a 50% chance of finding a collision, correct? And the cost to get at least >90% would be much higher?
My hope in showing that this attack is already feasible, albeit expensive, was to illustrate how close we are to making it even cheaper, especially when considering theoretical calculations that bring the cost down to the lower millions—particularly if we factor in ASIC optimization to the level of Bitcoin miners, as estimated in the paper
But the problem is that it's still theoretical and I believe in reality would cost a lot more than we theoretically calculate here. For example, you shared that the lowest electricity cost is 0.002$ in Iran, but what about the cost of transporting all the equipment? I believe accounting for it will also significantly increase the cost of the attack and it's only one example of the unaccounted variables which I think there are more.
About the last section in the above comment, I believe the following part from the @panprog's comment:
It doesn't allow to steal all MKR locked in VoteDelegates, only from VoteDelegates selected by lockstake users in amounts selected (since owner is LockstakeEngine, thus it can't withdraw more than lockstake users locked). It doesn't allow to steal from funds locked in lockstake which do not have VoteDelegate selected. Since lockstake allows up to $250M locked by the rules of this contest, the attack impact is at most $250M, but likely a bit less (say, we can reasonably expect 90% lockstake users to have VoteDelegate selected, meaning attack impact is around $225M). Generally we can't tell if it allows to gain control over Maker protocol or elect attacker's hat with all the voting power stolen. In particular, the $250M lockstake limit assumes most MKR will not be locked in lockstake and can be used to prevent this impact. So attacker can't be sure in any impact other than $225M worth of MKR being stolen
I believe it answers your concern.
Moreover, with the new calculations, the length of the attack is 17+ years. I understand that the duration is not specified in our rules, but it's the constraint we have to consider when defining the severity.
Hence, I believe based on all the arguments, i.e. cost of the attack is still significant, the cost of $287 million is theoretical and I believe is unrealistic due to unaccounted costs and not a high probability of finding a hash collision, also the extensive length of the attack, this issue is low severity. Planning to accept the escalation and invalidate the issue.
Thank you for your detailed response.
Still based on the above arguments, I believe we should account for $250 million as the maximum loss here.
I'm not sure I understand why we are limiting the loss to only $250 million. Could you elaborate on this, please?
The attacker first steals $250 million worth of MKR from the most active voters—more votes than have ever been cast in any previous vote. This allows the attacker to gain full control of the Maker protocol, which includes both MKR and DAI, while the lockstake is only a module of the protocol.
As I understand it's still the cost to get a 50% chance of finding a collision, correct?
For 2^81 hashes, the probability of a collision is 86.47%. With 2^82 hashes, it's 99.97%. You can see this in the formulas for collision probabilities I provided here and verified in the spreadsheet here.
To quickly confirm that these formulas are correct, you can refer to the probability table for the birthday paradox on Wikipedia here. The calculations there match the formula I provided. You can check this in list 2 of the same spreadsheet. I have reproduced the calculations for 2^256 possible hashes, and the probabilities match exactly with those listed on Wikipedia.
And the cost to get at least >90% would be much higher?
2^82 is sufficient for a 99.97% probability. It’s a 7.33% increase to achieve over 90%. So 2x to get to 99.97% and 7.33% to get to 90%.
But the problem is that it's still theoretical and I believe in reality would cost a lot more than we theoretically calculate here. For example, you shared that the lowest electricity cost is $0.002 in Iran, but what about the cost of transporting all the equipment? I believe accounting for that will significantly increase the cost of the attack, and it's only one example of unaccounted variables, which I think there are more.
I don't believe it's possible to account for everything, so we need to simplify and overlook some factors. However, I would also argue that there are unaccounted optimizations as well. Because the paper estimates the attack cost to be in $10s of millions and take 1 year. Therefore, there must be several other optimizations to reach this number.
About the last section in the above comment, I believe the following part from the @panprog's comment I > I believe it answers your concern.
It doesn't allow to steal from funds locked in lockstake which do not have VoteDelegate selected
This is incorrect, as I stated in my reply, point 2 here.
Generally we can't tell if it allows to gain control over Maker protocol or elect attacker's hat with all the voting power stolen.
I responded to this in my comment and provided data showing that the largest votes in history involved 113,809 MKR, which is worth $231 million. The attacker would steal more MKR than has ever been voted with, giving them a very high chance of executing the attack. Everyone else would need to gather even more votes than have ever been collected in the entire history of Maker (or at least the last 3 years). So, with the attacker's votes, this vote would have twice+ as many as ever before, and they would need to accomplish this without the participation of the most active voters (the attacker stole their votes). All of this would need to happen within 16 hours.
Moreover, with the new calculations, the length of the attack is 17+ years. I understand that the duration is not specified in our rules, but it's a constraint we must consider when defining the severity.
Could you expand on this? In your opinion, what cost and length of an attack would be reasonable to classify this issue as Medium severity?
It doesn't allow to steal from funds locked in lockstake which do not have VoteDelegate selected
This is incorrect, as I stated in my reply, point 2 here.
I appologize I overlooked this, yes, this point (2) is incorrect, but this doesn't really change anything as this simply allows to steal all MKR in the lockstake ($250M) and not only lockstake MKR locked in VD (which I estimated to be $225M) - the cost of the attack then should be below $375M (instead of $340M I estimated). I think everyone still assumed $250M, so no difference with this point. The other points are correct.
As for taking control over entire protocol with stolen MKR - this is still speculation and attacker can not be sure in this. Given the threat to the whole protocol, many inactive voters can vote against the attacker. The fact that the largest voting in history involved $231M worth of MKR doesn't ensure a successful attack, voting where the entire protocol is at stake is very different from all the other voting in the history. For example, large market makers who normally don't care about voting will be incentivized to move funds from the exchanges to vote not to lose their money etc.
It's become evident that the Lead Senior Watsons are employing various strategies to challenge the validity of this issue. Their methods range from standard procedures to potentially questionable tactics. A concerning aspect of this situation is that the judge appears to be accepting comments without requiring substantiating evidence, which raises questions about the process.
With significant attention focused on these matters, Sherlock will make a decision in the coming days. However, given the current circumstances, it's clear that these mediums will not be approved.
Let's face it: Sherlock isn't about to rock the boat. They'll undoubtedly find some convoluted reason to reject the proposal, even though approving would be the sensible choice. With a judge who doesn't seem interested in demanding proof and decision-makers who always play it safe, this outcome was practically guaranteed from the start.
@00xSEV Thanks to you, this thread is now the most comprehensive discussion of the create2 hash collision issue, but the gap in DB tech remains unchallenged. Would you mind responding to this comment?
The gap between current tech and what's needed is astronomical (10 orders of magnitude):
There's no notable memory cost with the application of Pollard's rho algorithm.
Section 5.2 of https://people.scs.carleton.ca/~paulv/papers/JoC97.pdf.
The memory requirements for a hash function attack can be eliminated using collision search techniques.
6.2 goes over a theoretical ASIC to solve this problem, for MD5. They design a machine with 18 GB of memory which completes in 21 days and have the following note:
The run-time of this attack is proportional to the square root of the hash result space. Thus, if this attack were applied to SHA-1 whose hash results are 160 bits long (compared to 128 bits for MD5), the attack would take 2**16 times longer.
That'd have this attack take 10 years with that memory config, yet the full formula is there to be played with and it's not impossible (and arguably not infeasible) as-written.
@kayabaNerve thanks, so the reads and writes need to be divided by theta (2^23 for the 17 years scenario)? So:
From 6.2,
The overall rate at which the processors produce distinguished points is mθ ⁄ t = 405 per second, which can be accommodated quite easily by the large memory.
18 GB of RAM can have 405 * 22 bytes written per second. Even if you double 22 bytes to accomodate how our hash is 25% larger, you end up with 17.4 KB/s. Your read/write numbers are horrendously off-base AFAICT.
Hi @00xSEV, I am afraid I have to step in and make a correction regarding this comment of yours:
As I understand it's still the cost to get a 50% chance of finding a collision, correct?
For 2^81 hashes, the probability of a collision is 86.47%. With 2^82 hashes, it's 99.97%. You can see this in the formulas for collision probabilities I provided here and verified in the spreadsheet here.
To quickly confirm that these formulas are correct, you can refer to the probability table for the birthday paradox on Wikipedia here. The calculations there match the formula I provided. You can check this in list 2 of the same spreadsheet. I have reproduced the calculations for 2^256 possible hashes, and the probabilities match exactly with those listed on Wikipedia.
And the cost to get at least >90% would be much higher?
2^82 is sufficient for a 99.97% probability. It’s a 7.33% increase to achieve over 90%. So 2x to get to 99.97% and 7.33% to get to 90%.
I am afraid it's all not that simple. The $\frac{2^{81}}{m} + \frac{2.5}{\theta}$ formula for the runtime from this paper is actually an approximation of the original result from 2013 paper Parallel Collision Search with Cryptanalytic Applications by Paul C. van Oorschot & Michael J. Wiener. The original formula for the expected runtime for finding a hash collision (see p.15, eq. 7) is:
$$T_{hash} = (\sqrt{\pi n}/m + 2.5/\theta) \cdot t$$
In the formula above, $n$ is the size of the state space ($2^{160}$), $m$ is the number of parallel processors, $\theta$ is the proportion of distinguihed points, and $t$ is the time to compute a single hash function. $\sqrt{n} = 2^{80}$, and $\sqrt{\pi} \approx 1.77$, thus $\sqrt{\pi n} \approx 2^{81}$; here is where $2^{81}$ comes from.
Now, the runtime of parallel version of Pollard's Rho algorithm with distinguished points has nothing to do with the probabilities from Wikipedia's Brithday problem's probabilities: they are very much related, but it's still very much apples and oranges. The probabilities from the Birthday problem table can be applied only to the naive algorithm; they are related to the Pollard's algorithm expected runtimes, but not directly. The formula above gives the expected runtime, which roughly corresponds to 50% probability of success, i.e. for a large number of experiments (if we had the time and resources to conduct those), 50% would have the runtime to find a collision lower than that, and 50% would have the runtime higher than that.
I do find that you bring very valuable arguments for the viability of the attack, and also did a great work analyzing the costs and runtimes, but I have to make this specific correction for the sake of mathematical correctness.
I've hidden one comment above because it was subjective, personal, didn't bring value and was essentially trying to manipulate the decision without providing any concrete evidence of this being a valid medium. Please refrain from such comments.
Thanks to everyone for such extensive comments, I'm amazed by everyone here.
But, @00xSEV, as I understand, for the impacts shared in the report, the attacker has to actually be able to win on every vote, which is probability speculation as also detailed by @panprog in this. I actually agree with this and indeed if there's voting where the life of the protocol and the funds of each user are at stake, there would be a much larger voting power. That's why I believe it would be fair to limit the damage to $250m, because as I understand, these $250m are directly at threat, while other impacts depend on voting and our discussion about voting here would be a speculation from both sides. It also applies to the following:
I responded to this in https://github.com/sherlock-audit/2024-06-makerdao-endgame-judging/issues/64#issuecomment-2303596707 and provided data showing that the largest votes in history involved 113,809 MKR, which is worth $231 million. The attacker would steal more MKR than has ever been voted with, giving them a very high chance of executing the attack. Everyone else would need to gather even more votes than have ever been collected in the entire history of Maker (or at least the last 3 years). So, with the attacker's votes, this vote would have twice+ as many as ever before, and they would need to accomplish this without the participation of the most active voters (the attacker stole their votes). All of this would need to happen within 16 hours.
For 2^81 hashes, the probability of a collision is 86.47%. With 2^82 hashes, it's 99.97%. You can see this in the formulas for collision probabilities I provided https://github.com/sherlock-audit/2024-06-makerdao-endgame-judging/issues/64#issuecomment-2303596707 and verified in the spreadsheet here.
Thank you, excuse me for misunderstanding it.
I don't believe it's possible to account for everything, so we need to simplify and overlook some factors. However, I would also argue that there are unaccounted optimizations as well. Because the paper estimates the attack cost to be in $10s of millions and take 1 year. Therefore, there must be several other optimizations to reach this number.
Fair enough, but that's a very big problem. We do not account for a lot of variables both increasing and decreasing the cost and our calculations are very theoretical and we potentially can decrease the cost of the attack to be even less than $10m, but none of that means that the issue is possible in reality (I'm not trying to say it's infeasible, but that in reality, the cost would be much higher than we calculate on paper).
Could you expand on this? In your opinion, what cost and length of an attack would be reasonable to classify this issue as Medium severity?
In my opinion, the reasonable length would be <=10 years at least (Ideally even less) and the cost basically <=$375m, assuming that $250m are directly at threat and other funds are speculation because there's no guarantee the attacker would actually win the votes.
Also, thinking more about the optimisations you mentioned here, I think they're also speculative:
What I'm trying to say is that this issue has a lot of speculations on the actual cost of the attack and the real impact of the attack. Even with these great calculations (honestly, great job), we can't know what it would cost in reality and if the attacker would be able to actually win the votes, assuming the situation with MKR and locked funds will be completely different when the attack takes place and adds even more speculation.
Hence, my decision remains the same, accept the escalation and invalidate this issue.
@kayabaNerve
Your read/write numbers are horrendously off-base AFAICT.
The overall rate at which the processors produce distinguished points is mθ ⁄ t = 405 per second
I'm afraid my numbers do check out using the simple formula you quoted:
I'm pretty sure in the above calculations, them being so simple.
Less sure about why extrapolation in the paper contradicts this simple calculation in our case. I see two flaws:
we must fix the amount of memory, and it is possible that an MD5 collision will not be found before the memory fills up. In this case, we continue by simply overwriting new distinguished points on top of old 22 ones.
The rate at which they must overwrite those points, for different m, t, and theta is not considered a bottleneck, but it can be (as shown in the calculations).
Additionally, using this seems wrong:
The run-time of this attack is proportional to the square root of the hash result space. Thus, if this attack were applied to SHA-1 whose hash results are 160 bits long (compared to 128 bits for MD5), the attack would take 216 times longer.
We cannot use the same t for keccak256, since the t they used is specifically for their (theoretical) chip for the simpler MD5.
1) I thought I caveated it's a distinct hash function not just in bit length, but apologies if I forgot to. I do agree that changes the theoretical cost/complexity of an ASIC that has the same performance they assume, but that's not the point here.
2) They estimate 405 writes per second given a machine which does so many hashes (the exact hash done doesn't matter, solely the rate). Your sole commenting of "read/write" without distinguishing is harmful IMO. The writes are trivially allowable.
The reads, they don't comment on, and I was unclear the rate myself. Let's assume it's your number which is in fact 1000x more than feasible today from a single DB.
It's 19 GB. Just RAM cache it and replicate it 1000x. If I'm allowed 2**80 iterations yet not 19 TB of RAM, I have an incredibly stupid millionaire funding me. Even with doubled requirements for overhead, 38 TB isn't an issue. Even further doubling due to the larger size of the hash and further overhead isn't an issue.
This commentary is due to how the length of the dataset doesn't increase with the hash's bit-length (solely the runtime, per my quote).
I'll also reiterate I didn't participate in this report in any way, I solely commented on this mediation.
@kayabaNerve the static size isn't the concern, but the rates specifically.
You can only "simply replicate" DBs if they're isolated in usage - what you write in one instance doesn't have to be read from another. If it were so, no DB is needed, just process it locally (like PoW).
In our case we are looking for collisions (common distinguished points) in parallel, so each of the instances needs to read what others have written (in at least an eventually consistent way), and at the same time needs to write its work for others to be able to read it. This trivially proves the need for reading and writing at least once per distinguished point into the DB shared by all "searchers". With the numbers used here, it appears to be infeasible with current tech.
405 distinguished points per second was for all machines (the m
variable in the formula), not for each. The idea you can't handle 405 ~30 byte writes per second across a replicated database, even if one replicated 1000 times, is ridiculous to me.
You're welcome to disagree/refute me, though I've volunteered enough time I'm fine not further participating (especially since I'm not actually involved, and I believe this mediation was decided in the negative despite the paper I've cited roughly estimating a 10m USD cost over a 10y time period. Accordingly, even if I successfully argue its claims (for which I have no incentive), it's moot).
This report seems decided regardless of this point, and I'm just trying to get closer to the truth for future reference. I hope that someone else may correct these points if they are wrong.
The idea you can't handle 405 ~30 byte writes per second
@kayabaNerve I think you missed why 405 is the wrong number to use (it uses wrong m, theta, and t)
The overall rate at which the processors produce distinguished points is mθ ⁄ t = 405 per second
- m in our case is 1M, theta is 2^-23, and t is 1/35×10^9 (35 GH/s for each ASIC). This gives 4172325134, or 4.2*10^9 in my previous comment. 4 Billion read and writes per second. 1000x more than currently possible.
and the t is not applicable to this case even if the paper's theoretical machine is assumed
We cannot use the same t for keccak256, since the t they used is specifically for their (theoretical) chip for the simpler MD5.
We cannot use the same t for keccak256, since the t they used is specifically for their (theoretical) chip for the simpler MD5.
Yes, I ignored whatever fixed ratio is relevant due to the 27 years of progress in silicon. If we can now do keccak256 faster than we could do MD5 in 1997, we could simply downclock. If we're still several times slower, the small factor doesn't explain the breadth of our disagreeance.
I'm unclear your reasoning for your choice of theta. It went from (0.66)2-35 to 2-23 and is why these numbers are so distinct. Apologies if there is an undeniable reason for that which I'm missing, as yes, that'd be my blunder.
00xSEV
High
An attacker can exploit LSUrn address collisions using create2 for complete control of Maker protocol
Summary
An attacker can use brute force to find a collision between a new urn address (dependent solely on
msg.sender
) and an EOA controlled by the attacker. While this currently costs between $1.5 million and several million dollars (detailed in "Vulnerability Details"), the cost is decreasing, making the attack more feasible over time.By brute-forcing two such urns, the attacker can transfer all MKR used in LSE and VDs to their own VD, allowing them to elect any new
hat
and potentially take full control of the Maker protocol.Vulnerability Detail
Feasibility of Collision
The current cost of this attack is estimated to be less than $1.5 million at current prices.
The computational, time, and memory costs have been extensively discussed in many issues with multiple judges, concluding that the attack is possible, albeit relatively expensive (up to millions of dollars). Given that MKR's market cap is ~$2.2 billion as of August 3, and 11.7% ($242 million) is now delegated, the potential profit significantly outweighs the cost of the attack.
Considering that the reviewed contracts are the final state of MakerDAO, we must be aware that future price drops for this attack will occur due to new algorithms, reduced computational costs, and specialized hardware (ASICs). These machines, created for the attack, could also be used to compromise other protocols, further reducing the cost per attack. Additionally, growth in Maker's market cap can make the attack more profitable and worthy of investment.
Examples of Previous Issues with the Same Root Cause
Summary
The current cost of this attack is estimated to be less than $1.5 million at current prices.
An attacker can find a single address collision between (1) and (2) with a high probability of success using the meet-in-the-middle technique, a classic brute-force-based attack in cryptography:
The feasibility, detailed technique, and hardware requirements for finding a collision are well-documented:
The Bitcoin network hashrate has reached 6.5x10^20 hashes per second, taking only 31 minutes to achieve the necessary hashes. A fraction of this computing power can still find a collision within a reasonable timeframe.
Steps
eoa11
eoa12
, when used as a salt for LSUrn creation, produces an urn with an address equal toeoa11
.vat.hope(attacker)
andlsmkr.approve(attacker, max)
fromeoa11
.LSE.open(0)
fromeoa12
:LSUrn1
.LSUrn1
address ==eoa11
address.LSUrn1
retains the approvals given fromeoa11
in step 2.eoa21
,eoa22
, andLSUrn2
.LSE.lock(LSUrn1, 1000e18)
to deposit 1000 MKR intoLSUrn1
:vat.urns[LSUrn1].ink
by 1000e18.urnVoteDelegates[LSUrn1]
remainsaddress(0)
.LSUrn1
toLSUrn2
:attacker
account usingvat.fork
because both LSUrns have given approval to theattacker
address.vat.frob
can be used to move fromvat.urns[LSUrn1].ink
tovat.gem[LSUrn1]
, and thenvat.frob
to move fromvat.gem[LSUrn1]
tovat.urns[LSUrn2].ink
.attackersVD
(controlled by the attacker) usingVoteDelegateFactory.create
from theattacker
address.LSE.selectVoteDelegate(LSUrn1, victimVD)
:victimVD
is the target for fund extraction.vat.urns(ilk, urn)
.LSUrn2
in step 6,LSUrn1
has 0 .ink, so no funds are moved tovictimVD
, buturnVoteDelegates[LSUrn1]
is set tovictimVD
.LSUrn2
back toLSUrn1
(See step 6).LSE.selectVoteDelegate(LSUrn1, attackersVD)
:LSUrn1
has 1000e18 .ink.VD.withdraw
inside_selectVoteDelegate
withprevVoteDelegate
set tovictimVD
.victimVD
toattackersVD
.LSE.selectVoteDelegate(LSUrn2, victimVD)
(see step 8).LSUrn1
toLSUrn2
(See step 6).LSE.selectVoteDelegate(LSUrn2, attackersVD)
(see step 10):vat.urns[LSUrn2].ink
== 1000e18.attackersVD
balance of MKR is 2000e18.victimVD
.victimVD
.victimVD
withaddress(0)
and repeat steps 8-13 to move all funds in LSE toattackersVD
.LSE.free
850 MKR (depositing 1000 MKR - 15% withdrawal fee) to reduce the capital/cost required for the attack.hat
and vote for it with all the stolen power (almost all active voters), thereby gaining full control of the system:hat
from being selected.Result:
attackersVD
, effectively immobilizing all LSE.hat
election.Other Variations:
eoa11
can be replaced with a contract created byeoa3
. The address of the contract can be brute-forced in the same way aseoa11
. The contract performs step 2 instead ofeoa11
and self-destructs in the same transaction.LSUrn2
will be a regular urn. In step 13, the attacker must transfer LS MKR fromLSUrn1
and withdraw 85% (with a 15% withdrawal fee). They then deposit (lock
) it inLSUrn1
and repeat the process. Refer toALSEH6.testAttack1Loop1Urn
in PoC.testAttack4SendOneInk*
.LSUrn1
(testAttack5SendLsMkr).Link to create2
Impact
delay
(16 hours).chief.hat
, thereby gaining full control over the system:Line
).attackersVD
. This will brick all LSE operations.Code Snippet
test/ALockstakeEngine.sol
in the root project directory.test/ALockstakeEngine.sol
It is based on the
LockstakeEngine.t.sol
setUp
function:block.number
for caching RPC callschief
andpolling
contracts from mainnetVoteDelegateFactory
To see the diff, you can run
git diff
. Note: all other functions exceptsetUp
are removed from the file and the diff.git diff --no-index lockstake/test/LockstakeEngine.t.sol test/ALockstakeEngine.sol
```diff diff --git a/lockstake/test/LockstakeEngine.t.sol b/test/ALockstakeEngine.sol index 83fa75d..ba4f381 100644 --- a/lockstake/test/LockstakeEngine.t.sol +++ b/test/ALockstakeEngine.sol @@ -2,20 +2,32 @@ pragma solidity ^0.8.21; -import "dss-test/DssTest.sol"; -import "dss-interfaces/Interfaces.sol"; -import { LockstakeDeploy } from "deploy/LockstakeDeploy.sol"; -import { LockstakeInit, LockstakeConfig, LockstakeInstance } from "deploy/LockstakeInit.sol"; -import { LockstakeMkr } from "src/LockstakeMkr.sol"; -import { LockstakeEngine } from "src/LockstakeEngine.sol"; -import { LockstakeClipper } from "src/LockstakeClipper.sol"; -import { LockstakeUrn } from "src/LockstakeUrn.sol"; -import { VoteDelegateFactoryMock, VoteDelegateMock } from "test/mocks/VoteDelegateMock.sol"; -import { GemMock } from "test/mocks/GemMock.sol"; -import { NstMock } from "test/mocks/NstMock.sol"; -import { NstJoinMock } from "test/mocks/NstJoinMock.sol"; -import { StakingRewardsMock } from "test/mocks/StakingRewardsMock.sol"; -import { MkrNgtMock } from "test/mocks/MkrNgtMock.sol"; +import "../dss-flappers/lib/dss-test/src//DssTest.sol"; +import "../dss-flappers/lib/dss-test/lib/dss-interfaces/src/Interfaces.sol"; +import { LockstakeDeploy } from "../lockstake/deploy/LockstakeDeploy.sol"; +import { LockstakeInit, LockstakeConfig, LockstakeInstance } from "../lockstake/deploy/LockstakeInit.sol"; +import { LockstakeMkr } from "../lockstake/src/LockstakeMkr.sol"; +import { LockstakeEngine } from "../lockstake/src/LockstakeEngine.sol"; +import { LockstakeClipper } from "../lockstake/src/LockstakeClipper.sol"; +import { LockstakeUrn } from "../lockstake/src/LockstakeUrn.sol"; +import { VoteDelegateFactoryMock, VoteDelegateMock } from "../lockstake/test/mocks/VoteDelegateMock.sol"; +import { GemMock } from "../lockstake/test/mocks/GemMock.sol"; +import { NstMock } from "../lockstake/test/mocks/NstMock.sol"; +import { NstJoinMock } from "../lockstake/test/mocks/NstJoinMock.sol"; +import { StakingRewardsMock } from "../lockstake/test/mocks/StakingRewardsMock.sol"; +import { MkrNgtMock } from "../lockstake/test/mocks/MkrNgtMock.sol"; + +import {VoteDelegateFactory} from "../vote-delegate/src/VoteDelegateFactory.sol"; +import {VoteDelegate} from "../vote-delegate/src/VoteDelegate.sol"; + + +contract DSChiefLike { + DSTokenAbstract public IOU; + DSTokenAbstract public GOV; + mapping(address=>uint256) public deposits; + function free(uint wad) public {} + function lock(uint wad) public {} +} interface CalcFabLike { function newLinearDecrease(address) external returns (address); @@ -29,7 +41,7 @@ interface MkrAuthorityLike { function rely(address) external; } -contract LockstakeEngineTest is DssTest { +contract ALockstakeEngineTest is DssTest { using stdStorage for StdStorage; DssInstance dss; @@ -40,7 +52,7 @@ contract LockstakeEngineTest is DssTest { LockstakeClipper clip; address calc; MedianAbstract pip; - VoteDelegateFactoryMock voteDelegateFactory; + VoteDelegateFactory voteDelegateFactory; NstMock nst; NstJoinMock nstJoin; GemMock rTok; @@ -84,8 +96,13 @@ contract LockstakeEngineTest is DssTest { } } - function setUp() public { - vm.createSelectFork(vm.envString("ETH_RPC_URL")); + // Real contracts for mainnet + address chief = 0x0a3f6849f78076aefaDf113F5BED87720274dDC0; + address polling = 0xD3A9FE267852281a1e6307a1C37CDfD76d39b133; + uint chiefBalanceBeforeTests; + + function setUp() public virtual { + vm.createSelectFork(vm.envString("ETH_RPC_URL"), 20422954); dss = MCD.loadFromChainlog(LOG); @@ -101,7 +118,10 @@ contract LockstakeEngineTest is DssTest { MkrAuthorityLike(mkr.authority()).rely(address(mkrNgt)); vm.stopPrank(); - voteDelegateFactory = new VoteDelegateFactoryMock(address(mkr)); + // voteDelegateFactory = new VoteDelegateFactoryMock(address(mkr)); + voteDelegateFactory = new VoteDelegateFactory( + chief, polling + ); voter = address(123); vm.prank(voter); voteDelegate = voteDelegateFactory.create(); ```Add the following
remappings.txt
to the root project directory.Run
forge test --match-path test/ALSEH5.sol -vvv
(PoCs for 2 LSUrns)pragma solidity ^0.8.21;
import "./ALockstakeEngine.sol";
contract VoteDelegateLike { mapping(address => uint256) public stake; }
interface ChiefLike { // function GOV() external view returns (GemLike); // function IOU() external view returns (GemLike); function lock(uint256) external; function free(uint256) external; function vote(address[] calldata) external returns (bytes32); function vote(bytes32) external; // mapping(address => uint256) public deposits; function deposits(address) external returns (uint); }
contract ALSEH5 is ALockstakeEngineTest { // Just some address that the attacker wants to use, a regular EOA address attacker = makeAddr("attacker"); // Address mined by the attacker to create LSUrn // so that the LSUrn address will be equal to an EOA controlled by the attacker address minedUrnCreator = makeAddr("minedUrnCreator");
}
Tool used
Manual Review
Recommendation
salt
, including usingmsg.sender
.block.prevrandao
withmsg.sender
. This approach will make finding a collision practically impossible within the short timeframe thatprevrandao
is known.