BIP-39 passphrase hex rod

Can BIP-39 passphrase be cracked ?

In a recent post about BIP-39 I described how mnemonic sentences in the context of Bitcoin work and what makes them secure. 128 or 256 bit cryptography is considered secure and unbreakable now and for the foreseeable future. It's the basis on which Bitcoin wallet security depends on. Can the same thing be said about the optional BIP-39 passphrase, the so called 25th word ? Let's find out.

Here's a typical scenario: You have your 24 seed words backed up somewhere, ideally stamped on a piece of fireproof, acid-proof and pressure-proof stainless steel. You then decide to enable BIP-39 passphrase support in your hardware wallet and stamp the passphrase(s) on a hexagonal stainless steel rod and store the rod in a separate geographical location to your 24-word seed backup in order to:

  • make it more difficult to steal your funds in case your seed words get compromised
  • have multiple accounts in your wallet (each passphrase corresponding to a separate account)
  • pass on the Bitcoins to the relatives after your death

Then I stumble upon your BIP-39 mnemonic backup stashed in your office drawer, import it into a new Electrum wallet, check the wallet balance but none of the addresses have ever been used. I know you have some Bitcoins though because I also happen to know your Twitter handle, check your tweets and see many references to "HODL" and "TO THE MOON". I assume you must be using a BIP-39 passphrase.

The question then arises: "How easy is it to crack this extra passphrase?" and "What makes a good, hard to crack passphrase?"

While looking for answers I did some research and found some answers although they seemed a bit vague:

What does it mean a complex passphrase exactly? We can do some research ourselves by looking at the BIP-39 spec but this time we start where we finished last time:

The last step of BIP-39 is creating the actual binary seed which is then used as a master key in BIP-32 deterministic wallet or using other methods.

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

The passphrase is used in the final step of the BIP-39 key derivation process. It uses Password-Based Key Derivation Function 2 to turn the mnemonic sentence (the 12 or 24 seed words) + an optional passphrase into a binary seed. Below is a quote from Wikipedia describing the input parameters and the operation of this function (scroll down for a simpler explanation of PBKDF2):

PBKDF2 applies a pseudorandom function, such as hash-based message authentication code (HMAC), to the input password or passphrase along with a salt value and repeats the process many times to produce a derived key, which can then be used as a cryptographic key in subsequent operations. The added computational work makes password cracking much more difficult, and is known as key stretching.

Having a salt added to the password reduces the ability to use precomputed hashes (rainbow tables) for attacks, and means that multiple passwords have to be tested individually, not all at once. The standard recommends a salt length of at least 64 bits.[6] The US National Institute of Standards and Technology recommends a salt length of 128 bits.

The PBKDF2 key derivation function has five input parameters:

DK = PBKDF2(PRF, Password, Salt, c, dkLen)

where:

  • PRF is a pseudorandom function of two parameters with output length hLen (HMAC-SHA512 in BIP-39)
  • Password is the master password from which a derived key is generated (mnemonic words)
  • Salt is a sequence of bits, known as a cryptographic salt (BIP-39 passphrase)
  • c is the number of iterations desired (2048 iterations in BIP-39)
  • dkLen is the desired bit-length of the derived key (512 bits)
  • DK is the generated derived key

A simpler explanation of PBKDF2 is this: It's a cryptographic function designed to turn some password and an optional passphrase (salt) into a cryptographic hash. This function is designed to run slowly (think 2048 times slower than a single invocation of HMAC-SHA512 in the context of Bitcoin). In the case of BIP-39 final key derivation this is the gist of what PBKDF2 does: it runs HMAC-SHA512 2048 times. This is the only thing that we need to keep in mind for now.

BIP-32 (Hierarchical deterministic wallet)

Once we run PBKDF2 on our mnemonic sentence + a passphrase we end up with a key. This key is then used as a seed to BIP-32 private/public key generation. I'm not going to dive into the details of BIP-32 here, suffice to say that the cost of generating private/public keys and associated addresses and checking them against a database of addresses ever used is negligible compared to the PBKDF2 function above.

Classes of attack

Let's define a few classes of attack. Each class represents the level of attack on BIP-39 passphrase and requires more and more expensive hardware.

Class A (10,000 hashes/s): My laptop can run about 500 PBKDF2-HMAC-SHA512 hashes per second on a single CPU core. Let's assume I can run it on all 8 cores and get 4000 hashes/s and I have 2 laptops.

