Arabadzhiev - The pool verification in `NapierRouter` is prone to collision attacks

[sherlock-admin]

Arabadzhiev

medium

The pool verification in NapierRouter is prone to collision attacks

Summary

Using computed pool addresses to verify the callback function callers is collision attack prone and can be abused in order to steal all token allowances of the NapierRouter contract

Vulnerability Detail

With the current state of the NapierRouter contract implementation, both the mintCallback and swapCallback use the _verifyCallback function in order to verify that the address that called them is a Napier pool deployed by the PoolFactory attached to the router. This is done by computing the Create2 pool address using the basePool and underlying values passed in to either of the callbacks as arguments and the comparing that address to the msg.sender.

However, this method of verifying the caller address is collision prone, as the computation of the Create2 address is done by truncating a 256 bit keccak256 hash to 160 bits, meaning that for each address there are 2^96 possible hashes that will result in it after being truncated. Furthermore, what this means is that if a basePool and underlying combination that results in an address controlled by a malicious user is found, all token allowances given to the NapierRouter contract can be stolen.

In this article and this report from a past Sherlock contest, it is shown that this vulnerability will likely cost a few million dollars as of today, but due to the rapid advancement in computing capabilities, it is likely that it will cost much less a few years down the line.

Impact

All token allowances of the NapierRouter can be stolen

Code Snippet

NapierRouter.sol#L65-L68

Tool used

Manual Review

Recommendation

In the PoolFactory contract, create a function that verifies that a given pool address has been deployed by it using the _pools mapping. Example implementation:

contract PoolFactory is IPoolFactory, Ownable2Step {
    ...
    /// @notice Mapping of NapierPool to PoolAssets
    mapping(address => PoolAssets) internal _pools;
    ...
+   function isFactoryDeployedPool(address poolAddress) external view returns (bool) {
+       PoolAssets memory poolAssets = _pools[poolAddress];
+       return (
+           poolAssets.basePool != address(0) &&
+           poolAssets.underlying != address(0) &&
+           poolAssets.principalTokens.length != 0
+       );
    }
}

And then use it in the NapierRouter::_verifyCallback function in place of the computed address comparison logic:

    function _verifyCallback(address basePool, address underlying) internal view {
-       if (
-           PoolAddress.computeAddress(basePool, underlying, POOL_CREATION_HASH, address(factory))
-               != INapierPool(msg.sender)
-       ) revert Errors.RouterCallbackNotNapierPool();
+       if (factory.isFactoryDeployedPool(msg.sender)) revert Errors.RouterCallbackNotNapierPool();
    }

[sherlock-admin4]

Escalate

Invalid. Both the mentioned report requires only 2^80 computation to find a collision hash because of the birthday paradox. In this issue, the attacker needs approx 2^160 computation to find the exact match with the specific napier pool deployed.

You've deleted an escalation for this issue.

[Arabadzhiew]

Escalate

Invalid. Both the mentioned report requires only 2^80 computation to find a collision hash because of the birthday paradox. In this issue, the attacker needs approx 2^160 computation to find the exact match with the specific napier pool deployed.

How exactly did you come to that conclusion? The goal of this exploit is not to find a match with a specific Napier pool, but instead a match with an EOA controlled by the attacker. The case is the same in the mentioned report. If anything, in the case of the NapierRouter the collision would be theoretically more likely to happen, since here we have two address arguments (320 bits) that can be played with when trying to find а collision, while in the Kyberswap issue there is an address + uint24 (184 bits).

[Coareal]

How exactly did you come to that conclusion? The goal of this exploit is not to find a match with a specific Napier pool, but instead a match with an EOA controlled by the attacker. The case is the same in the mentioned report. If anything, in the case of the NapierRouter the collision would be theoretically more likely to happen, since here we have two address arguments (320 bits) that can be played with when trying to find а collision, while in the Kyberswap issue there is an address + uint24 (184 bits).

Removed escalation. Agree that issue is similar to Kyberswap's.

[nevillehuang]

Escalate

How would the allowances be stolen here? Wouldn’t a user be only approving specified PT amounts wherein every swap will consume the approval, thus making this attack not profitable?

Additionally, This issue seems to lack a further description/explanation of the attack vector specific to napier as opposed to the linked issue:

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.

Perhaps the watsons @Arabadzhiew @xiaoming9090 can clarify better

[sherlock-admin2]

Escalate

How would the allowances be stolen here? Wouldn’t a user be only approving specified PT amounts wherein every swap will consume the approval, thus making this attack not profitable?

Additionally, This issue seems to lack a further description/explanation of the attack vector specific to napier as opposed to the linked issue:

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.

Perhaps the watsons @Arabadzhiew @xiaoming9090 can clarify better

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.

[Arabadzhiew]

Escalate

