[bitcoin-dev] BIP proposal: derived mnemonics

[bitcoin-dev] BIP proposal: derived mnemonics

[millibitcoin]

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

Re: [bitcoin-dev] BIP proposal: derived mnemonics

[Jonas Schnelli]

[-- Attachment #1.1: Type: text/plain, Size: 1956 bytes --]

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>


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [bitcoin-dev] BIP proposal: derived mnemonics

[Jochen Hoenicke]

[-- Attachment #1: Type: text/plain, Size: 1069 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 1536 bytes --]

Re: [bitcoin-dev] BIP proposal: derived mnemonics

[Jonas Schnelli]

[-- Attachment #1.1: Type: text/plain, Size: 1673 bytes --]


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


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

Re: [bitcoin-dev] BIP proposal: derived mnemonics

[Gregory Maxwell]

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.