Class B (1,000,000 hashes/s): GeForce GTX 1080 can run approx. 240,000 hashes/s. We have a few gfx cards at our disposal for this kind of attack.

Class C (100,000,000 hashes/s): Hypothetically we can assume cracking BIP-39 passphrases will be profitable in the near future and some company will create a specialised ASIC just for this purpose. Let's assume it will be 10x faster than the GFX card above so roughly 2,4M hashes/s. A typical attacker will own a few such specialised devices.

Class D: (1,000,000,000 hashes/s): A supercluster of ASIC (like a mining pool but for cracking PBKDF2-HMAC-SHA512)

It's worth mentioning that no devices of Class C or Class D exist today. It's possible that such devices might appear one day though so we need to keep this in mind when deciding about the length of our passphrase we want to use.

BIP-39 passphrase cracking times

Let's consider a few typical dictionaries and charsets people use when generating passwords in general and BIP-39 passphrases in particular:

Let's bear the following in mind:

  • An attacker doesn't know what dictionary/charset you used for your passphrase. He/she may start with the easiest dictionaries/combinations (for example 1 or 2 word dictionary lookups) and then move on to more difficult strategies. The actual time it takes to crack your passphrase might be longer than the time given in the tables below.
  • On the other hand on average it'll take half the time given in the tables below for an attacker to obtain the correct passphrase
  • A general formula for calculating passphrase entropy in bits is log2(no_of_combinations). So for example log2(2048^2) = 22 bits of entropy. Recollect that the PKCS standard recommends a salt length of at least 64 bits.

PBKDF2 weakness (optimisation)

Andrea Visconti, Simone Bossi, Hany Ragab an Alexandro Calò published a paper called "On the weakness of PBKDF2". The gist of it is that there are a few optimisations in PBKDF2 that can be implemented and the whole scheme gets optimised. The authors mention 50% optimisation in the first case. So we can bear this in mind when reading the cracking times below. (Eg. We can assume the actual optimisation will in fact be 50% in which case instead of 2 milleniums the cracking time will be 1 millenium etc.).

BIP-39 wordlist (2048 words)

BIP-39 wordlist abandon,ability,...,zoo
Password Class of Attack
Words Combinations Entropy Class A Class B Class C Class D
2 2048^2 22 Bits 7 Mins 4 Secs Instant Instant
3 2048^3 33 Bits 10 Days 2 Hours 85 Secs 8 Secs
4 2048^4 44 Bits 55 Years 203 Days 2 Days 4 Hours
5 2048^5 55 Bits 114 Milleniums 1 Millenium 11 Years 1.5 Years
6 2048^6 66 Bits ∞ ∞ ∞ 2 Milleniums
7 2048^7 77 Bits ∞ ∞ ∞ ∞

Long Diceware Wordlist (7776 words)

Diceware wordlist abacus,...,zoom
Password Class of Attack
Words Combinations Entropy Class A Class B Class C Class D
2 7776^2 26 Bits 100 Mins 1 Minute Instant Instant
3 7776^3 39 Bits 1.5 Years 130 Hours 1.5 Hours 7 Mins
4 7776^4 52 Bits 11 Milleniums 115 Years 1.5 Years 42 Days
5 7776^5 65 Bits ∞ ∞ 9 Milleniums 901 Years
6 7776^6 76 Bits ∞ ∞ ∞ ∞
7 7776^7 90 Bits ∞ ∞ ∞ ∞

Short Diceware Wordlist (1296 words)

Diceware wordlist acid,...,zoom
Password Class of Attack
Words Combinations Entropy Class A Class B Class C Class D
2 1296^2 21 Bits 3 Mins 1 Sec Instant Instant
3 1296^3 31 Bits 60 Hours 36 Mins 21 Secs Instant
4 1296^4 41 Bits 3 Milleniums 32 Days 8 Hours 47 Mins
5 1296^5 52 Bits ∞ 4 Milleniums 1.5 Years 42 Days
6 1296^6 62 Bits ∞ ∞ 1.5 Milleniums 150 Years
7 1296^7 72 Bits ∞ ∞ ∞ ∞

Numerals

