# Recovery Passphrase Collission for BIP-39 and BIP-44

Referring to the standards of [BIP-39] and [BIP-44]: a 'master password' consisting of 12 words uniformly selected from a 2048-word dictionary corresponds to 128 bits of entropy, that is then used as a seed for the generation of keypairs in many wallet implementations.

While not contesting the sufficiency of the offered security, what stops an attacker from iterating over such seeds just to check balances on other's wallets? What would the threat scenario/attacker model be called?

128-bit entropy simply means that we have $$2^{128}$$ different values to search, which is similar to 128-bit security. For a single target that is impossible since even the collaborative powers of Bitcoin Miners can reach $$\approx 2^{92}$$ in a year. Therefore one needs $$2^{35}$$ years to find the correct password. The iteration of PBKDF2 is 2048 so, we need to multiply $$2^{35}$$ with $$2^{11}$$ that makes $$2^{46}$$ years if we assume that SHA2d running time is equal to PBKDF2.

In the case of finding multi-password attack, with parallel versions of Oechslin's rainbow tables, the expected cost of finding a password from $$t$$ targets is $$2^{128}/t$$. Now assume that you have a billion of targets. Then, you will be able to find the first password much lower than 128-bit security. The cost would be below $$2^{100}$$ and the time would be below $$2^{70}$$. This can be achievable with supercomputers.

Conclusion: Using 128-bit entropy is not secure in multi-target attack case. The users should concentrate on password settings with 256-bit entropy.

Note 1: The title includes the word collision, however, a collision has nothing to do with finding a password of a user. A collision is finding two pairs of passwords such that after PBKDF2 is applied the result will be the same. This has cost $$2^{64}$$ with 50% probability of success. The pre-image attack is the attack for passwords with a cost of $$2^{128}$$ is the setup of the question.

Note 2: A detailed entropy calculations of Bip39 in this answer.

• Do you have a reference for the total powers of bitcoin miners in a year (2^92). Is this somehow deduced from the hashrate in TH/s ? May 2, 2021 at 8:28
• @Avatar33 you can find in this answer and edit to see the formula. May 2, 2021 at 8:30

The thing that stops the attacker iterating through all possibilities is time.