0x52 - Router.sol is vulnerable to address collission

[sherlock-admin2]

0x52

medium

Router.sol is vulnerable to address collission

Summary

Router.sol never verifies that the callback msg.sender is actually a deployed pool. This allows for a provable address collision that can be used to drain all allowances to the router.

Vulnerability Detail

The pool address check in the the callback function isn't strict enough and can suffer issues with collision. Due to the truncated nature of the create2 opcode the collision resistance is already impaired to 2^160 as that is total number of possible hashes after truncation. Obviously if you are searching for a single hash, this is (basically) impossible. The issue here is that one does not need to search for a single address as the router never verifies that the pool actually exists. This is the crux of the problem, but first let's do a little math as to why this is a problem.

A primer on hash collision probability can be found here (https://kevingal.com/blog/collisions.html). The odds of a collision are dependant on both the amount of addresses to search against as well as the number of brute force attempts to match them. From the article linked we can see that the estimated odds of collision are:

$$ 1 - e ^ {-k(k-1) \over 2N } $$

Where k is the number of hash values and N is the number of possible hashes

For very large numbers we can further approximate the exponent to:

$$ -k^2 \over 2N $$

This exponent is now trivial to solve for an approximate attack value which is:

$$ k = \sqrt{2N} $$

In our scenario N is 2^160 (our truncated keccak256) which means that our approximate attack value is 2^80 since we need to generate two sets of hashes. The first set is to generate 2^80 public addresses and the second is to generate pool address from variations in the pool specifics(token0, token1, fee). Here we reach a final attack value of 2^81 hashes. Using the provided calculator we see that 2^81 hashes has an approximate 86.4% chance of a collision. Increase that number to 2^82 and the odds of collision becomes 99.96%. In this case, a collision between addresses means breaking this check and draining the allowances of all users to a specific token. This is because the EOA address will collide with the supposed pool address allowing it to bypass the msg.sender check. Now we considered the specific of the contract.

Router.sol#L47-L51

require(
  msg.sender == address(_getPool(tokenIn, tokenOut, fee)),
  'Router: invalid callback sender'
);

The above snippet from the swapCallback function is used to verify that msg.sender is the address of the pool.

Router.sol#L224-L231

function _getPool(
    address tokenA,
    address tokenB,
    uint24 fee
) private view returns (IPool) {
    return IPool(PoolAddress.computeAddress(factory, tokenA, tokenB, fee, poolInitHash));
}

We see that these lines never check with the factory that the pool exists or any of the inputs are valid in any way. token0 can be constant and we can achieve the variation in the hash by changing token1. The attacker could use token0 = WETH and vary token1. This would allow them to steal all allowances of WETH. Since allowances are forever until revoked, this could put hundreds of millions of dollars at risk.

Although this would require a large amount of compute it is already possible to break with current computing. Given the enormity of the value potentially at stake it would be a lucrative attack to anyone who could fund it. In less than a decade this would likely be a fairly easily attained amount of compute, nearly guaranteeing this attack.

Impact

Address collision can cause all allowances to be drained

Code Snippet

Router.sol#L39-L70

Tool used

Manual Review

Recommendation

Verify with the factory that msg.sender is a valid pool

[sherlock-admin]

1 comment(s) were left on this issue during the judging contest.

Trumpero commented:

invalid, it's impossible to override an existing contract in EVM. From EIP-684

[IAm0x52]

Escalate

I believe this has been incorrectly excluded.

invalid, it's impossible to override an existing contract in EVM. From EIP-684

Judges comment here is incorrect. A contract won't exist at this address since the collision would likely occur with at least one ERC20 token that doesn't exist. To reiterate what is in my submission, I think that in the current implementation the collision resistance is not strong enough. The currently available hashing power makes this risk very real (profitability will improve with time) and the losses could be enormous. The router contract is an immutable contract which means that it is almost guaranteed that with time this will be exploited, since it can't be fixed via upgrade. By implementing my suggested mitigation, the chance of exploit becomes zero due to EIP-684.

[sherlock-admin2]

Escalate

I believe this has been incorrectly excluded.

invalid, it's impossible to override an existing contract in EVM. From EIP-684

Judges comment here is incorrect. A contract won't exist at this address since the collision would likely occur with at least one ERC20 token that doesn't exist. To reiterate what is in my submission, I think that in the current implementation the collision resistance is not strong enough. The currently available hashing power makes this risk very real (profitability will improve with time) and the losses could be enormous. The router contract is an immutable contract which means that it is almost guaranteed that with time this will be exploited, since it can't be fixed via upgrade. By implementing my suggested mitigation, the chance of exploit becomes zero due to EIP-684.

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.

[Trumpero]

@IAm0x52
I agree that the statements in this issue are correct. However, the likelihood of this issue occurring is nearly impossible, and the cost to attack it will be unreal. These issues can be found in other protocols such as UniswapV3, and I believe those protocols don't need to fix it because the issue is mostly impossible to happen in reality. Therefore, this issue should be considered as a low or non-issue.
References:
https://github.com/Uniswap/v3-periphery/blob/main/contracts/SwapRouter.sol#L65
https://github.com/Uniswap/v3-periphery/blob/main/contracts/libraries/CallbackValidation.sol#L21

[IAm0x52]

2^80 is 1.208e24

The current hashrate of Bitcoin is 4.71e20

1.208e24/4.71e20 = 2565.61

This means 2^80 hashes can be generated in 2565 seconds or less than 1 hour. 2^82 (our near guaranteed collision) would be generated in 10260 seconds or ~3 hours. I am aware that Bitcoin uses SHA256 while the hash in this case is Keccak256 but SHA256 is only ~50% faster which means that the resources required to exploit this would be ~50% higher. As shown this would still result in a trivial low amount of time crack it. With a compute of only 1% of the current Bitcoin hashrate, the attack would take ~17-23 days (1,500,000-2,000,000 seconds). As stated in my original submission, this attack is already possible and profitable, though the attacker would need to be well funded.

[manhlx3006]

Hi,
Even though it is possible for the collision, as you also mentioned, the attacker needs to have a huge computation power, which also means it takes a long time and spends a big amount of expense in order to check IF the attack is possible. In another note, the Router is developed and mainly used by developers which makes the potential profit from the attack is even less (if they wait for a benefit is high enough to start performing the attack, they can not be sure the actual attackable funds after 3-4 weeks, while spending huge amount of funds from their side).

On the other hand, while the collision can be achieved by 2^82 hash, it also requires a database of 2^81 * 20 bytes to store all the EOA addresses (which is quite impossible for current hardware market).

Thus, the likelihood of this attack to happen is really low and unpractical.

[jkoppel]

0x52 is correct. I checked the calculations. The calculator linked to is for a slightly different scenario than this one and is too low by a factor of 2 for number of hashes needed. Even with that, this attack is certain to be feasible, and quite economical within the next decade. All it takes is a single large transaction going through the router for this attack to become profitable.

@manhlx3006 is correct that a naive collision-finding algorithm would take an astronomical amount of space. But you don't build a secure system by requiring an attacker to use a naive algorithm. You want to use 20 bytes to store every hash computed? Try using a Bloom filter and using 1 bit instead. I'm sure it can be brought down more; I expect that some clever hashing schemes can produce a result of the form "This input has a hash collision with one of these 2^40 other inputs." That reduces the 2^81 compute 2^80 storage problem into a 2^81 compute 2^41 storage problem followed by a second 2^40 compute problem.

Regardless, how much do you want to bank on a solution to the storage problem not existing? The hashing problem is believed to be computationally irreducible; the storage problem is not.

[IAm0x52]

@jkoppel hit the nail on the head with his explanation with respect to the storage requirement.

Additionally you are deploying an immutable router contract. Approval are permanent unless actively revoked. Very easy to accrue tens of millions of dollars worth of vulnerable approvals even with a low volume protocol. As an example, the vulnerable sushiswap router accumulated multiple millions worth in a few days. Simply being an approval to an immutable contract massively increases the scope of the vulnerable funds.

Storage and compute are getting exponentially cheaper with each passing year, bringing the cost down significantly with time.

[IAm0x52]

My final set of thoughts on the matter:

I don't think there is anything much hypothetical left in this scenario.

The profit motive is huge. Relatively low use applications garner millions in exploitable approvals (i.e. Sushiswap Router)

You can see a coded POC here showing exactly what I'm talking about in the link below. It generates 2^8 random addresses then looks for matches in a domain of 2^24. The average across 10 runs is 65586, which is almost perfectly 2^16 (65536). This exactly lines up with the figures presented in my original submission.

https://gist.github.com/zobront/263f7cd6df079a48d9f96c83ef369f69

There is no hypothetical to the collision. The collision WILL happen as shown from the POC above. The collision resistance is 2^81 which is not suitable collision protection.

The Bitcoin network performs ~2^67 hashes per second, which means the network’s hash power is enough to perform this attack every ~2 hours. Meanwhile, the block rewards for Bitcoin are 6.25 BTC / block, implying that this much hash power is purchased for ~$2mm every 2 hours. The compute is already possible.

Optimization to storage makes storage requirements possible as pointed out in @jkoppel comment above.

Compute and storage will continue to become cheaper and the contract is immutable, so no upgrade can fix this. The cost of exploit becomes lower with each passing day.

Another consideration is that subsequent attacks become half as expensive. Once you have the EOA's generated you can reuse them to start attacking the next target coin.

Last but not least this entire exploit is easily preventable with a single change to the contract:

Verify with the factory that msg.sender is a valid pool

I think at this point I believe I have adequately proved this is an medium severity issue according to Sherlock criteria. Since it is not only possible (even more so in the future) but also profitable, causing massive losses to users. IMO the discussion here should be whether this is a medium or high risk issue, not between medium and low.

[nevillehuang]

I was initially skeptical of this finding too, due to the large computing power required for the attack. But given how easy the fix is, and the potential positive profit margin ever increasing for say a high TVL pool, this should be a valid M given sherlock's rule here:

3. A material loss of funds, no/minimal profit for the attacker at a considerable cost

[Trumpero]

Respectfully, here is my final statement for this issue:

I believe this issue is only have impact in the far future. Using the Bitcoin network's computing power to estimate this issue amplifies the hypothesis for exploitation and doesn't make sense, since the power of the Bitcoin network is much higher than that of the most powerful supercomputers in the world. The current hashrate of Bitcoin is 449.64 EH/s (4.49e20), while the total hashrate of the top 10 supercomputers in the world is less than 2000 TH/s (2e15)
(I used the latest statistics from the top500 website for supercomputers to compute the hashrate https://www.top500.org/lists/top500/2023/06/
and used the approximate conversion from FPlops to hashrate from there
https://www.quora.com/How-do-you-convert-m-flop-s-to-hash-s
https://bitcointalk.org/index.php?topic=52303.0)

Therefore, if the Bitcoin network needs 2 hours to generate address collisions, a combination of the top 10 supercomputers would need more than 400,000 hours to exploit it, even though these supercomputers are massively expensive and complex. Any supercomputer always requires a very high and unreal cost for attacker, but its power is still insufficient to exploit this issue. A supercomputer is the most powerful option that attacker can obtain, and it even nearly impossible for attacker to access the most powerful supercomputers in the world. Therefore, I believe it is impossible and unprofitable for attackers to exploit this in the next few years (maybe few decades), as using Bitcoin's computing power amplifies the hypothesis for exploitation.

This issue should be an informational issue in my opinion. However, I will leave it to Sherlock team to make the final decision and will respect the final result.

[jkoppel]

Comparing the hashrate of the top supercomputers to that of the Bitcoin network is like comparing the carrying capacity of a humanoid robot to that of a container ship. Yes, all the humanoid robots in the world might not be able to carry as much as a single container on a container ship, but that doesn't mean shipping a single container overseas is prohibitively expensive.

It may be true that the supercomputers combined only have 2000 TH/s. But anyone can beat that by spending $30k on Antminers. https://koinly.io/blog/best-crypto-mining-hardware/

[T1MOH593]

As I understand, all the calculations above state that any random collision is found. However not every address gives approval to router in this specific protocol. Probability that collisionned address has given approval to KyberSwap Router must be also applied. What set of addresses can give approve to KyberSwap among all possible addresses - computation above assumes that all the existing, which is obviously incorrect. If take 1e9 among 2^256 possible (or 2^160, not sure) - above calculation is far from reality.
Am I wrong?

[jkoppel]

@T1MOH593 Yes, you are wrong. The collision needs to be between (a) the address of a pool using some currency, and (b) any EOA controlled by the attacker. Once this collision is found, the attacker has the ability to steal all approvals to the router using that currency.

[T1MOH593]

@jkoppel Computation above states that 2^80 number of tries needed to find collision with probability 50%. However this computation states that collision between any a) evm address and b) any EOA will be found. However a) must be restricted to "(a) the address of a pool using some currency".
This condition complicates calculations, because set of satisfied addresses reduces from 2^160 to subset of KyberSwap pools

