BIP39 HMAC-SHA512 rationale ?

[Ninki-Ben]

I was reading the BIP39 spec for generating mnemonics from bits of entropy and so derive a n word phrase. The mnemonic phrase is then stretched using 2048 rounds of sha512, with an optional salted password.

I am finding it difficult to rationalise the 2048 rounds. Assuming the default password is used ("mnemonic" according to the specification) all the 2048 rounds would do is slow down a brute force attack on guessing an n bit key.

What is the attack vector for this? The one I came up with was, if someone saw your phrase and partially memorized it, it would massively slow them down trying various combinations to discover the seed.

Am I missing something important here?

[DeathAndTaxes]

It is called key stretching.

Say the attacker has a brute force cracking rig which can do 1 billion hashes per second.  By requiring 2048 rounds you reduce the attackers throughput to ~500K passwords per second.

Honestly though 2048 is far too low.  For example PBKDF2 (a common key stretching algorithm) by default does 100,000 hashing operations.  This would reduce the same hypothetical attacker to 10,000 passwords per second.

[Ninki-Ben]

Yes, but my point is, this isn't a password or a spec for a brain wallet, it is computer generated entropy, lets say 256 bits, with a csprng, being represented as a word list. So the only use case I can see, if you use the specification's default password, is slowing down an attacker who has seen a part of your phrase and so significantly reduced the search space. The stretching makes sense if you use a chosen password and assume your seed phrase will not be kept secret.


I was pointed to this discussion which gives some insight into the thinking:

https://github.com/bitcoin/bips/pull/17

Cheers

Ben

[DeathAndTaxes]

The HMAC is only used when going from mnemonic -> seed.  

A user may decide to protect their mnemonic by passphrase. If a passphrase is not present, an empty string "" is used instead.

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

The spec however allows the user to add a user defined passphrase. So the key stretching is to protect the user defined passphrase not the raw mnemonic.  If there is no user defined passphrase then HMAC is still used for consistency but it has no effect on security.

Still I don't see much utility in this as 2,048 is an insufficient number of iterations to provide more than a cryptographic speed bump.  A single GPU cracker can perform 80M+ HMAC-SHA512 operations per second reducing that by a factor of 2,048 still means 40,000 passwords per second and that is just a single GPU.

To put it into context iTunes uses 10,000 rounds of PBKDF2 to protect an mp3 account.  The Lastpass password manager defaults to 100,000 rounds of PBKDF2 and it can be increased by the user.  Key stretching should be as long as possible (but not so long as to disrupt the user).  Making a user wait 30 seconds every time they login isn't viable  but creating or restoring a seed is infrequent.  The iterations should be at least a hundred thousand if not hundreds of thousands.  It could even be variable by using a few bits from the checksum.

[gmaxwell]

Still I don't see much utility in this as 2,048 is an insufficient number of iterations to provide more than the cryptographic equivalent of a speed bump.  A single GPU cracker can perform 80M+ HMAC-SHA512 operations per second.  To put it into context iTunes uses 10,000 rounds of PBKDF2 and that is to protect a mp3 account.  Lastpass (password manager) defaults to 100,000 rounds of PBKDF2 and it can be increased by the user.  Key stretching should be as long as possible (but not so long as to disrupt the user).  Since creating or restoring a seed is infrequent the iterations should be as high as possible that it will still complete in a few seconds (or at a minimum a significant fraction of a second).

I provided feedback along these lines too: https://github.com/bitcoin/bips/pull/17#issuecomment-34442152

What ended up getting proposed there is effectively a fairly insecure brainwallet scheme. I'd personally not recommend people deploy it.