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:

• Here’s a page from Trezor’s wiki describing multi-passphrase encryption, the $5 wrench attack and example passphrases: “lonelypumpkins” and “funnyspirit“. – how good are such passphrases (2 English dictionary words)?
• Here’s Andreas Antonopoulos in Sep 2018 saying that “a relatively complex passphrase will keep you safe for several weeks to a month. A very strong, complex passphrase will keep you safe for months.“
• By the way Andreas’ recommended word-length for pass-phrases changed from:
  • 8–10 words, in July ‘18
  • 6–8 words, in Sept ‘18
  • 4–6 words, in Feb ‘19

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:

• BIP-39 wordlist (2048 word dictionary)
• EFF diceware long wordlist for use with five dice (7776 words)
• EFF diceware short wordlist for use with four dice (1296 words)
• Numerals (0-9) – 10 characters
• Alphabet (either upper or lower case letters) – 26 characters
• Alphanum (either upper or lower case letters + numbers) – 36 characters

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 ?

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

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.