How would the allowances be stolen here? Wouldn’t a user be only approving specified PT amounts wherein every swap will consume the approval, thus making this attack not profitable?

Additionally, This issue seems to lack a further description/explanation of the attack vector specific to napier as opposed to the linked issue:

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.

Perhaps the watsons @Arabadzhiew @xiaoming9090 can clarify better

Most of the users that will perform more than 1 swap with a specific token using the router will simply give max approval to it. This is because:

1. It saves gas by not having to make a separate approve call for each swap;
2. By default, this is what you are prompted to do by Metamask when you are required to give token allowance to some dapp;

Additionally, I have only given a high level overview of the issue, since it is very similar to the one reported in the Kyberswap contest, and I thought that a more in-depth explanation would simply be redundant. But since you are asking about it, I'm going to provide a short explanation on one of the ways of how this vulnerability can be exploited in the context of Napier:

Taking the NapierRouter::swapCallback function:

    function swapCallback(int256 underlyingDelta, int256 ptDelta, bytes calldata data) external override {
        // `data` is encoded as follows:
        // [0x00: 0x20] CallbackType (uint8)
        // [0x20: 0x40] Underlying (address)
        // [0x40: 0x60] BasePool (address)
        // [0x60:  ~  ] Custom data (based on CallbackType)
        (address underlying, address basePool) = abi.decode(data[0x20:0x60], (address, address));
        _verifyCallback(basePool, underlying);

        CallbackType _type = CallbackDataTypes.getCallbackType(data);

        if (_type == CallbackType.SwapPtForUnderlying) {
            CallbackDataTypes.SwapPtForUnderlyingData memory params =
                abi.decode(data[0x60:], (CallbackDataTypes.SwapPtForUnderlyingData));
            params.pt.safeTransferFrom(params.payer, msg.sender, uint256(-ptDelta));
        ...
    }

As it can be seen in this snippet, the basePool and underlying values are only used for the pool address verification. Furthermore, we can see that in the first if block of the function there is a single safeTransferFrom call that sends a concrete amount of a concrete token from a concrete address to the msg.sender. All the values in bold are passed in as function arguments and are not used for the CREATE2 pool address computation. What we can conclude from this is that if someone manages to find a combination of basePool and underlying that passes the _verifyCallback check for their EOA, then they can easily steal all of the token allowances given to the router contract.

[0xMR0]

msg.sender is already being validated as napier pool address.

    /// @dev Revert if `msg.sender` is not a Napier pool.
    function _verifyCallback(address basePool, address underlying) internal view {
        if (
            PoolAddress.computeAddress(basePool, underlying, POOL_CREATION_HASH, address(factory))
                != INapierPool(msg.sender)
        ) revert Errors.RouterCallbackNotNapierPool();
    }

It would revert for non-existent napier pool address. How the recommendation is different from the above check?

[Arabadzhiew]

@0xMR0 Quoting what is stated in my report:

However, this method of verifying the caller address is collision prone, as the computation of the Create2 address is done by truncating a 256 bit keccak256 hash to 160 bits, meaning that for each address there are 2^96 possible hashes that will result in it after being truncated. Furthermore, what this means is that if a basePool and underlying combination that results in an address controlled by a malicious user is found, all token allowances given to the NapierRouter contract can be stolen.

Additionally, the recommendation is different from the current approach of verification in that, it will verify whether the msg.sender is a legit Nepier pool by checking that it was deployed by the PoolFactory rather than comparing it to a computed Create2 address, which is collision prone.

Please read the full report and the resources attached to it in order to gain a deeper understanding of the vulnerability in question.

[massun-onibakuchi]

I think CREATE2 with Factory pattern can be found in well-known UniswapV3, and I believe Uniswap v3 don't need to fix it because the issue seems to be 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

Also, the attack cost makes a strong external condition, which requires a very big upfront cost with no certainty on pay out as attacker.

[nevillehuang]

To keep consistency of results, I think this issue should remain valid, but I am keeping my escalation up for @Czar102 to revisit this type of issues. I believe based on sponsor comments here and the assumption that all users make max approvals towards the router, this type of issues should have a better sherlock rule catering to this and/or make known to sponsors to be aware as a known accepted risk.

[Arabadzhiew]

The reason why such a vulnerability has not been exploited in the wild yet is that as @massun-onibakuchi mentioned, the attack requires a big upfront cost as of today. However, given the fact that NapierRouter is an immutable contract and taking into consideration the rapid advancement of computing capabilities (the Bitcoin hashrate alone has almost doubled since the Kyberswap issue was reported - it has raised from 4.71e20 to 7.68e20), we can see how this exploit might become much more profitable and very realistically feasible in the not so distant future. And as of now, the Sherlock rulebook does not have a fixed timeline within which an issue must occur, in order for it to be considered valid.

Also, the allowances that are going to be given to the contract are not an assumption, but rather a "fact of life" for such kind of contracts. Pretty much all DEX router contracts have token allowances in the magnitudes of millions of dollars. And that is because understandably, nobody wants to pay extra gas fees when possible.

On a final note, in the particular case of the NapierRouter all token allowances given to it can be stolen with a single address collision, while in the case of the Kyberswap issue, a separate collision has to be found for each token. That is because the CREATE2 addresses of the Napier pools are not computed based on all token addresses used within them.

I will refrain from commenting on this issue any further. I believe that enough has been said in order for the Head of Judging to be able to make an informed decision.

[xiaoming9090]

A note to the judges. The risk profile of this issue is the same as the Arcadia's Contest (https://github.com/sherlock-audit/2023-12-arcadia-judging/issues/59). Thus, the risk rating of this issue should be aligned for consistency. Thanks.

[cvetanovv]

This issue should remain Medium. The report is similar to the Arcadia contest from a few weeks ago. It wouldn't be fair for it to be Low here. However, I suggest that Sherlock include it in the documentation as a known issue in the future.

[Czar102]

To exploit this, an attacker would need to find a collision between an owned address and a potentially deployed pool (if there is less than 10^12 pools deployed then the attack is definitely unfeasible). So, the attacker needs to make the owner deploy a pool. The attacker needs to be the owner.

The issue by itself is a borderline Med/Low, so I believe, considering this additional constraint needed to execute it, this issue should be of Low severity.

Please correct me if I'm understanding something wrongly.

[Arabadzhiew]

@Czar102 There doesn't have to be a deployed pool at the given address. The goal of the exploit is to find a combination of the basePool and underlying values that results in an address that is equal to an EOA controlled by the malicious user. Then, that user will be able to call any one of the two callbacks through that EOA and steal the token allowances given to the router contract.

[Czar102]

@Arabadzhiew indeed, thank you for correcting me!

I'm planning to reject the escalation and leave this a valid Medium severity issue.

[Czar102]

On second thoughts, @Arabadzhiew can you elaborate how much computation needs to be done having ~2^50 memory available?

If an algorithm for finding this collision is not provided, I'm planning to invalidate this finding, similarly to findings that do not describe the algorithm in the future. (full feasibility analysis should have been done)

[Arabadzhiew]

Using the so-called "naive" collision finding algorithm, which is the one in question in all of the resources I have attached to my report requires at least 2^80 of storage available. And because that is an enormous amount as of today's standards, this is the biggest bottleneck of this exploit. What this essentially means is that with 2^50 of memory, the exploit will be practically impossible to execute using this algorithm.

To show how much more computation will have to be made with this amount of memory, let's look at some math. I'm going to use the following formula to calculate the hash collision probabilities:

$$ k^2 \over 2N $$

Where k is the number of computed hashes and N is the total number of possible hashes (2^160 in our case).

You can read more about it here, but essentially, it is a very simplified version of a more complex hash collision probability formula, that works well with very big numbers. This is the least accurate formula from all of the mentioned ones in the article, but it is the only one that will return a probability value that is different from 0 with such a low k value being passed in to it.

So for the scenario where we have 2^50 of memory available, we will first generate 2^50 public addresses, store those in our memory and then compute another set of 2^50 different pool addresses (by using different basePool and underlying values for each one). In that case, we will have k = 2^51. The output that we will get for this value from the above formula is the following: 1.7347235e-18 - a very small decimal value. This is our probability value between 0 and 1, where 0 = 0% probability and 1 = 100% probability. So to get how many times we will have to make 2^50 computations in order to have ~100% probability of collision, we have to divide 1 by that value. This results in the following value: 5.7646075e+17 which is exactly equal to 2^59. What we can derive from that is that to have approximately 100% probability of finding a collision in a 160 bit space, with only 2^50 of memory available, we will have to perform *2^50 2^59 = 2^109 computations. Obviously, this is a massive amount of computations. To put into perspective how big it actually is, if we had the full Bitcoin computation power at the hashrate of 7.68e20, it would take us 26797.9 years** to make this many computations.

On the other hand though, if we had 2^80 of memory available, then the probability values will look completely differently. We will perform the exact same procedure as above, but this time we will generate two sets of 2^80 addresses. So our value of k will be equal to 2^81 this time around. And because that value is much bigger than 2^51, it allows us to use the other more accurate formulas. I will be using the following formula for this probability calculation, which is simply a more accurate version of the one used above:

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

The output that we get from that formula is 0.86466471676 which represents ~86.46% chance of collision for the computation of 2^81 addresses. That is much better than than the previous example. And if we bump up our computations to 2^82, then we will get 0.99966453737 as an output, which represents ~99.96 chance of collision for that many computations. And for the sake of comparison, 2^81 computations can be performed in 0.87 hours by the Bitcoin network at the hashrate of 7.68e20 and 2^82 in 1.74 hours.

On a final note, I'd like to mention once again that this is the simplest form of a hash collision finding algorithm, which does not make use of any memory saving optimizations. There are potential ways to bring down the amount of memory required for performing it, such as using bloom filters as mentioned in this comment under the Kyberswap issue, so I'm sure that with time we will see more and more feasible implementations of that algorithm.

@Czar102 I hope this clarifies things further.

[Czar102]

On a final note, I'd like to mention once again that this is the simplest form of a hash collision finding algorithm, which does not make use of any memory saving optimizations. There are potential ways to bring down the amount of memory required for performing it, such as using bloom filters as mentioned in this comment under the Kyberswap issue, so I'm sure that with time we will see more and more feasible implementations of that algorithm.

Unless these optimizations are shared, I believe address collision to be a non-issue. Bloom filter can optimize storage down to 1 bit, but I don't think it's possible to go much further based on information-theoretic limitations: when a function $f: \;\mathbb{B}^{20}\rightarrow \{ 0, 1\}$ (describing whether a hash was already yielded) has at most $2^{2^{50}}$ configurations, the "expected value of information" about any random hash can't be larger than $2^{-110}$, even with fractional information (probabilistic approaches).

Of course, my rough understanding may be wrong, so I'm open to having my mind changed. For now, this attack seems to be impossible to carry out. Hence, I'm planning to invalidate this finding.

[midori-fuse]

As the submitter of the same issue in Arcadia, this conversation has been quite helpful, and we'd like to share our thoughts.

When we investigated the issue in Arcadia, we only really thought of the time complexity of $O(2^{N/2})$, which is possible, but not the memory complexity, which is indeed impossible as of now. The head of judging's question made us realize the additional constraint, and we apologize for not realizing it earlier during the Arcadia contest.

However, as the head of judging stated himself in the Sherlock discord, I do believe the continuous development of available resources and what's at stake makes this issue worth mitigating. This is the kind of issue that's of critical impact if were to happen, and while it's impossible as of now, there's no telling when it will be possible in the future.

Hence, while I believe this issue is true, I don't have opinions about its severity. What I would consider is what are the odds it becomes realistic in the lifetime of this protocol, not just at this current moment.

• In other words we're betting on how much can the storage problem can be solved, and how much funds are still at stake by then. This is also one of the discussion points from the Kyber issue.

I do believe, however, that it's the responsibility of the issue author to outline the constraints related to the attack, and these kind of issues will likely need a revisit in the future given technological advancements.

[Arabadzhiew]

After doing some further research on the topic, I came across this paper, which describes a much more sophisticated collision finding algorithm. It requires 160 Terabytes (~2^47) of memory and 2^92 computations. Now, in my eyes, this looks like a much more feasible implementation. The number of computations is quite a bit higher, but it is still well within the realm of feasibility. Using the analogy that I've used above, the Bitcoin network will need ~0.2 years at the hashrate of 7.68e20 to make that many computations.

The thing is, if someone decides to try and perform this exploit in the future, they won't be targeting a single protocol. They will be targeting as much protocols as they possibly can. So the more protocols there are with this vulnerability in them, the more likely it will be that this gets exploited.

[Czar102]

The thing is, if someone decides to try and perform this exploit in the future, they won't be targeting a single protocol. They will be targeting as much protocols as they possibly can. So the more protocols there are with this vulnerability in them, the more likely it will be that this gets exploited.

I don't think that's true given the memory complexity of this attack.

Nevertheless, the linked paper does present a way to optimize the memory complexity beyond the approach outlined in the previous comments. 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 of 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 the current prices. This, of course, doesn't take into account the fact that keccak256 mining is a niche field, so the extent of cost optimization is much worse.

I'd also like @midori-fuse to sign off on my reasoning – would you agree that it's possible to execute this attack?

I think this finding was correctly judged as a Medium severity one.

[midori-fuse]

This is a really cool algorithm. Massive kudos to @Arabadzhiew for finding this paper.

Indeed that 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 = \frac{1}{\theta} = 2^{40}$ and achieve the same execution time, but with $\sim 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. Taking technological advancements into consideration, the computing power here does not have to be solely keccak256 mining, but also overall processor improvements as well.

[nevillehuang]

Maybe off topic and not relevant to finding but Curious why nobody tried to exploit uniswapv3

[Czar102]

@nevillehuang probably because you would need to create your own ASIC just for this (millions) or pay a quarter billion dollars for many, many GPU-hours.

[nevillehuang]

@Czar102 Surely its worth it for say a 400+ million USDC/ETH univ3 pool right?

[Czar102]

Result: Medium Unique

[sherlock-admin4]

Escalations have been resolved successfully!

Escalation status:

• nevillehuang: rejected