Address Collisions: A Birthday Paradox?

How likely is an address collision attack to succeed? This question sparked debate in audit competitions a few years ago. Some reports used the birthday paradox to estimate the probability, but the calculation overlooked a subtle distinction. In this post, we revisit the attack scenario and explain how that distinction changes the probability of success.

We begin with the address-collision attack that motivated EIP-3607, then examine an attack that remains possible after the EIP and clarify how its collision probability differs from the classic birthday problem.

Address collisions before EIP-3607

Before EIP-3607, an attacker could exploit a collision between an EOA address they controlled and a contract address at which they could deploy code. The attacker could generate candidate EOA addresses by sampling private keys and candidate contract addresses by varying, for example, a CREATE2 salt. Once they found a match, they could deploy the contract (e.g., a prewritten DEX), let it collect enough ERC-20 approvals, and later use the hidden private key to sweep the funds via ERC-20 transferFrom.

EIP-3607 blocks this attack by rejecting transactions originating from an ordinary deployed contract account, even if someone knows a private key matching its address. The proposal backs this concern with an estimated cost of roughly $2^{80}$ computational operations to find such a collision.

Collision attacks after EIP-3607

However, EIP-3607 does not prevent an attacker from using an EOA whose address matches that of an undeployed contract. Consider the router implementation reviewed in the 2023 KyberSwap contest:

function swapCallback(
    int256 deltaQty0,
    int256 deltaQty1,
    bytes calldata data
) external override {
    require(deltaQty0 > 0 || deltaQty1 > 0, 'Router: invalid delta qties');
    SwapCallbackData memory swapData = abi.decode(data, (SwapCallbackData));
    (address tokenIn, address tokenOut, uint24 fee) = swapData.path.decodeFirstPool();
    require(
        msg.sender == address(_getPool(tokenIn, tokenOut, fee)),
        'Router: invalid callback sender'
    );

    // token transfer logic ...
}

Here, _getPool computes a pool address by hashing inputs including tokenIn, tokenOut, and fee. It does not check whether the factory has actually deployed the pool. An attacker can therefore generate two sets of addresses: one from EOA private keys and another from different combinations of tokens and fees, searching for a match. For example, they can fix tokenIn to USDC and vary tokenOut and fee. Once they find a matching private key, they can drain the USDC users have authorized the router to spend.

The KyberSwap contest report applies the classic birthday formula to estimate the attack’s success probability. With $2^{80}$ EOA addresses and $2^{80}$ candidate pool addresses, it treats the combined $2^{81}$ addresses as a single group and reports a collision probability of approximately 86.4%. The same probability calculation also appears in the Napier contest discussion.

However, these estimates count any collision among the generated addresses, including collisions within either group. The attack requires a collision between the two groups.

What is the birthday paradox?

The classic birthday problem asks:

How many people do we need for two of them to share a birthday?

For $k$ independent, uniformly random draws from $N$ possible values, in the birthday regime where $k=O(\sqrt{N})$, the standard birthday approximation gives

$$P(\text{non-collision}) \approx e^{-k^2/(2N)}.$$

Taking $N=2^{160}$ and $k=2\sqrt{N}=2^{81}$, as in the KyberSwap discussion, gives a collision probability of approximately $1-e^{-2}\approx86.47\%$. This is the calculation behind the report’s estimate.

What is different here?

The difference is that we are drawing from two random sources: private key generation and smart contract address generation. We should therefore ask the following question:

We draw two groups of numbers independently and uniformly at random from $1, \ldots, N$, with $m$ samples in each group, allowing repeated values. How likely is a collision between the two groups? The probability is lower than in the classic birthday problem with $k=2m$, since collisions within each group do not count. But how much lower? Can we quantify it?

One might expect the collision probability to be halved, since roughly half of all pairs contain one sample from each group. However, halving the number of relevant pairs does not generally halve the probability of finding at least one collision.

To simplify the calculation, we consider the complementary event: no collision occurs between the two groups. Subtracting its probability from 1 gives the cross-group collision probability.

Each cross-group pair avoids a collision with probability $1-1/N$. With $m$ samples in each group, there are $m^2$ such pairs. If collisions for different cross-group pairs were mutually independent, the probability of no cross-group collision would be $(1-1/N)^{m^2}$.

For $m=\lfloor\sqrt{N}\rfloor$, this expression tends to $e^{-1}$ as $N\to\infty$, by the standard limit $(1-1/N)^N\to e^{-1}$. The collision events are not mutually independent, so the expression is not exact. Nevertheless, the actual probability has the same limit. We omit the proof here.

The collision probability is therefore approximately $1-e^{-1}\approx63.2\%$, rather than the reported $86.4\%$.

More generally, when $m$ and $k$ are on the order of $\sqrt{N}$, comparing the cross-group approximation $1-e^{-m^2/N}$ with the classic birthday approximation $1-e^{-k^2/(2N)}$ shows that equal collision probabilities require

$$\frac{m^2}{N} = \frac{k^2}{2N}, \qquad\text{i.e. } 2m = \sqrt{2}\,k.$$

Thus, with equally sized groups, the two group problem requires approximately $\sqrt{2}\approx1.41$ times as many total samples to achieve the same collision probability.

In practice, generating an address may cost different amounts of computation on the two sides, for example, when one side generates EOA addresses and the other computes CREATE2 addresses, or when the two computations require different numbers of Keccak evaluations. An unequal allocation of samples may therefore be more efficient under a fixed computational budget.

With approximately $x\sqrt{N}$ samples in one group and $y\sqrt{N}$ in the other, where $x,y>0$ are fixed, the cross-group collision probability approaches $1-e^{-xy}$ as $N$ grows. For a fixed total number of samples, meaning a fixed $x+y$, this probability is maximized when $x=y$.

For example, groups of sizes $0.5\sqrt{N}$ and $1.5\sqrt{N}$ give a collision probability of approximately $1-e^{-0.75}\approx52.8\%$, compared with $63.2\%$ for two equally sized groups with the same total number of samples. This widens the gap with the classic birthday estimate, as it would still predict a collision probability of $86.47\%$ for the same total number of samples.

Conclusion

In this post, we examined cross group address collisions in attacks that remain possible after EIP-3607, and explained why the classic birthday formula overestimates their success probability.

Although finding such collisions remains computationally demanding, the potential rewards can be substantial. For instance, the same callback validation pattern also appears in Uniswap V3’s SwapRouter. Improvements in hardware may lower attack costs, while more approved funds could increase the value at risk. Understanding the correct probability model is therefore essential to assessing the attack’s feasibility and economic incentives.