Bitcoin

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 wordlistabandon,ability,…,zoo
PasswordClass of Attack
WordsCombinationsEntropyClass AClass BClass CClass D
22048^222 Bits7 Mins4 SecsInstantInstant
32048^333 Bits10 Days2 Hours85 Secs8 Secs
42048^444 Bits55 Years203 Days2 Days4 Hours
52048^555 Bits114 Milleniums1 Millenium11 Years1.5 Years
62048^666 Bits2 Milleniums
72048^777 Bits

Long Diceware Wordlist (7776 words)

Diceware wordlistabacus,…,zoom
PasswordClass of Attack
WordsCombinationsEntropyClass AClass BClass CClass D
27776^226 Bits100 Mins1 MinuteInstantInstant
37776^339 Bits1.5 Years130 Hours1.5 Hours7 Mins
47776^452 Bits11 Milleniums115 Years1.5 Years42 Days
57776^565 Bits9 Milleniums901 Years
67776^676 Bits
77776^790 Bits

Short Diceware Wordlist (1296 words)

Diceware wordlistacid,…,zoom
PasswordClass of Attack
WordsCombinationsEntropyClass AClass BClass CClass D
21296^221 Bits3 Mins1 SecInstantInstant
31296^331 Bits60 Hours36 Mins21 SecsInstant
41296^441 Bits3 Milleniums32 Days8 Hours47 Mins
51296^552 Bits4 Milleniums1.5 Years42 Days
61296^662 Bits1.5 Milleniums150 Years
71296^772 Bits

Numerals

Numerals0123456789
PasswordClass of Attack
LengthCombinationsEntropyClass AClass BClass CClass D
21007 BitsInstantInstantInstantInstant
3100010 BitsInstantInstantInstantInstant
410,00013 BitsInstantInstantInstantInstant
5100,00017 Bits10 SecsInstantInstantInstant
61 Million20 Bits2 Mins1 SecInstantInstant
710 Million23 Bits20 Mins10 SecInstantInstant
8100 Million27 Bits3.5 Hours1.5 MinsInstantInstant
1010 Billion33 Bits15 Days3.5 Hours2 Mins1 Sec
121 Trillion40 Bits3 Years11 Days3 Hours17 Mins
2010^2066 Bits3 Milleniums

Alphabet – 26 characters

Upper Case AlphaABCDEFGHIJKLMNOPQRSTUVWXYZLower Case Alphaabcdefghijklmnopqrstuvwxyz
PasswordClass of Attack
LengthCombinationsEntropyClass AClass BClass CClass D
26769 BitsInstantInstantInstantInstant
317,57614 Bits2 SecsInstantInstantInstant
4456,97619 Bits46 SecsInstantInstantInstant
511.8 Million23 Bits20 Mins12 SecsInstantInstant
6308.9 Million28 Bits8.5 Hours5 Mins3 SecsInstant
78 Billion33 Bits9 Days2 Hours1 Mins8 Secs
8200 Billion38 Bits242 Days2.5 Days35 Mins3.5 Mins
95.4 Trillion42 Bits17 Years63 Days15 Hours1.5 Hours
10141 Trillion47 Bits447 Years4.5 Years16 Days39 Hours
1295 Quadrillion56 Bits302 Milleniums3 Milleniums30 Years3 Years
151.6 Sextillion70 Bits531 Years53 Years
2019.9 Octillion94 Bits

Alphanum – 36 characters

Upper Case AlphaABCDEFGHIJKLMNOPQRSTUVWXYZor Lower Case Alphaabcdefghijklmnopqrstuvwxyzand Numerals0123456789
PasswordClass of Attack
LengthCombinationsEntropyClass AClass BClass CClass D
21,29610 BitsInstantInstantInstantInstant
41.6 Million21 Bits2.5 Mins1.5 SecsInstantInstant
62 Billion31 Bits2.5 Days36 Mins21 SecsInstant
836^841 Bits9 Years32 Days7 Hours47 Mins
1036^1052 Bits11 Milleniums115 Years423 Days42 Days
1236^1262 Bits150 Milleniums1500 Years150 Years
1536^1577 Bits
2036^20103 Bits

Is my passphrase SAFU ?

Coldbit Passphrase - 4 words
Coldbit BIP39 Passphrase – 4 words
  • 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 the dice and pick 6 random words from the short diceware list.
  • Don’t rely on your memory or paper or electronic devices to store your passphrases. Order Coldbit Passphrase coupled with Coldbit Steel to have a durable, fireproof, waterproof and pressure-proof backup of your seed words and passphrases.
Coldbit 7 Word Passphrase
Coldbit 7-Word Passphrase from the short diceware list

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

If you want to learn more about Bitcoin wallet/key security and best practices for safe storage sign up to our newsletter below:

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.

14 Comments

Leave a Reply to Defcon0 Cancel reply

Your email address will not be published.

No products in the cart.