BIP proposal: derived mnemonics

(not sure so sent again after subscribing (one use case added))

Dear Bitcoin developers,

Below is provided a draft BIP proposal for a master mnemonic sentence from which other mnemonics sentences can be derived in a deterministic non-reversible way (on an offline computer). This would make it much easier to split funds into smaller fractions and use those in a HD-wallet when appropriate (just by inserting 12 or more words), without ever putting the master mnemonic at risk on an online computer. But there are many more use cases.

A reference implementation, specifically for use with a Trezor, has been generated and can be found at: http://thebitcoinecosystem.info/DerivedMnemonics.html

I'm not a professional programmer or cryptographer, so the idea and reference implementation will probably need a lot of reviewing but I do think Bitcoin needs this extension and the corresponding ease of use and improved security model.

In the hope you like the idea,

Regards, sumBTC

<pre>
   BIP: ???
   Title: Derived mnemonics from a master mnemonic.
   Author: sumBTC <millibitcoins@gmail•com>
   Status: For Discussion
   Type:
   Created: 2016-07-24
</pre>

==Abstract==

This BIP??? uses a master mnemonic sentence, as described in BIP39, for the deterministic generation of derived mnemonic sentences. The derived mnemonics are of the same format as the master mnemonic but can consist of a higher or lower number of words.

Binary seeds can then be generated for derived mnemonics (and master mnemonic) as described in BIP39. Each of these seeds can be used to generate deterministic wallets using BIP-0032 or similar methods.

==Motivation==

A mnemonic code or sentence is superior for human interaction as described in BIP39 and can, for example, be written on paper or even memorized. However, once a mnemonic has been used online, even through the use of a hardware wallet, the mnemonic could be compromised. This should be considered a bad practice from a security standpoint.

We therefore propose the generation of a master mnemonic offline and from this generate (also offline) multiple derived mnemonics in a deterministic way for online use. The master mnemonic is never used online and the master mnemonic cannot be obtained from the derived mnemonics. Examples of use cases are described below.

==Generating the master mnemonic==

The master mnemonic is first derived as a standard mnemonic as described in BIP39.

==From master mnemonic to derived mnemonics==

From the master mnemonic a new string is created:

string = MasterMnemonic + " " + Count + " " + Strength;

Here, MasterMnemonic are the space separated words of the master mnemonic. Count = 0, 1, 2 denotes the different derived mnemonics of a given strength and Strength = numWords / 3 * 32, where numWords is the number of words desired for the derived mnemonic and only integer arithmetic is used in the calculation (e.g. for numWords = 14, Strength = 128). Both Count and Strength are converted to strings.

This string is then hashed using sha512:

hash = sha512(string);

and turned into a byte array:

for (var i=0; i<strength/8; i++) {
   byteArray[i] = (hash[Math.floor((i%64)/4)] >>> ((i%4)*8)) & 0b11111111;
}

This byte array is then used to generate a new mnemonic as shown in the reference implementation using the method described in BIP39. The core of the new code in the reference manual can be found by jumping to "start: new code" in the reference software.

A passphrase for the master mnemonic has the same effect on the derived mnemoncis (so must be included).

==Reference Implementation==

The reference implementation generates addresses based on BIP44 for a 24 word master mnemonic and is available from

http://thebitcoinecosystem.info/DerivedMnemonics.html

or

github (not yet)

==Checking the derived mnemonics using Electrum==

The displayed addresses in each of the reference implementations can be easily checked using Electrum in the following manner:

move the directory ~/.electrum to a backup directory. start Electrum and choose: Restore a wallet or import keys Hardware wallet Restore Electum wallet from device seed words TREZOR wallet Insert one of the mnemonics and check that the same addresses are generated by Electrum

Check the private keys: move the directory ~/.electrum to a backup directory. start Electrum and choose: Restore a wallet or import keys Standard wallet Import one of the private keys and check that the correct address has been generated.

Some checks should include a passphrase.

==Examples of Use Cases==

A person with 25 bitcoin splits funds using 5 derived mnemonics and sends 5 bitcoins to the first address of each derived mnemonic. He can then use a (hardware) HD-wallet and simply insert one of the derived mnemonics to put only 5 bitcoins online and at risk at once. All funds can be recovered from the master mnemonic.

A person wants to give 10 bitcoin to each of his family members, giving each participant a derived mnemonic and sending bitcoin to each of them. The donating person can always recover the derived mnemonic if one of his family members loses his derived mnemonic.

For his Trezor wallet, someone wants to memorize only a 12 words master seed but wants to insert a 24 words derived seed so a key logger on his computer has 24! possibilities to check and not 12! (not a possibility for the current reference implementation but trivial to add).

Hi

> ==Generating the master mnemonic==
>
> The master mnemonic is first derived as a standard mnemonic as described
> in BIP39.

> ==From master mnemonic to derived mnemonics==
>
> From the master mnemonic a new string is created:
>
> string = MasterMnemonic + " " + Count + " " + Strength;
>
> Here, MasterMnemonic are the space separated words of the master
> mnemonic. Count = 0, 1, 2 denotes the different derived mnemonics of a
> given strength and Strength = numWords / 3 * 32, where numWords is the
> number of words desired for the derived mnemonic and only integer
> arithmetic is used in the calculation (e.g. for numWords = 14, Strength
> = 128). Both Count and Strength are converted to strings.
>
> This string is then hashed using sha512:
>
> hash = sha512(string);