Numerals 0123456789
Password Class of Attack
Length Combinations Entropy Class A Class B Class C Class D
2 100 7 Bits Instant Instant Instant Instant
3 1000 10 Bits Instant Instant Instant Instant
4 10,000 13 Bits Instant Instant Instant Instant
5 100,000 17 Bits 10 Secs Instant Instant Instant
6 1 Million 20 Bits 2 Mins 1 Sec Instant Instant
7 10 Million 23 Bits 20 Mins 10 Sec Instant Instant
8 100 Million 27 Bits 3.5 Hours 1.5 Mins Instant Instant
10 10 Billion 33 Bits 15 Days 3.5 Hours 2 Mins 1 Sec
12 1 Trillion 40 Bits 3 Years 11 Days 3 Hours 17 Mins
20 10^20 66 Bits ∞ ∞ ∞ 3 Milleniums

Alphabet - 26 characters

Upper Case Alpha ABCDEFGHIJKLMNOPQRSTUVWXYZ Lower Case Alpha abcdefghijklmnopqrstuvwxyz
Password Class of Attack
Length Combinations Entropy Class A Class B Class C Class D
2 676 9 Bits Instant Instant Instant Instant
3 17,576 14 Bits 2 Secs Instant Instant Instant
4 456,976 19 Bits 46 Secs Instant Instant Instant
5 11.8 Million 23 Bits 20 Mins 12 Secs Instant Instant
6 308.9 Million 28 Bits 8.5 Hours 5 Mins 3 Secs Instant
7 8 Billion 33 Bits 9 Days 2 Hours 1 Mins 8 Secs
8 200 Billion 38 Bits 242 Days 2.5 Days 35 Mins 3.5 Mins
9 5.4 Trillion 42 Bits 17 Years 63 Days 15 Hours 1.5 Hours
10 141 Trillion 47 Bits 447 Years 4.5 Years 16 Days 39 Hours
12 95 Quadrillion 56 Bits 302 Milleniums 3 Milleniums 30 Years 3 Years
15 1.6 Sextillion 70 Bits ∞ ∞ 531 Years 53 Years
20 19.9 Octillion 94 Bits ∞ ∞ ∞ ∞

Alphanum - 36 characters

Upper Case Alpha ABCDEFGHIJKLMNOPQRSTUVWXYZ or Lower Case Alpha abcdefghijklmnopqrstuvwxyz and Numerals 0123456789
Password Class of Attack
Length Combinations Entropy Class A Class B Class C Class D
2 1,296 10 Bits Instant Instant Instant Instant
4 1.6 Million 21 Bits 2.5 Mins 1.5 Secs Instant Instant
6 2 Billion 31 Bits 2.5 Days 36 Mins 21 Secs Instant
8 36^8 41 Bits 9 Years 32 Days 7 Hours 47 Mins
10 36^10 52 Bits 11 Milleniums 115 Years 423 Days 42 Days
12 36^12 62 Bits ∞ 150 Milleniums 1500 Years 150 Years
15 36^15 77 Bits ∞ ∞ ∞ ∞
20 36^20 103 Bits ∞ ∞ ∞ ∞

Is my passphrase SAFU ?

Coldbit BIP39 Passphrase - 7 word passphrase
  • If your passphrase is a 1 word from a dictionary (aka the 25th word) it is NOT SAFE. Change it to at least a 4 word passphrase as soon as possible
  • lonelypumpkins is a better passphrase than hodl but it's not a passphrase than can withstand a few hours of cracking on regular hardware (too short)
  • For the Long Diceware dictionary - use at least 4 words
  • For the Short Diceware dictionary - use at least 6 words
  • If you want to use BIP-39 wordlist as your dictionary use at least 6 words.
  • You don't have to limit yourself to dictionary words. The more uncommon word you use the more difficult it is to crack and the harder to remember.
  • Don't make the common mistakes people make when coming up with a passwords. Don't use your birthday, people's names, pets' names and favourite places as your passphrases.
  • When in doubt roll a dice and pick 6 random words from the long diceware list.
  • Don't rely on your memory or paper or electronic devices to store your passphrases. Get Coldbit Passphrase coupled with Coldbit Steel or Coldbit Hex to have a durable, fireproof, waterproof and pressure-proof backup of your seed words and passphrases.

BTCRecover

You can see a practical example of using BTCRecover to recover a forgotten password below. In these examples the public address is known and there is no need to look it up in the blockchain (which will slow the process down).

How I checked over 1 trillion mnemonics in 30 hours to win a bitcoin

1 year later after publishing this article John Cantrell brute-forced the missing 4 words from a 12-word mnemonic and swept 1 BTC using a rented farm of powerful gfx cards. We estimated a Class C attack (a farm of powerful gfx cards or ASICs) to take ~ 2 days to crack 4 missing BIP-39 words. Very close to John's result.

Back to blog