2
$\begingroup$

According to https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki#From_mnemonic_to_seed

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).

Given that we know the 24-word mnemonic seed, what is the amount of characters that I should choose for my password such that it's very hard to guess with a very fast super computer? Or better, how many permutations should be enough so it's safe?

$\endgroup$
7
  • $\begingroup$ What is your target security? Can we call this a dupe to your question Is using 7-8 random words from all words of a language as password a good idea?. If not, please indicate. $\endgroup$
    – kelalaka
    Nov 8, 2021 at 22:51
  • $\begingroup$ Any contemporary advice to use PBKDF2 for password hashing is incompetent or geared towards making the system breakable. When combined with "The iteration count is set to 2048", that's a provocation against common sense! Guess how I classify that advice, in light of precedents like DES key size and Dual_EC_DRBG. $\endgroup$
    – fgrieu
    Nov 9, 2021 at 7:38
  • $\begingroup$ @fgrieu I guess, they use PBKDF2 only to combine a password and to output a binary seed to be used in secp256k1. Not for security. They already say a minumum 128-bit entropy is allowed. The OP must use 256 to achieve 2560bit entropy since the Grover. $\endgroup$
    – kelalaka
    Nov 9, 2021 at 17:55
  • $\begingroup$ @kelalaka: The question asks how to choose a password, with the intent that it protects a private key. The question assumes "that we know the 24-word mnemonic seed", and the public key is to be assumed known. With that, isn't each password testable with about 2048 SHA-512 and one point multiplication on secp256k1? If so, I can't condone that little entropy-stretching. That's a highway for password crackers. $\endgroup$
    – fgrieu
    Nov 9, 2021 at 19:57
  • $\begingroup$ @fgrieu mnemonic is not public . passpharase can be used for plausible deniability in the case for the mnemonic words are determined. Then again one needs around 256-bit entropy. Also, as you can see on the link of OP, it can be empty. Maybe, OP asking, given the attackers know the 24-words,... $\endgroup$
    – kelalaka
    Nov 9, 2021 at 20:11

1 Answer 1

1
$\begingroup$

The private and public key in ECC

To create a public key in 256-bit ECC ( Bitcoin uses secp256k1) one needs uniform random 256-bit to produce a secret key $k$ (256-bit number) and publishes $[k]G$, i.e. scalar multiplication with base point $G$ and this is protected by the discrete logarithm problem on the ECC and if the curve group is generic than the best-known attack has the cost of $2^{128}$. Keep in mind that once a Cryptographic Quantum Computer is built, the Shor's algorithm when applied to the DLog, the security is gone!

Random passwords not hard remember use Dicewire xkcd936

Humans hard to remember random 64 hexes, so researchers invented dicewire, and Bip39 is similar to it. In Bip39, instead of remembering the 64 hexes, once rolls random numbers, probably by tossing a fair coin, or getting from /dev/urandom to select words from the word list of Bip39. Is well known that 24-word creates around 256-bit entropy.

The selected words are not public and keep them secret all the time.

Now we may consider the usage of the passphrase as

  • To achieveplausible deniability
  • To increase the randomness where the random source for generating 24-word mnemonic is not reliable as one hopes, and
  • Use the mnemonic seed as the source of entropy and protect it with a passphrase.

If we read the question as,

Given that attackers (not we) know the 24-word mnemonic seed, what is the amount of characters that I should choose for my password such that it's very hard to guess with a very fast super computer? Or better, how many permutations should be enough so it's safe?

So we assume the 24-word mnemonic word is not secured properly.

First of all, the repo is around 8 years old (created_at": "2013-11-19T17:18:41Z ) older than the latest password hashing competition held in 2015. It is normal for them to mention PBKDF2, not Argon2. It seems this document is not updated for today's needs! But it is not normal to suggest iteration 2048 and there were still better candidates at that time.

  • Bcrypt 1999 - iteration, no memory hardness
  • PBKDF2 2000 - iteration, no memory hardness
  • Scrypt 2009 - iteration, have memory hardness
  • Argon2 2015 - iteration, have memory hardness and have counter to parallelization.

