# 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?

## 2 Answers

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.

From your first link:

To create a binary seed from the mnemonic, we use the PBKDF2 function with a mnemonic sentence (in UTF-8 NFKD) used as the password and the string "mnemonic" + passphrase (again in UTF-8 NFKD) used as the salt. The iteration count is set to 2048 and HMAC-SHA512 is used as the pseudo-random function. The length of the derived key is 512 bits (= 64 bytes).

So it isn't simply a string of 12 words, they are also using a hash function to derive the key from those words.

Even if it was a simple string of words, you'd need to run through 10788914613853470623442441579 iterations per millisecond for a whole year to get through all the possibilities for 128 bits.

• The entropy is 128 bits. According to the proposal, the last 4 bits are a checksum. Dec 9, 2020 at 14:45