I really appreciate if someone corrects me

[jkoppel]

@T1MOH593 I don't know where you're getting that from, so it's hard for me to give a response more constructive than "read the Router code and understand how a collision between an arbitrary attacker-controlled EOA and an arbitrary pool with a fixed currency allows major theft."

Then if you can iterate through 2^80 addresses for KyberSwap pools all of which use currency A, and 2^80 random EOA addresses, you have a large collision probability.

[T1MOH593]

My bad, you're right. Take a look on Router code helped
Thanks for explanation, I expected I was wrong

[hrishibhat]

Result:
Medium
Unique
Based on all the information from the comments above and discussing further with various parties, this issue seems to be a serious issue and while the timeline is unclear but depends on the computational power available and other factors mentioned above. Its possibility is likely in the near future from hours to days to months to years and may not be a hypothetical scenario anymore.

While Sherlock understands the details of this particular issue may evolve in the future, from the perspective of this contest given that the protocol can still fix this, considering this issue a valid medium.

Note: Given the nature of this issue, and the possibility of more information surfacing on the same, this issue must be referred to for future contests only under matching scenarios, and would advice against drawing conclusions/interpretations inspired by this issue on any of the future issues.
Also currently the rulebook does not have a fixed timeline within which the issue must occur. This will be discussed further and added to the rule.

[sherlock-admin2]

Escalations have been resolved successfully!

Escalation status:

• IAm0x52: accepted

[c14sh]

Great discussion!
@IAm0x52 Is the PoC written by zobront? or is it that 0x52 == zobront?

[c14sh]

Great discussion! @IAm0x52 Is the PoC written by zobront? or is it that 0x52 == zobront?

Seems the PoC is finding the first hash of 256 hashes in 24bit space, not collision. Surely, the answer is 2^24/256 = 65536 in average from probabilistic perspective.

[manhlx3006]

[Will fix in the upcoming version of the protocol]

Thanks for all provided information and explanation. We understand the risk of the issue.

Given the fact that the timeline is unclear and depends on many factors, as well as the Factory has been deployed on all supported networks (which can not have logics of storing the list deployed pools), we will put this fix into our in-progress and up-coming protocol.

For the Router contract, since it is used mostly by developers (as we are an Aggregator and users interact with another Router instead of this one), we will put a notice into our docs and advice developers to be careful when approving token allowances to this Router contract, and the new fix will also be added into the upcoming version, and adjust the Router logic accordingly.

In the mean time, we are analyzing the potential risks as well as the likelihood of the issue (computation power, expenses, etc).

Thanks all.