Firstly, don't use characters, again use Bip39 or dicewire to generate the passphrase. So, with 12 words one can reach around 128-bit entropy, and this even with a simple hash like SHA1 or SHA256 instead of PBKDF2 or Argon2, is secure enough from the Summit and Collective power of the BitCoin Miners where the Miner once reached $\approx 2^{92.09}$ SHA256d per year on 7 February 2021. If we assume this is your target security for your password, then for PBKDF2

  • use iteration like 1M so that you can reduce the collective power to $\approx 2^{70}$ and reduce the Summit to around $~2^{50}$*. The nice thing about this iteration is adjustable according to your need. ( One can use the benchmark of the Hashcat on NVidia RTX 3090 to adjust the target security according to the supercomputer that holds many RTXs instead of the collective power of miners).

    The 12-word mnemonic will be far safe for Summit, 6-word Bip39 will have overcome its power. however, we have better alternatives, even then and now - Scrypt and Argon2!

Use Argon2 whenever possible

Today the bitcoin miners extensively use ASICs and GPUs to massively parallelize the mining process. Now, we have Argon2 like mechanisms against them

  • Adjustable memory so that ASIC and GPU search power is reduced. Even on PCs, and not that the memory usage timing can be exploited.

  • Adjustable parallelism so that the core of CPUs cannot be completely run in parallel instances.

  • And, again the iteration count to reduce the single search timing.

    Argon2 parameters must the measured before deciding, and still 12-word mnemonic will be quite safe for Argon2. We can say still the 6-word Bip39 will be safe against the Summit.

Or better, how many permutations should be enough so it's safe?

Reading this as the permutation of the 24 words. Then we have 24! and by using the String's Approximation Formula $$n! \sim \sqrt{2 \pi n}\left(\frac{n}{e}\right)^n$$ then setting $n=24$

$$24! \sim \sqrt{2 \pi 24}\left(\frac{24}{e}\right)^{24} \sim 6.2\mathrm{e}{+23} \sim 2^{80}$$

This is quite good (approximately 8-word Bip39), however, keep in mind that, if the attacker knows the 24-word mnemonic, then the entropy of the derived key $k$ together with the passphrase cannot pass $2^{80}$. If you are fine with 80-bit entropy then with Argon2id with nice parameters this is enough to be secure against password searching. $2^{50}\ll 2^{80}$

Still, the advice is to use a new 24-word mnemonic if you can keep it safe so that one may find the exploit the $80$-bit entropy - not clear now without brute-forcing the passphrase. If not,

Final advice; use password managers like keepass and password1 where you only need one good password preferably from dicewire or Bip39. They can create really random passwords for the needs and the password vaults are protected with your password and the rest is handled by them.


*Keep in mind that the number are approximate, not exact. We cannot be sure without sitting on the console of the The Supercomputer - Summit

$\endgroup$
3
  • 1
    $\begingroup$ I agree that "mosquito test above place birth tribe mountain market unknown robust act consider" or the permutation thing with 1M rather than 512 PBKDF2 iterations would be safe. But I'd rather spend that CPU time on Argon2, scrypt (presented 2009, widely available in 2013) or even bcrypt (1999) and be able to use a shorter phrase with equivalent security. Also I would not be able to confidently remember that long a passphrase, and I'm confident more than 1/4 of a user base would not, or would have written the passphrase. Thus I do not recommend that system. $\endgroup$
    – fgrieu
    Nov 10, 2021 at 7:25
  • $\begingroup$ Yeah, that was requiring a real calculation that I skipped since I can't be precise. However, 6 to 7 should be enough. Hmm, seems that i forgot to emphasize to use Argon2. Long password, well that is a human issue, however, some people write it down some forgot it. There are ews about forgotten password for the wallets that has huge amount of coins. It seems the limit of available coins approaches to 0 when n goes to infinity. I will update the answer, later. Thanks. $\endgroup$
    – kelalaka
    Nov 10, 2021 at 9:34
  • $\begingroup$ @fgrieu I guess the real aim of the passphrase is generating more than one private and the corresponding keys. Bitcoin uses lots of key pairs per user. They use more Hierarchical Deterministic Wallets, BIP0032/BIP0044 that fits more into usage. $\endgroup$
    – kelalaka
    Nov 12, 2021 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.