1) My humble cryptographic understanding tells me that you should probably use sha512_hmac where you add an passphrase and a salt.

2) Side-note: Bip39 does still use PBKDF2 with 2048 iterations which I personally consider "not enough" to protect a serious amount of funds.

Also the checksum based on the predetermined wordlist has some security downsides over using a plain 32byte entropy (64hex chars) or a base58check encoded extended private master key.

3) Another idea: What would speak against deriving a child key after bip32, lets say at m/88'/0'/n' and use the derived 256bits to encode your mnemonic? This would at least require your master mnemonic passphrase to derive a valid "child mnemonic".

4) I'm still not convinced if we should encourage users to "only store and backup" the bip39 mnemonic. Reconstructing funds from a seed can be difficult especially if you don't have access to a trusted TX-indexed full node (~150GB of data required). Novice users might also underestimate the risk of losing metadata coupled with their transactions when they only store the wallet seed.

</jonas>

Jonas Schnelli via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> schrieb am Di., 26. Juli 2016 um 22:10 Uhr:

> Side-note: Bip39 does still use PBKDF2 with 2048 iterations which I
> personally consider "not enough" to protect a serious amount of funds.
>
>

But what are the alternatives? Put an expensive processor and a decent amount of memory in every hardware wallet to support scrypt? Use a million iterations and just wait 10 minutes after entering you passphrase? Or compute the secret key on your online computer instead?

Also, how many iterations are secure? A million? Then just add two random lower-case letters to the end of your passphrase and you have a better protection with 2048 iterations. If you want to be able to use your passphrase with cheap hardware and be protected against a high-end computer with multiple GPUs that is almost a mllion times faster, then you have to choose a good passphrase. Or just make sure nobody steals your seed; it is not a brainwallet that is only protected by the passphrase after all.

Regards,
  Jochen

> But what are the alternatives?  Put an expensive processor and a decent
> amount of memory in every hardware wallet to support scrypt?  Use a
> million iterations and just wait 10 minutes after entering you
> passphrase?  Or compute the secret key on your online computer instead?

What the Digital Bitbox team does, is, PBKDF2 the user entered passphrase on the computer with >20'000 iterations, then PBKDF2 again onchip with the 2048 rounds. If somebody manages to steal your backup (in that case a file/SDCard or printed PDF), it would at least required > 22'048 iterations to derive the key from a passphrase which I consider "stronger" then just using 2048 iterations.

> Also, how many iterations are secure?  A million?  Then just add two
> random lower-case letters to the end of your passphrase and you have a
> better protection with 2048 iterations.

I guess you shouldn't delegate KDF security to the user. But sure, this could help as well. This is part of the UI.

On the other hand, forcing the user to select a long/more-secure passphrase will very likely lead to many funds get lost behind encryption because of lost/forgotten passphrases.

> If you want to be able to use
> your passphrase with cheap hardware and be protected against a high-end
> computer with multiple GPUs that is almost a mllion times faster, then
> you have to choose a good passphrase.  Or just make sure nobody steals
> your seed; it is not a brainwallet that is only protected by the
> passphrase after all.

Agree. But IMO this fact should not be an excuse to reduce/use low iterations during KDF (especially SHA2 based KDFs).

</jonas>

On Wed, Jul 27, 2016 at 10:39 AM, Jochen Hoenicke via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org> wrote:

> Jonas Schnelli via bitcoin-dev <bitcoin-dev@lists•linuxfoundation•org>
> schrieb am Di., 26. Juli 2016 um 22:10 Uhr:
>>
>> Side-note: Bip39 does still use PBKDF2 with 2048 iterations which I
>> personally consider "not enough" to protect a serious amount of funds.
>>
>
> But what are the alternatives?  Put an expensive processor and a decent
> amount of memory in every hardware wallet to support scrypt?  Use a million
> iterations and just wait 10 minutes after entering you passphrase?  Or
> compute the secret key on your online computer instead?
>
> Also, how many iterations are secure?  A million?  Then just add two random
> lower-case letters to the end of your passphrase and you have a better
> protection with 2048 iterations. If you want to be able to use your
> passphrase with cheap hardware and be protected against a high-end computer
> with multiple GPUs that is almost a mllion times faster, then you have to
> choose a good passphrase.  Or just make sure nobody steals your seed;

Jochen, two alternatives were raised in public discussion:

Use a scheme which supports delegatable hardening-- (there are two broad classes proposed, one where the delegated party learns information that would let them bypass the part of the hardening they perform but only that part, and another where the delegation is information theoretically private.)

or

Eschew the pretextual 'hardening' that serves no purpose but to cause users to think the scheme is more secure than it is, and which makes the system more complex to implement.

Both were rejected by the authors of that spec.

> it is
> not a brainwallet that is only protected by the passphrase after all.

This ignores the history of that spec and the widespread use. Because of the design, the check value can't be computed without a fixed dictionary, and many people do use it as a brainwallet-- which is what that BIP originally specified, in fact.