Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet master seed with optional encryption

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet master seed with optional encryption

[Jean-Paul Kogelman]

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

Hi Jeremy,

The main reason is to stick as close to BIP 0038 as possible, allowing implementers to reuse existing code paths. This proposal and BIP 0032 don't really put any restrictions on content of the seed itself (as can be seen in test vector 1).

jp

On Jul 19, 2013, at 11:09 AM, Jeremy Spilman <jeremy@taplink.co> wrote:

Very clear write-up Jean!

Quick question - what is the purpose of step 10 of the encryption process -- why XOR the master seed with some bytes of the hashed passphrase before encrypting the XOR'd master seed with the remaining bytes of the hashed passphrase? Versus simply encrypting the master seed with the hashed passphrase of equal length to the seed?

Does this basically serve the fucntion of an IV?

Do you really need this since the master seed must be high entropy random bytes in the first place?

Thanks,
--Jeremy

On Fri, 19 Jul 2013 10:46:44 -0700, Jean-Paul Kogelman <jeanpaulkogelman@me.com> wrote:


Hi everyone,

I'm looking for feedback on the proposal below.

Kind regards,

Jean-Paul

---
BIP: 
Title: Base58 encoded HD Wallet master seed with optional encryption
Author: Jean-Paul Kogelman
Status: Draft
Type: Informational
Created: 17-07-2013

Abstract

This proposal describes a method for encoding and optionally encrypting a Bitcoin Hierarchical Deterministic (HD) Wallet master seed. Encoded master seeds are intended for use on paper wallets. Each string contains all the information needed to verify and reconstitute an HD wallet except for the optional passphrase. The encrypted version uses salting and scrypt to resist brute-force attacks.

The method provides two encoding methodologies in 3 lengths each (16, 32 and 64 byte seeds). One is a clear version of the master seed with verification information for integrity checking and the other is an encrypted representation.

A 32-bit hash of the resulting master Bitcoin public address is encoded in plain text within each seed record, so in the case of an encrypted seed, it can be correlated to a Bitcoin public address with reasonable probability by someone not knowing the passphrase. The complete Bitcoin public address can be derived through successful decoding and optional decryption of the master seed record.


Motivation

The extended private keys proposed in BIP 0032 are long, fixed length records and don't offer any form of security. The master seed used to generate the HD wallet is typically shorter than the extended master private key that results from it. 

A compact representation of the master seed is easier to handle and a 2-factor version of the master seed record allows for safe storage and the creation of paper wallets by 3rd parties. 


Copyright

This proposal is hereby placed in the public domain.


Rationale

User story: As a Bitcoin user who uses HD wallets, I would like the ability to store my wallet master seed in a compact form as a paper wallet.

User story: As a Bitcoin user who uses HD wallets, I would like the ability to have a 3rd party create a paper wallet with my master seed in it, without having access to the funds stored in the wallet.

User story: As a Bitcoin user who uses HD wallets, I would like the ability to choose the strength of the master seed depending on my security requirements and how I wish to store it. 


Specification

This proposal makes use of the following functions and definitions:

AES256Encrypt, AES256Decrypt: the simple form of the well-known AES block cipher without consideration for initialization vectors or block chaining. Each of these functions takes a 256-bit key and a variable legth of input and deterministically yields output data of similar length to the input.

SHA256: a well-known hashing algorithm that takes an arbitrary number of bytes as input and deterministically yields a 32-byte hash.

RIPEMD160: a well known hashing algorithm that takes an arbitrary number of bytes as input and deterministically yields a 20-byte hash.

scrypt: A well-known key derivation algorithm. It takes the following parameters: (string) password, (string) salt, (int) n, (int) r, (int) p, (int) length, and deterministically yields an array of bytes whose length is equal to the length parameter.

HMAC-SHA512: Produces a 64 byte (512 bit) hash based message authentication code using the SHA512 hash function using a seed (in our case we will use a byte representation of "Bitcoin seed") and an aribtrary input message. The output will be 64 bytes.

Base58Check: a method for encoding arrays of bytes using 58 alphanumeric characters commonly used in the Bitcoin ecosystem.

G, N: Constants defined as part of the secp256k1 elliptic curve. G is an elliptic curve point, and N is a large positive integer.

Prefix

It is proposed that the resulting Base58Check-encoded string start with either "WS" for clear master seed records or "ws" for 2-factor master seed records. The prefixes "WS" and "ws" were chosen as abreviations of the term "Wallet Seed" and upper case to indicate whether it's a clear representation and lower case when it's a 2-factor representation. 

To keep the size of the encrypted key equal to the clear version, no initialization vectors (IVs) are used in the AES encryption. Rather, suitable values for IV-like use are derived using scrypt from the passphrase and from using a 32-bit hash of the resulting Bitcoin public address as salt.

Proposed specification

There are 2 seed record representations with 3 lengths each, resulting in a total of 6 different object identifier prefixes. 

Prefix 0x1093: Clear 16 byte master seed, total length: 22 bytes
Prefix 0x1E68: Clear 32 byte master seed, total length: 38 bytes
Prefix 0x665A: Clear 64 byte master seed, total length: 70 bytes

Prefix 0x1EE4: 2-factor 16 byte master seed, total length: 22 bytes
Prefix 0x38AE: 2-factor 32 byte master seed, total length: 38 bytes
Prefix 0xBECB: 2-factor 64 byte master seed, total length: 70 bytes

These are constant bytes that appear at the beginning of the Base58Check-encoded record, and their presence causes the resulting string to have a predictable prefix.

How the user sees it: 35, 57 or 101 characters always starting with either "WS" or "ws".

Count of payload bytes (beyond prefix): 20, 36 or 68

Payload format:
4 bytes: SHA256(SHA256(master_bitcoin_public_address))[0...3], used both for typo checking and as salt.
16, 32 or 64 bytes: either a clear representation or an encrypted representation of the master seed.

Range in Base58Check encoding for clear 16 byte master seed (prefix WS):
Minimum value: WSJ5JnjiRZT8b15aZr6GGWzt2VMBPapmhBQ (based on 0x10 0x93 plus twenty 0x00's)
Maximum value: WShQumr1iGdbTpWiesWbb189p7rSLBiq3EJ (based on 0x10 0x93 plus twenty 0xFF's)

Range in Base58Check encoding for clear 32 byte master seed (prefix WS):
Minimum value: WS7SqjMWhDGCagcZxCk317LLWyWUny7465ENGKEKuxBf5sFvRHmRRfCgr (based on 0x1E 0x68 plus thirty-six 0x00's)
Maximum value: WSLAbo8WHEQr1Z1cv26Z5njh5URHMo9fPiDFYE2NpCwmAoPZwDxzm3PjB (based on 0x1E 0x68 plus thirty-six 0xFF's)

Range in Base58Check encoding for clear 64 byte master seed (prefix WS):
Minimum value: WS2cMzM9WrogWVLKYFzTaTXZnYCryY31uptmdevXuRFBXTWJhmt4No9Eejoj3apqyU5RkyXsGHFPbZd14oz7Fv1Mi85kadBD4TPsL (based on 0x66 0x5A plus sixty-eight 0x00's)
Maximum value: WS6PXJ1HoJXn9hyLz8uXQEy2ZajAVaFDTViXhZDthwYbhyvfHRqjwU4FoGpepCbuuycAwMFbgoZB6E48baqD1c9PdMNUZCSSBmfE7 (based on 0x66 0x5A plus sixty-eight 0xFF's)

Range in Base58Check encoding for 2-factor 16 byte master seed (prefix ws):
Minimum value: ws1nyTi9KjdRkJda4Yh1KkXSLC8SZ6kKzEM (based on 0x1E 0xE4 plus twenty 0x00's)
Maximum value: wsR8aSpScSotd84i9a7LeEei7pdhVkeciX8 (based on 0x1E 0xE4 plus twenty 0xFF's)

Range in Base58Check encoding for 2-factor 32 byte master seed (prefix ws):
Minimum value: wsC8sayZpTpeX3k6jcCMeTedDapXkXd7SZpRJbSjdeqKBJ2Vnrm1xyfD3 (based on 0x38 0xAE plus thirty-six 0x00's)
Maximum value: wsQrdekZQUyHwv99hRYsj93yn5jLKMfikCoJaWEnXubRGEA9Jnxg5KaPW (based on 0x38 0xAE plus thirty-six 0xFF's)

Range in Base58Check encoding for 2-factor 64 byte master seed (prefix ws):
Minimum value: ws4XTrriTEyyy2TrGWv9R7o94CyBiN69S2VxiK5tVW9htEi48w54sQ43JChCmadoGtYpZSu7vqbbQTMemCSyyToyLPPMjughcXNxE (based on 0xBE 0xCB plus sixty-eight 0x00's)
Maximum value: ws8JdAWrjgi5cF6siPqDEuEbqFVVEQJLyhKinDPFJ2T84m8Qib2kS4y4Sji8YCQsDQ5ZjpcrMMuNu7nnHyJ5j9x1Fcg5iUwvZ7krH (based on 0xBE 0xCB plus sixty-eight 0xFF's)

Generation of master seed:

1. Take either an existing 16, 32 or 64 byte master seed S, or generate one from a (P)RNG.
2. Calculate I = HMAC-SHA512(key = "Bitcoin seed", msg = S)
3. Split I into two 32-byte sequences, IL and IR.
4. Use IL as master secret key. IR, the master chain code is not relevant here.
5. In case IL is 0 or >= N, the master key is invalid. Go back to step 1 if generating, or in case of a provided master seed, return an error.
6. Compute the public key K = IL*G
7. Calculate the master Bitcoin public address A = Base58Check(RIPEMD160(SHA256(K)))
8. Calculate the salt = SHA256(SHA256(A))[0...3]

Encryption:

9. Derive a hash H from the passphrase using scrypt
    - Parameters: passphrase is the passphrase itself encoded in UTF-8, salt = salt, n = 16384, r = 8, p = 8, length = seed length + 32
10. The first number of bytes in H, equal to length of seed S are used to xor seed S. Call the result X.
11. Do AES256Encrypt(message = X, key = last 32 bytes of H), call this encrypted_seed.


The encrypted_master_seed is the Base58Check-encoded concatenation of the following, which totals 2 + 4 + seed length bytes (22, 38 or 70 bytes):

encrypted_master_seed = prefix + salt + encrypted_seed

The clear version is:

master_seed = prefix + salt + seed S


Decryption:

1. Collect encrypted_master_seed and passphrase from user.
2. Perform step 9 of encryption with the passphrase and the salt from the encrypted_master_seed.
3. With the encrypted_seed from encrypted_master_seed do AES256Decrypt(message = encrypted_seed, key = last 32 bytes of H), call this decrypted_seed.
4. With the first number of bytes in H, equal to the length of the decrypted_seed, perform the xor operation on decrypted_seed and call the result S.
5. Perform generation steps 2 until 8 and verify that the generated salt is equal to the salt from encrypted_master_seed.


Suggestions for implementers of proposal with alt-chains

This proposal involves hashing of a text representation of a public address which for Bitcoin includes the leading '1'. Alt-chains can easily be denoted simply by using the alt-chain's preferred format for representing an address. Alt-chain implementers may also change the prefix such that encoded master seeds do not start with "WS" or "ws".


Bitcoin testnet representation

This proposal does not cover separate Bitcoin testnet representations of encoded master seeds, although since the 4 salt bytes are based on a double SHA256 of the Bitcoin public address, they will be different for Bitcoin testnet public addresses and validation will fail. 


Reference implementation

TODO


Test vectors

Test 1:

Seed      : 000102030405060708090a0b0c0d0e0f
Clear     : WSZsLQ5c1uKrRQugbrZNYsvMhRixiaWaVmJ
Password  : Satoshi
Encrypted : wsHb15443fYPmneEXskd6wUZeP15fCiA69n
Address   : 15mKKb2eos1hWa6tisdPwwDC1a5J1y9nma
xprv      : xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6LnF5kejMRNNU3TGtRBeJgk33yuGBxrMPHi
xpub      : xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjqJoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8

Test 2:

Seed      : 7f0ad7d595be13e6fe4cf1fa0fbb6ae9c26c5d9b09920709414982b6363d5844
Clear     : WSB7z3izBZwDoaAUA4mDpEHzAZsA5zfTWu3cCxhkaLtZ4Ur6n6mXsgpMK
Password  : Nakamoto
Encrypted : wsFp1uM2gFhd2PuRzmNFReRud71hgmVwPoc7cGpxuvgETRsv8J1wHNANJ
Address   : 1A54ECavJaJAoLGqqNrPd9Y3cvSvkL2Roz
xprv      : xprv9s21ZrQH143K3f9hMVvcbY4EX4CfxsEtc6C5BMkZtgGpTGpxAscoq7SLSAcL6k5dxaZ9s4SChrtfSFoKpijuwAnhuPn76eva6W8bDr118t3
xpub      : xpub661MyMwAqRbcG9EATXTcxfzy563ANKxjyK7fykABT1ooL5A6iQw4NukpHShDxYgeso4NHscFmqcVEtdUt61c8RCf7FqXK9z6sgfkQvYBQPP

Test 3:

Seed      : fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8a8784817e7b7875726f6c696663605d5a5754514e4b484542
Clear     : WS6186bsAkSaGRjRZ1UGyCGigxsXPvnYGSqNHJYmauV9X4W8tLJke1DH8UP8YMsDLdsjwgodcghjjKqkWQmk3t7qDbNMJVBDKcD2s
Password  : Vires In Numeris
Encrypted : ws7vDy7RjqMvcPX7GeakKvdK6vDKGhRSjQtaRfKUVQrJXwwetLSeTdNgGzn5BKZZqz1BBdaHBFYfLvNUSxDaoP1ojJMMJD9UnQuwt
Address   : 1JEoxevbLLG8cVqeoGKQiAwoWbNYSUyYjg
xprv      : xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U
xpub      : xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB

Test 4:

Seed      : 6ca4a27ac660c683340f59353b1375a9
Clear     : WSXnfK5CJbDoSwcqMfz7Xqy3avuPHSxDQQk
Password  : 聡中本
Encrypted : wsFWKz3c5eeHRwtJveSdFvwUrmoNVkJ5ns2
Address   : 1JVncPbsdB2s4zHim3VdAWNkZ8JANBZ1U9
xprv      : xprv9s21ZrQH143K3mJ4upPSDfXdA34yNjem6PSsXT63vm8dq8ikUJv4iiTD3PrSKtdGZXFVD689z5T7knXo55BjcHS2WL3Syp2DbGgnbgxw2QA
xpub      : xpub661MyMwAqRbcGFNY1qvSaoUMi4uTnCNcTcNUKqVfV6fchw3u1rEKGWmgtfUMRKLgUHNZ7dfsh8Ys6SLwUojZqScFBQL3dFGF3QywNLJVZ2o


Acknowledgements

Mike Caldwell for BIP 0038, which this proposal borrows heavily from.


See Also

BIP 0032 Hierarchical Deterministic Wallets: https://en.bitcoin.it/wiki/BIP_0032
BIP 0038 Passphrase-protected private key: https://en.bitcoin.it/wiki/BIP_0038





[-- Attachment #2.1: Type: text/html, Size: 17356 bytes --]

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet master seed with optional encryption

[Mike Hearn]

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

This isn't usable for SPV wallets unless it has a birthday in it. Otherwise
you either need to scan the entire chain (slow) or find a fully indexed
copy of the block chain (expensive, more centralised). Just add a UNIX time
as an extra 4 bytes, or if you want to save a few characters then use a
uint16 that represents "days since birth of this specification".

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet master seed with optional encryption

[Jean-Paul Kogelman]

Hi Mike,

I had a similar request on the forums. I suggested adding either a 2 byte 'weeks since genesis' or 'months since genesis', but starting from spec birth works too. Would either of those work for you?


jp

On Jul 22, 2013, at 6:14 AM, Mike Hearn <mike@plan99.net> wrote:

> This isn't usable for SPV wallets unless it has a birthday in it. Otherwise you either need to scan the entire chain (slow) or find a fully indexed copy of the block chain (expensive, more centralised). Just add a UNIX time as an extra 4 bytes, or if you want to save a few characters then use a uint16 that represents "days since birth of this specification".

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet master seed with optional encryption

[Jean-Paul Kogelman]

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


I added a 2 byte 'weeks since 2013-01-01' field and updated the prefixes, ranges and test vectors.

The updated proposal lives here:
https://bitcointalk.org/index.php?topic=258678

Cheers,

jp

On Jul 22, 2013, at 06:14 AM, Mike Hearn <mike@plan99.net> wrote:

This isn't usable for SPV wallets unless it has a birthday in it. Otherwise you either need to scan the entire chain (slow) or find a fully indexed copy of the block chain (expensive, more centralised). Just add a UNIX time as an extra 4 bytes, or if you want to save a few characters then use a uint16 that represents "days since birth of this specification".

[-- Attachment #2.1: Type: text/html, Size: 933 bytes --]

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet master seed with optional encryption

[Gregory Maxwell]

On Mon, Jul 22, 2013 at 2:37 PM, Jean-Paul Kogelman
<jeanpaulkogelman@me.com> wrote:
>
> I added a 2 byte 'weeks since 2013-01-01' field and updated the prefixes,
> ranges and test vectors.
>
> The updated proposal lives here:
> https://bitcointalk.org/index.php?topic=258678

Greetings.  Any recent progress on this?

Do we believe this proposal can replace BIP38?  If not, what are the
limitations that would prevent it from doing so?

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet master seed with optional encryption

[Jean-Paul Kogelman]

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


I've made no changes since the last time I've mentioned it here on the list (when the BIP procedures were being discussed).

The last changes are:

01-10-2013 - Expanded the salt to be prefix + date + checksum and renamed 'master seed' to 'root key'.
24-07-2013 - Added user selectable KDF + parameters, encoded in the prefix.
22-07-2013 - Added 2 byte creation date field, as a result, the prefix is expanded to 3 bytes.

The biggest difference between this proposal and BIP38 is that BIP38 allows a 3rd party to generate the encrypted private key + confirmation code from a passphrase code. Since this proposal is about encrypting a random value that's fed into HMAC-SHA512 and the presence of a partial hash of the root address, that's not possible.




>> https://bitcointalk.org/index.php?topic=258678
> 
> Greetings.  Any recent progress on this?
> 
> Do we believe this proposal can replace BIP38?  If not, what are the
> limitations that would prevent it from doing so?


[-- Attachment #1.2: Type: text/html, Size: 1590 bytes --]

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 842 bytes --]

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet master seed with optional encryption

[Jean-Paul Kogelman]

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

Merry Christmas everyone!

I've updated the proposal.

I've changed the checksum to be a double SHA256 of the private key instead of the public address string and I've added support for 3rd party KDF computation.

The full proposal with updated test vectors lives here:

https://bitcointalk.org/index.php?topic=258678

Cheers,

Jean-Paul

[-- Attachment #1.2: Type: text/html, Size: 1141 bytes --]

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 842 bytes --]

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Jean-Paul Kogelman]

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

Hi everyone,

We've been hard at work updating the spec to include features that were requested. We've removed the Scrypt dependency that was present in the initial drafts, added new KDFs, added plausible deniability and have a reference implementation.


Kind regards,


Jean-Paul Kogelman


---

Recent changes:

15-02-2014 - Updated wording of various parts.
06-02-2014 - Added Will Yager's implementation as reference.
05-02-2014 - Changed prefix to 2 bytes, 'RK' and 'rk' for clear version and encrypted version respectively.
05-02-2014 - Added entropy field to encrypted version, moved KDF field from prefix into entropy field.
05-02-2014 - Changed computation of H to use PBKDF2-HMAC-SHA512 instead of Scrypt.
05-02-2014 - Changed checksum field to bloom field in encrypted version. Now supports 2 passwords.
27-12-2013 - Added some clarifications such as password character set (UTF-8) and endianness of fields.
26-12-2013 - Changed checksum to double SHA256 of private key, added 3rd party KDF support.
01-10-2013 - Expanded the salt to be prefix + date + checksum and renamed 'master seed' to 'root key'.
24-07-2013 - Added user selectable KDF + parameters, encoded in the prefix.
22-07-2013 - Added 2 byte creation date field, as a result, the prefix is expanded to 3 bytes.


BIP: 
Title: Base58 encoded HD Wallet root key with optional encryption
Author: Jean-Paul Kogelman
Status: Draft
Type: Informational
Created: 18-07-2013

Abstract

This proposal describes a method for encoding and optionally encrypting a Bitcoin Hierarchical Deterministic (HD) Wallet root key. Encoded root keys are intended for use on paper wallets. Each string contains all the information needed to verify and reconstitute an HD wallet except for the optional passphrases. The encrypted version uses salting and a user selectable key derivation function (KDF) + parameters to resist brute-force attacks at varying degrees and optionally a second password for plausible deniability.

The method provides two encoding methodologies in 3 lengths each (16, 32 and 64 byte root keys). One is a clear version of the root key with verification information for integrity checking and the other is an encrypted representation.

Additionally a 2 byte compressed date field is present to limit the block chain rescan on wallet import.


Motivation

The extended private keys proposed in BIP 0032 are long, fixed length records and don't offer any form of security. The root key used to generate the HD wallet is typically shorter than the extended master private key that results from it. 

A compact representation of the root key is easier to handle and a 2-factor version of the root key record allows for safe storage and the creation of paper wallets by 3rd parties. The KDF and its parameters are user selectable, allowing for a varying level of resistance against brute force attacks. This proposal currently defines 5 sets of parameters with room for 27 more that can be defined at a later date. Implementors are advised to contact the author with new KDF proposals.

Copyright

This proposal is hereby placed in the public domain.

Rationale

User story: As a Bitcoin user who uses HD wallets, I would like the ability to store my wallet root key in a compact form as a paper wallet.

User story: As a Bitcoin user who uses HD wallets, I would like the ability to have a 3rd party create a paper wallet with my root key in it, without having access to the funds stored in the wallet.

User story: As a Bitcoin user who uses HD wallets, I would like the ability to choose the strength of the root key depending on my security requirements and how I wish to store it. 

User story: As a Bitcoin user who uses HD wallets, I would like the ability to import a root key into a simplified payment verification (SPV) client without having to redownload the entire block chain, but rater a limited range, to find associated transactions.

User story: As a Bitcoin user who uses HD wallets, I would like to choose the KDF and its parameters that is used to hash the passphrase that protects my root key to fit my security needs and available processing power. 

User story: As a Bitcoin user who uses HD wallets, I would like to outsource the KDF computation to a 3rd party with more processing power.

User story: As a Bitcoin user who uses HD wallets, I would like to have a second password that can decrypt a second root key.

Specification

This proposal makes use of the following functions and definitions:

All input/output text is to be UTF-8 encoded

AES256Encrypt, AES256Decrypt: The AES block cipher, applied in ECB mode.

SHA256, SHA512: The hash algorithms of the same name. 

HMAC-SHA512: The HMAC message authentication code algorithm, using SHA512 as the hash function

PBKDF2-HMAC-SHA512: The PBKDF2 key derivation algorithm, described in PKCS #5 v2.0 and RFC 2898, using HMAC-SHA512 as the pseudorandom function

Scrypt: The key stretching algorithm of the same name

Base58Check: The textual data encoding frequently used by various Bitcoin-related systems

"Root Key": The 16/32/64 byte value encoded in the wallet. This value is used to derive the private keys for addresses in the Bitcoin Wallet

"Master Key": The primary Bitcoin private key, which is derived from the Root Key

"||" refers to concatenation, not the logical OR operation

"G", "N": Constants defined as part of the secp256k1 elliptic curve. G is an elliptic curve point, and N is a large positive integer.

Prefix

The Base58Check representation of the wallet will start with "RK" (Root Key) if the wallet is unencrypted, and will start with "rk" if the wallet is encrypted.

Proposed specification

Unencrypted wallet:

Prefixes:
0x28C1: 16 byte root key, no encryption. 24 byte total length
0x4AC5: 32 byte root key, no encryption. 40 byte total length
0xFBB3: 64 byte root key, no encryption. 72 byte total length

These are constant bytes that appear at the beginning of the Base58Check-encoded record, and their presence causes the resulting string to have a predictable prefix.

"date" is a 2-byte, little endian field containing the number of weeks since jan 1st 2013. It is used to optimize blockchain scan upon wallet import.

"checksum" is the first 4 bytes of SHA256(SHA256(master_secret)), where master_secret is the "Master Secret Key (IL)" from the BIP32 specification. In other words, "checksum"=SHA256(SHA256(HMAC-SHA512("Bitcoin seed", root_key)[0:32]))[0:4].

"root_key" is the 16/32/64 byte root key used for the HD wallet

In summary, the clear wallet looks like this:
[prefix, 2 bytes][date, 2 bytes][checksum, 4 bytes][root_key, 16/32/64 bytes]

Range in Base58Check encoding for clear 16 byte root key (prefix RK):
Minimum value: RK52zvuD3xRhwto8JDTonxhru6awsFfNqKCTmT (based on 0x28 0xC1 plus twenty-two 0x00's)
Maximum value: RKCsfF9RpLnrxo1kp2o7mfWYeAV1NNYxWSMRym (based on 0x28 0xC1 plus twenty-two 0xFF's)

Range in Base58Check encoding for clear 32 byte root key (prefix RK):
Minimum value: RK15fXAj9BEMooghtx2gY5YrSh23LYKS8mZnaz8oYf1EDnqAwtAADGMVUDHG (based on 0x4A 0xC5 plus thirty-eight 0x00's)
Maximum value: RK5MUEoFU24QARcsX5HR2ieCjem468hDeQm4J2aH5zsCVJXUCGn6nsVQEFhN (based on 0x4A 0xC5 plus thirty-eight 0xFF's)

Range in Base58Check encoding for clear 64 byte root key (prefix RK):
Minimum value: RK1uXsCQAKqaa2s7YBDeaLS2KTqZcNjjQSgdSfDv4fqGkTw8KBfZ2ND4Cp7vHdzhjJ2C2Jtf4CwgScRnXvpzuQT2W4Vj2SgCyfBgpTzF (based on 0xFB 0xB3 plus seventy 0x00's)
Maximum value: RK3B9TMn55dey3an1oHpwB81FPZboakivYtqFvCaeknPzPK4iTvoFKzxVWKcD9YfJwjkyS36bqnSqjibUurcQ7J2EsQww5zPpJNzqjkw (based on 0xFB 0xB3 plus seventy 0xFF's)


Encrypted wallet:

Prefixes:

0xF83F: 16 byte root key, encrypted. 26 byte total length
0x6731: 32 byte root key, encrypted. 43 byte total length
0x4EB4: 64 byte root key, encrypted. 76 byte total length

These are constant bytes that appear at the beginning of the Base58Check-encoded record, and their presence causes the resulting string to have a predictable prefix.

"date" is a 2-byte, little endian field containing the number of weeks since jan 1st 2013. It is used to optimize blockchain scan upon wallet import. The maximum value of 0xFFFF results in: jan 1st 3269

"entropy" is a 2/3/4 byte (corresponding to whether the key is 16/32/64 bytes) field. The first five bits contain the KDF type, and all other bits contain random data. This is used as a salt to make cracking the wallet password harder.

"bloom_filter" is a 4 byte little-endian field containing a bloom filter to check that the user entered their password correctly.

"encrypted_root_key" is the 16/32/64 byte encrypted root key used for the HD wallet

In summary, the encrypted wallet looks like this:
[prefix, 2 bytes][date, 2 bytes][entropy, 2/3/4 bytes][bloom_filter, 4 bytes][encrypted_root_key, 16/32/64 bytes]


Range in Base58Check encoding for encrypted 16 byte root key (prefix rk):
Minimum value: rk2V4R2ys91WigNPL5nots6a97rfMnwTkPAb2XgNo (based on 0xF8 0x3F plus twenty-four 0x00's)
Maximum value: rk57mv9oertBLsHfncAvqnbetCBdNS1gFHQaFsD3p (based on 0xF8 0x3F plus twenty-four 0xFF's)

Range in Base58Check encoding for encrypted 32 byte root key (prefix rk):
Minimum value: rk1CYsqKjsbXa7uvncEaW4XSeVzcpq1U9yDMxd2cWwfkGf1FMjENaVThYpLRNwqo (based on 0x67 0x31 plus fourty-one 0x00's)
Maximum value: rk7Xw5b6fidaCk489LhaiMqHkZo7RYGTmzvJY9A5joxe8KXAn8BC66cmQPYYYvy8 (based on 0x67 0x31 plus fourty-one 0xFF's)

Range in Base58Check encoding for encrypted 64 byte root key (prefix rk):
Minimum value: rk48BmQWeQbATSXbP5U6XVsXRJTs4Ea1TVZBbHLPPsboCFyxDj2Jaz2JAJno97hq6dq2bANLuWydY8QSZgKVGhPRZazXt1swPXwzVLw1QnVAz (based on 0x4E 0xB4 plus seventy-four 0x00's)
Maximum value: rkCRtT9R9kuAapCaLQFif5uo8gUrjgKsvYmGGTpX2ZTjTfwe9M7A6KezTh7f4FDxfZFVbHypodMNnNdmWYb8mzTokHXVR1u7KicrLLFFu7GJW (based on 0x4E 0xB4 plus seventy-four 0xFF's)


Encoding of KDF + parameters:

A number of KDF functions are available, to accommodate a wide range of possible use cases. The KDFs are defined as follows:

ID	KDF	Parameters
0x00	scrypt	n = 2^14, r = 8, p = 8
0x01	scrypt	n = 2^16, r = 16, p = 16
0x02	scrypt	n = 2^18, r = 16, p = 16
0x08	PBKDF2-HMAC-SHA512	iterations = 216
0x09	PBKDF2-HMAC-SHA512	iterations = 221

All other possible values (3-7 and 10-31) are reserved.

Please note that KDFs 1 and 2 will probably not run on mobile devices. KDFs 8 and 9 are very memory efficient.

Generation of date:

The purpose of the date field is to make scanning the blockchain for transactions to/from this wallet faster. The date *must* be on or before the date of the first transaction to/from the wallet. If the date is unknown (e.g. on an embedded device) or the user does not wish to reveal the wallet creation date, this field can be set to zero (which may incur a performance penalty for the wallet software). When importing, it is advised to start scanning from a few days before the encoded date. The date field is a little-endian integer containing the number of weeks, rounded down, since Jan 1st 2013. 

Examples: 

sep 18th 2013 - jan 1st 2013 =  260 days =  37 weeks 1 day = rounded down becomes 0x0025
mar  3rd 2027 - jan 1st 2013 = 5174 days = 739 weeks 1 day = rounded down becomes 0x02E3

Derivation of Master Key from Root Key (please see BIP 0032 for a full description of HD wallets):

1. Take 16/32/64 byte Root Key. Call it S
2. Calculate I = HMAC-SHA512(key = "Bitcoin seed", msg = S)
3. Let IL = I[0:32]. IL is the Master Key
4. If IL is 0 or IL >= N, where N is the curve order of Secp256k1 (the elliptic curve used by Bitcoin), the Root Key is invalid and a new one should be chosen.

Encryption:

Let "passphrase" be the user's chosen passphrase
Let "fake_passphrase" be the user's chosen second passphrase, or a randomly generated string if the user chose not to use a second passphrase
Let "KDF" be the chosen key derivation function
Let "root_key" be the 16/32/64 byte Root Key

1. Create the correct "Prefix" and "Date" field
2. Create the random "Entropy" field and encode the KDF number in the top 5 bits
3. Let "salt" = Prefix || Date || Entropy
4. Calculate "preH" = HMAC-SHA512(key = salt, msg = passphrase)
5. Calculate "strongH" = KDF(msg = preH, salt = preH, output_len = 64) This step can be outsourced to a 3rd party, if desired.
6. Calculate "postH" = HMAC-SHA512(key = passphrase, msg = salt)
7. Calculate "H" = PBKDF-HMAC-SHA512(msg = postH, salt = strongH, iterations = 210, output_len = len(root_key) + 32)
8. Calculate "whitened_key" = root_key XOR H[0:len(root_key)]
9. Calculate "encrypted_key" = AES256Encrypt(message = whitened_key, key = HR), where HR is the last 32 bytes of H
10. Calculate "fake_key" by decrypting encrypted_key with fake_passphrase
11. Calculate "bloom_filter", containing root_key and fake_key. See the "Bloom Filter" section for more info.

encrypted_wallet = Prefix || Date || Entropy || bloom_filter || encrypted_key

Decryption of Root Key:

Let "passphrase" be the passphrase provided by the user

1. Extract "Prefix", "Date", "Entropy", "bloom_filter", and "encrypted_key" from the encrypted wallet
2. Determine the correct KDF from the top 5 bits of Entropy.
3. Let "salt" = Prefix || Date || Entropy
4. Perform steps 4 through 7 of Encryption to derive "H"
5. Calculate "whitened_key" = AES256Decrypt(message = encrypted_key, key = HR), where HR is the last 32 bytes of H
6. Calculate "root_key" = whitened_key XOR H[0:len(whitened_key)]
7. Verify that root_key is a member of bloom_filter

Bloom Filter:

The Bloom Filter is a data structure that allows us to check, within a range of probability, whether or not some piece of data has been added to it. In this case, we want to make sure that the user entered their password correctly, so we're checking that the decrypted root_key corresponds to the one that was added to the bloom filter when the wallet was created.

Bloom Filter Creation:

1. Let "bloom_filter" be an empty (set to all zeros) 32-bit, little-endian integer
2. To add an element "X" to bloom_filter, 
3. Calculate "E" = SHA256(SHA256(HMAC-SHA512("Bitcoin seed", X)[0:32]))[0:11]. Note, this corresponds to the same algorithm used as a checksum for un-encrypted wallets. It also corresponds to the double-SHA of the Master Key.
4. For each of the 11 bytes in E (call each byte "B"):
4a.   calculate "N" = B & 0x1F. N will range from 0 to 31. Set the Nth bit in bloom_filter to 1

You can add more items to the bloom filter, if desired. However, the filter parameters are optimized for 2 items (one "real" password/wallet, and one "fake" password/wallet). Please note that adding more items will drastically increase the chance of a false positive when entering a password. The chance of a password similar to a correct password passing the filter becomes more likely. This will generate a different Root Key and not the original one the user intended to decrypt.

Bloom Filter Verification:

Let "X" be some item
Let "bloom_filter" be the Bloom Filter you want to check if X belongs to

1. Calculate "x_only_filter", which is a Bloom Filter with X added to it
2. Ensure that any bit that is set in x_only_filter is also set in bloom_filter (i.e. x_only_filter & bloom_filter == x_only_filter)
3. If all bits set in x_only_filter are also set in bloom_filter, you know X is probably a member of bloom_filter. If not, X is definitely *not* a member of bloom_filter.

Suggestions for implementers of proposal with alt-chains

This proposal is network and coin agnostic (so long as the coin in question uses SECP256K1 ECC). Alt-coin implementors are advised to change the prefixes so that encoded root keys do not start with “RK" or “rk”.

Reference implementation

Python reference implementation: https://github.com/wyager/Encrypted-HD-wallet

Acknowledgements

Will Yager for the Python reference implementation and rewording of parts of this specification.
Mike Caldwell for BIP 0038, which this proposal borrows heavily from.

See Also

BIP 0032 Hierarchical Deterministic Wallets: https://en.bitcoin.it/wiki/BIP_0032
BIP 0038 Passphrase-protected private key: https://en.bitcoin.it/wiki/BIP_0038

Test vectors

The primary password will always decrypt the same root key, regardless of KDF selection, however, the secondary password will generate a different root key for every KDF.

Test 1:

Root Key	000102030405060708090a0b0c0d0e0f
Creation	04-02-2014
Clear	RK6nEaou4eFQC4SfrHtdh9jpnEme4K9dt2jBmG
Password	Satoshi
Public Address	15mKKb2eos1hWa6tisdPwwDC1a5J1y9nma
Private extended key	xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6LnF5kejMRNNU3TGtRBeJgk33yuGBxrMPHi
Public extended key	xpub661MyMwAqRbcFtXgS5sYJABqqG9YLmC4Q1Rdap9gSE8NqtwybGhePY2gZ29ESFjqJoCu1Rupje8YtGqsefD265TMg7usUDFdp6W1EGMcet8
Second password	Alpaca
Encrypted (KDF0)	rk354bXH1JsXTwWmuvRskFWoeUX8hMjQiseNM7wj6
Public Address	1Ndr6DnQm5EefVhTdKjXC3vH5qGRa1FCng
Private extended key	xprv9s21ZrQH143K3TxQaa6hd8mPR9Bw2ue1H5TMjUYuUEPEDUTxK7PZ191poMob8zbU5hsckCQoBFYtQZzbgxtYz1acbLmFQtjcbWSYhQ7kSZE
Public extended key	xpub661MyMwAqRbcFx2sgbdhzGi7yB2RSNMreJNxXrxX2ZvD6Go6rehoYwLJecVAuhHhMPSuMStnLHbzQ4CCyPqbVyLP4F2SmiLTcE3oicmA81M
Encrypted (KDF1)	rk354bq4dXW8VB67XSZzQdVLFJFz64v1Dh1i12VTY
Public Address	12cbi9vTjpZ8RjinLc2fJp1iDkL96xMQoe
Private extended key	xprv9s21ZrQH143K4JxBYKwi5dGE59G4vtRGLiyinEPxMdgYdPe6UqMrgJneacME8JQuoskvEzEZ1vnHwW8i1h4Mwm5wj5BUPJWf764QfkkvFAQ
Public extended key	xpub661MyMwAqRbcGo2eeMUiSmCxdB6ZLM97hwuKacoZuyDXWByF2Ng7E778RrYidat9n9Ht5cYrdS4gwVBA2g8VHAro7b4Gbvo2NKTLP9STuvP
Encrypted (KDF8)	rk354dUN5yrKvrMQRneKJvdJFf77WDJw5ZfeeRt4H
Public Address	14z6Vm4TRxd9ueasFahwBxYJ8jfhwhX4bt
Private extended key	xprv9s21ZrQH143K2AaodGyHvDBQFrFcDdHVJj15zqJUkU1wuLS5kFxgE9rGBvh8rAUeenfhhwC91efxn8kHbhKGeTaQkkyGFvbKiAuLcx8t8qP
Public extended key	xpub661MyMwAqRbcEefGjJWJHM88ot66d61LfwvgoDi6JoYvn8mEHoGvmxAk3DfcWWuDBqMUmPoXA28pa2uMnQFxKQe21Df5uQAGADCpcdZHAGe
Encrypted (KDF9)	rk354dedikaytYJ7D4btpcVfGuakfixf5yj2SnTcX
Public Address	17tzY2huzjbcRNV7e7BshxQ8UPrZhznBgn
Private extended key	xprv9s21ZrQH143K3Xt1wRGXFZ6D76dGLyGTWxvPv1QhkRcyPCbi6kM7WJG9dH6X9UMmzoTwoix3BsnzKf7ZkkpinPw8hyGaNLWzmcbemJVUWTj
Public extended key	xpub661MyMwAqRbcG1xV3SoXch2wf8TkkRzJtBqziPpKJm9xFzvreHfN46adUXfeFiVokTrKsBvK3zBgDJcUThjDtXAZ2dw9SYg74YMFjENB4aa

Test 2:

Root Key	7f0ad7d595be13e6fe4cf1fa0fbb6ae9c26c5d9b09920709414982b6363d5844
Creation	04-02-2014
Clear	RK22qqMb3CozsQfTTbSVsLEgXcjekut99SuSHn6urU4vWxjiQneHWVYabWgv
Password	Nakamoto
Public Address	1A54ECavJaJAoLGqqNrPd9Y3cvSvkL2Roz
Private extended key	xprv9s21ZrQH143K3f9hMVvcbY4EX4CfxsEtc6C5BMkZtgGpTGpxAscoq7SLSAcL6k5dxaZ9s4SChrtfSFoKpijuwAnhuPn76eva6W8bDr118t3
Public extended key	xpub661MyMwAqRbcG9EATXTcxfzy563ANKxjyK7fykABT1ooL5A6iQw4NukpHShDxYgeso4NHscFmqcVEtdUt61c8RCf7FqXK9z6sgfkQvYBQPP
Second password	hunter2
Encrypted (KDF0)	rk2cMHki73WbrYgo7XK9kSr6CGBPsMjU3uZf3f3qxCv4QoGy63DkBoGJKhPdvUtp
Public Address	16UCUo31Y7qDMWSs68FBAW759X4K3PZ9kN
Private extended key	xprv9s21ZrQH143K2dojoDyxmK7SLnyqSvn56oysqu2Ctf24Rdux6JFLReRgcH5KAM1GxCTVxjpc13Mh18kSmYqUep5EkbDvQJfEEVeLZXhyuYj
Public extended key	xpub661MyMwAqRbcF7tCuFWy8T4AtppKrPVvU2uUeHRpSzZ3JSF6dqZaySkATZEZWFcAMxqhD7oTdcaufofFy1WGLF7U21rztvTv6qmGrPq7s2W
Encrypted (KDF1)	rk2cMJ1KizRTPbBv8zaECpcQEY66SiZcfM2yAuCpdjDbJsdgZu9xdoFDpGuTVRYe
Public Address	15PXuaVAiU2fEEAsUjxWYHtzoM4D6FaC5F
Private extended key	xprv9s21ZrQH143K35ajB7SFjQJAzrmGbAJyp7iBYxhB3DcY9CC8XW5GkAHXDe2HXG6hUS3iquPbGAPuZygXm43BgYamWxiDN5sFm7w12db4uvU
Public extended key	xpub661MyMwAqRbcFZfCH8yG6YEuYtbkzd2qBLdnMM6nbZ9X1zXH53PXHxc14vcMHtfJRGTZVgj2gz8sc6sUuYoFub9HaBzkfaxguH4Byqo9NhK
Encrypted (KDF8)	rk2cMNSiQsAATQ19Y12nhGuL2uksZVASxNXAdjqrU3KaVcLH71No442sH1YvcwDL
Public Address	13jQ3pnGznGNTC2LVxJz1m27opav8WPVvH
Private extended key	xprv9s21ZrQH143K3aA9djUAAX1ASAcdqtuHEXmypDNd8gNy5PH4nm7y4QrieVdw7iQgA46LCJJAxdcN4qrP87Tp8XzJQbw7aeH3LPK8G7Zj6YT
Public extended key	xpub661MyMwAqRbcG4Ecjm1AXewtzCT8FMd8bkhacbnEh1uwxBcDLJSDcDBCVnvvrsENPhxpCZ3FYVokSvwfJJFVU9KF3ctQQJp229pgcFLavKJ
Encrypted (KDF9)	rk2cMPALytexkDuxm6QREojvgzoKcgKNeURPXDTVzPdZmbfzM2R3RX75Qqu4Yk5r
Public Address	1NBQsYC1vhfbkEoiPWmUb1QN36cCsMxcti
Private extended key	xprv9s21ZrQH143K4X6wJWAQbDawhqb2DaQT7mjbPhqNBHmspzrD1J5kcnb5syHr9LQggN3PtmvkjbMVs4zgTyjWmqKS4ix7J92z59cvbkF5W1s
Public extended key	xpub661MyMwAqRbcH1BQQXhQxMXgFsRWd38JUzfCC6EyjdJrhoBMYqQ1AauZjGev413kscEPLn4s3XmiDoL1pevGUKACx5ZhhPHvujKaVpe5TRt

Test 3:

Root Key	fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8 a8784817e7b7875726f6c696663605d5a5754514e4b484542
Creation	04-02-2014
Clear	RK2BvY13FUD6bX25tA7XDyfAn7zbXSL8pR6TRE3EHZZ8qBm9qEyZRih8x1XhhcZwjcTfpe1Qjydn4KU dia8Wf1NshUusP1D38i88MLU9
Password	Vires In Numeris
Public Address	1JEoxevbLLG8cVqeoGKQiAwoWbNYSUyYjg
Private extended key	xprv9s21ZrQH143K31xYSDQpPDxsXRTUcvj2iNHm5NUtrGiGG5e2DtALGdso3pGz6ssrdK4PFmM8NSpSBHNqPqm55Qn3LqFtT2emdEXVYsCzC2U
Public extended key	xpub661MyMwAqRbcFW31YEwpkMuc5THy2PSt5bDMsktWQcFF8syAmRUapSCGu8ED9W6oDMSgv6Zz8idoc4a6mr8BDzTJY47LJhkJ8UB7WEGuduB
Second password	Quis Custodiet Ipsos Custodes?
Encrypted (KDF0)	rk5ySVmNtFzgWZFXAehk6Akvf5PanApA5Y12arynxXZF7Lhc1YqaudukJFngEBXkpc4RGqqkM3ZW4RjE7HwhWTB5Uxi7pXy7vuKouQuZZzoTP
Public Address	1AbB8okTm3SgcHnqKskQFfBd1MndDq1G75
Private extended key	xprv9s21ZrQH143K4PUz4iSDMmUE9uovNGnZE6jZdKPDqozk8nBHBk3FRXo3tJEt4TFfo7Tkhnc9TAzUFvg7hsg7M1SddHF6nX9bBw9Tn968Aki
Public extended key	xpub661MyMwAqRbcGsZTAjyDiuQxhweQmjWQbKfARhnqQ9Xj1aWRjHMVyL7XjaDV9SNrb7S8YvGtTGUkrRLS3kTDbRKRq26khyJDyKDuquaBqRM
Encrypted (KDF1)	rk5ySWZriEipJWKyL6X8Rd86cgKn9qgGC7C4QYLVCjhyuBZiKXezzf6vjyJBXtFmP1f4qzaAAP5baRhKP4yCGo6LAU9keJCvRXoU77SUNmg1o
Public Address	1Fzh1NoMtYUBAoKQ2Lsb6rA81bKFfNx2az
Private extended key	xprv9s21ZrQH143K4KmLN9WLjPsVmKgVXPUfAScqkGeifQpTeXFw2X4ijfWNMDMtu4qfbbHZ69VSLcCMiGLHSLaQQY7Rb3PzHMRLLqVN6mjrGHP
Public extended key	xpub661MyMwAqRbcGoqoUB3M6XpEKMWyvrCWXfYSYf4LDkMSXKb5a4NyHTprCW3JAJ66rn947iM9iyzUoS4CSXhsDZyuaks5hueT9wtDSdm91ga
Encrypted (KDF8)	rk5ySbwggFoh8MZ1CnxqSeKwzag9ifrECtToowiRYKRgcueyMGX39yBGwxbY7ExKeTSmCRHokToThN8pxYWA9WQKrouVuatCMjcvX8PZ16tPf
Public Address	1AiALvRHrWwjViJn5Q6oki4qVZ5p7SepfB
Private extended key	xprv9s21ZrQH143K3CHptaD7aNZBUAYhjmCe5ceDLttwqKoQ3F73DRHNrSAVphAX2okZDWK82Eznf4bpmv9qjHZ7nzQjv2qNqXV8YwCWQEw2jiA
Public extended key	xpub661MyMwAqRbcFgNHzbk7wWVv2CPC9DvVSqZp9HJZPfLNv3SBkxbdQEUyfwf9rtzBwBvKTV2WDejdPupDmihidJmDTTgXpar3r48kNiGhEzC
Encrypted (KDF9)	rk5ySd2iHrVJ1CZ86Pyt6zerNzzBHfZo2rcBAX4MKNzX7doCZnNpBMc3pPf6igTCnk796isqtaEdcfagrN8Pced9VAtENVBtpugBLnjiGd28h
Public Address	1Gazv3FH8oDxUUzgrRmWL14X3oBY5myDdQ
Private extended key	xprv9s21ZrQH143K3YMD7T6LoFVGttrMKj9jxGAxfCv3pv6ZQfWcuBV5pqdcjyooGrqa8NeraYUuiTWJSWuz4fVMiCuEK8tWggZ6yMZZK7xLBkx
Public extended key	xpub661MyMwAqRbcG2RgDUdMAPS1SvgqjBsbKV6ZTbKfPFdYHTqmSioLNdx6bH6v4uA4MWygDxbDDbVGPCurrTm5RwMnh14jEaswhA6nFK1bFd2

Test 4:

Root Key	6ca4a27ac660c683340f59353b1375a9
Creation	04-02-2014
Clear	RK6nEmXZj2nqgtCVWk3s7Suvz2XtWrdhDPpJqS
Password	聡中本
Public Address	1JVncPbsdB2s4zHim3VdAWNkZ8JANBZ1U9
Private extended key	xprv9s21ZrQH143K3mJ4upPSDfXdA34yNjem6PSsXT63vm8dq8ikUJv4iiTD3PrSKtdGZXFVD689z5T7knXo55BjcHS2WL3Syp2DbGgnbgxw2QA
Public extended key	xpub661MyMwAqRbcGFNY1qvSaoUMi4uTnCNcTcNUKqVfV6fchw3u1rEKGWmgtfUMRKLgUHNZ7dfsh8Ys6SLwUojZqScFBQL3dFGF3QywNLJVZ2o
Second password	Bitcoin
Encrypted (KDF0)	rk354bYQBax15mmBSLTpaVuLRb9nDuaVbEseqBWpG
Public Address	1AGXnLksHQgovEyQvj8kY9QtFV2x8D1Nm
Private extended key	xprv9s21ZrQH143K3BMoPfivq74do9mxCnKRTZHWScTvVyrxGtCNvGd8bCZJk1Npwnds3ghiy4TTwmwtbSkpzTFcqLup57AWqm3NvRr6sNs7ZVt
Public extended key	xpub661MyMwAqRbcFfSGVhFwCF1NMBcScF3GpnD7EzsY4KPw9gXXTowP8zsnbJTDhU9o9Sj9M63Qx6bZhZ7gS6AzNjNehPUbqdhc6th1VA1FGVg
Encrypted (KDF1)	rk354bi6JiGeb5suvydsNtTosocEbpWcjoK7VL9Xv
Public Address	1DkoSDVN7aYZnGe3wUCXAjqc3cXT9oiHhG
Private extended key	xprv9s21ZrQH143K2Su2mQR7u6pweA8kwv4y3bKkvUeJUanC4eT7VVp64VxNH5uzwY12wE315rZMMf5XJQLcNLPBF7zcgoFv29UM3R9ctDqdshr
Public extended key	xpub661MyMwAqRbcEvyVsRx8GEmgCByFMNnpQpFMis3v2vKAwSnG338LcJGr8NDyhCcF7QV65cmybwrhCkYre87pkG3NCpckbc2itaJknWnwGGX
Encrypted (KDF8)	rk354dLtDHN3mPNSFABTNrhKmweKPZ55LJ31EM3k6
Public Address	1QShZTrKPJPBcstuYX5JKRHPs1HUtD7y8
Private extended key	xprv9s21ZrQH143K43FPi9awkCScXaAY4mEJje4PhS5uk2R67QU6p7bHXbvwgRdcwU9xZozYZ9hqfjm6ccAbGgU5eN4fp7uMY59MGq8swJVQPKW
Public extended key	xpub661MyMwAqRbcGXKrpB7x7LPM5c12UDxA6ryzVpVXJMx4zCoFMeuY5QFRXfg1tnVaP3Fv1tmhoV8jrRG29Gip9FwW7j3vGLNneaMepS1QuHP
Encrypted (KDF9)	rk354diEYQb4EdNjyosAZGNAB8L1spefWdz7RmZfX
Public Address	1NLVhK8AQn7p2edvTtFJgTz6itrBeHZ4Wa
Private extended key	xprv9s21ZrQH143K2stwSFWe4rPabNH1k1EVwQKwr7poayVZNPJup716aWVjDBVRVRh8gSgZhTP4uiaNuCkFbXXJCbDSnmvwNbnCuvQqHDDj7Ew
Public extended key	xpub661MyMwAqRbcFMyQYH3eRzLK9Q7W9TxMJdFYeWER9K2YFBe4MeKM8JpD4RrrKNRrTMT9T7FvDbvWhzAXT68HxuyZGJ9BkC6G3ZiMjj1UT76


[-- Attachment #1.2: Type: text/html, Size: 36057 bytes --]

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 842 bytes --]

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Pavol Rusnak]

On 03/12/2014 04:17 AM, Jean-Paul Kogelman wrote:
> We've been hard at work updating the spec to include features that were requested. We've removed the Scrypt dependency that was present in the initial drafts, added new KDFs, added plausible deniability and have a reference implementation.

Are you aware of BIP-0039?

https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki



-- 
Best Regards / S pozdravom,

Pavol Rusnak <stick@gk2.sk>

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Jean-Paul Kogelman]

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


On Mar 12, 2014, at 6:11 AM, Pavol Rusnak <stick@gk2.sk> wrote:

> On 03/12/2014 04:17 AM, Jean-Paul Kogelman wrote:
>> We've been hard at work updating the spec to include features that were requested. We've removed the Scrypt dependency that was present in the initial drafts, added new KDFs, added plausible deniability and have a reference implementation.
> 
> Are you aware of BIP-0039?
> 
> https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki
> 
> 

Yes I am. There are some differences between BIP 39 and my proposal though. 

- BIP 39 offers an easy list of words, no gnarly string of case sensitive letters and numbers.
- BIP 39 only offers one fixed length of entropy, always 12 words, no option to increase or decrease the length.
- BIP 39 doesn't have a genesis date field, so no optimization during blockchain rescan.
- BIP 39 doesn't have password typo detection. No easy way to recover a password if you know most of it.
- BIP 39 does not have a user selectable KDF, only 2048 round PBKDF2-HMAC-SHA512. 
- BIP 39 can't outsource the KDF computation to a 3rd party.
- BIP 39 wallet implementors can use their own word lists, breaking cross wallet compatibility.


jp

[-- Attachment #2: Message signed with OpenPGP using GPGMail --]
[-- Type: application/pgp-signature, Size: 842 bytes --]

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Pavol Rusnak]

On 03/12/2014 04:45 PM, Jean-Paul Kogelman wrote:
> Yes I am. There are some differences between BIP 39 and my proposal though. 
> 
> - BIP 39 offers an easy list of words, no gnarly string of case sensitive letters and numbers.

Which is better IMO. I can't imagine anyone writing down a long Base58
encoded string.

> - BIP 39 only offers one fixed length of entropy, always 12 words, no option to increase or decrease the length.

Not true, BIP39 supports 12/18/24 words (= 128/192/256 bits of entropy).

> - BIP 39 doesn't have a genesis date field, so no optimization during blockchain rescan.

This is nice addition, indeed. But we needed to limit the data as
possible in order not to increase the number of words needed to be noted
down.

> - BIP 39 doesn't have password typo detection. No easy way to recover a password if you know most of it.

It has a detection. Not correction though.

> - BIP 39 does not have a user selectable KDF, only 2048 round PBKDF2-HMAC-SHA512. 
> - BIP 39 can't outsource the KDF computation to a 3rd party.

True, but having one or two solid options are better than having
gazillions of possible options.

> - BIP 39 wallet implementors can use their own word lists, breaking cross wallet compatibility.

True, but they are encouraged to use the list provided. Possibility to
outsource KDF outside of your "standard" breaks much more compatibility
than this.

-- 
Best Regards / S pozdravom,

Pavol Rusnak <stick@gk2.sk>

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Gary Rowe]

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

Jean-Paul, it may be worth noting that the BIP39 word list is integrated
into Bitcoinj so will likely become the de facto standard for Android,
Trezor web and several desktop wallets. Anyone deviating from that word
list would likely find themselves in an isolated pocket.

Regarding the timestamp, MultiBit HD uses a simple timestamp of "number of
days since midnight of Bitcoin genesis block in UTC with modulo 97 checksum
appended". Thus a new seed generated on 27 January 2014 would have
"1850/01" as its checksum. When creating a new wallet the users are tested
that they have written the timestamp down along with the associated
12/18/24 words.

Modulo 97 was chosen since it catches about 99% of errors.


On 12 March 2014 15:55, Pavol Rusnak <stick@gk2.sk> wrote:

> On 03/12/2014 04:45 PM, Jean-Paul Kogelman wrote:
> > Yes I am. There are some differences between BIP 39 and my proposal
> though.
> >
> > - BIP 39 offers an easy list of words, no gnarly string of case
> sensitive letters and numbers.
>
> Which is better IMO. I can't imagine anyone writing down a long Base58
> encoded string.
>
> > - BIP 39 only offers one fixed length of entropy, always 12 words, no
> option to increase or decrease the length.
>
> Not true, BIP39 supports 12/18/24 words (= 128/192/256 bits of entropy).
>
> > - BIP 39 doesn't have a genesis date field, so no optimization during
> blockchain rescan.
>
> This is nice addition, indeed. But we needed to limit the data as
> possible in order not to increase the number of words needed to be noted
> down.
>
> > - BIP 39 doesn't have password typo detection. No easy way to recover a
> password if you know most of it.
>
> It has a detection. Not correction though.
>
> > - BIP 39 does not have a user selectable KDF, only 2048 round
> PBKDF2-HMAC-SHA512.
> > - BIP 39 can't outsource the KDF computation to a 3rd party.
>
> True, but having one or two solid options are better than having
> gazillions of possible options.
>
> > - BIP 39 wallet implementors can use their own word lists, breaking
> cross wallet compatibility.
>
> True, but they are encouraged to use the list provided. Possibility to
> outsource KDF outside of your "standard" breaks much more compatibility
> than this.
>
> --
> Best Regards / S pozdravom,
>
> Pavol Rusnak <stick@gk2.sk>
>
>
> ------------------------------------------------------------------------------
> Learn Graph Databases - Download FREE O'Reilly Book
> "Graph Databases" is the definitive new guide to graph databases and their
> applications. Written by three acclaimed leaders in the field,
> this first edition is now available. Download your free book today!
> http://p.sf.net/sfu/13534_NeoTech
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[William Yager]

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

This spec offers a lot of benefits over BIP 0038:

* Multiple KDFs (I think the chosen list is reasonable and fits all
required use cases)
* Multiple seed lengths
* Explicit BIP 0032 support
* Creation date field
* Plausible deniability (via the multiple-password mechanism)

I don't think it makes any sense to compare this to BIP 0039. BIP 0039 is
for key import/export, but it doesn't deal with anything like encryption,
wallet creation date, etc. The use cases are completely different.

I don't think we should let BIP 0039 (which is perfectly good for its
intended use case) hold us back from improving on BIP 0038 (which is also
good, but could use some changes).

Will




On Wed, Mar 12, 2014 at 11:49 AM, Gary Rowe <g.rowe@froot.co.uk> wrote:

> Jean-Paul, it may be worth noting that the BIP39 word list is integrated
> into Bitcoinj so will likely become the de facto standard for Android,
> Trezor web and several desktop wallets. Anyone deviating from that word
> list would likely find themselves in an isolated pocket.
>
> Regarding the timestamp, MultiBit HD uses a simple timestamp of "number of
> days since midnight of Bitcoin genesis block in UTC with modulo 97 checksum
> appended". Thus a new seed generated on 27 January 2014 would have
> "1850/01" as its checksum. When creating a new wallet the users are tested
> that they have written the timestamp down along with the associated
> 12/18/24 words.
>
> Modulo 97 was chosen since it catches about 99% of errors.
>
>
> On 12 March 2014 15:55, Pavol Rusnak <stick@gk2.sk> wrote:
>
>> On 03/12/2014 04:45 PM, Jean-Paul Kogelman wrote:
>> > Yes I am. There are some differences between BIP 39 and my proposal
>> though.
>> >
>> > - BIP 39 offers an easy list of words, no gnarly string of case
>> sensitive letters and numbers.
>>
>> Which is better IMO. I can't imagine anyone writing down a long Base58
>> encoded string.
>>
>> > - BIP 39 only offers one fixed length of entropy, always 12 words, no
>> option to increase or decrease the length.
>>
>> Not true, BIP39 supports 12/18/24 words (= 128/192/256 bits of entropy).
>>
>> > - BIP 39 doesn't have a genesis date field, so no optimization during
>> blockchain rescan.
>>
>> This is nice addition, indeed. But we needed to limit the data as
>> possible in order not to increase the number of words needed to be noted
>> down.
>>
>> > - BIP 39 doesn't have password typo detection. No easy way to recover a
>> password if you know most of it.
>>
>> It has a detection. Not correction though.
>>
>> > - BIP 39 does not have a user selectable KDF, only 2048 round
>> PBKDF2-HMAC-SHA512.
>> > - BIP 39 can't outsource the KDF computation to a 3rd party.
>>
>> True, but having one or two solid options are better than having
>> gazillions of possible options.
>>
>> > - BIP 39 wallet implementors can use their own word lists, breaking
>> cross wallet compatibility.
>>
>> True, but they are encouraged to use the list provided. Possibility to
>> outsource KDF outside of your "standard" breaks much more compatibility
>> than this.
>>
>> --
>> Best Regards / S pozdravom,
>>
>> Pavol Rusnak <stick@gk2.sk>
>>
>>
>> ------------------------------------------------------------------------------
>> Learn Graph Databases - Download FREE O'Reilly Book
>> "Graph Databases" is the definitive new guide to graph databases and their
>> applications. Written by three acclaimed leaders in the field,
>> this first edition is now available. Download your free book today!
>> http://p.sf.net/sfu/13534_NeoTech
>> _______________________________________________
>> Bitcoin-development mailing list
>> Bitcoin-development@lists.sourceforge.net
>> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>>
>
>
>
> ------------------------------------------------------------------------------
> Learn Graph Databases - Download FREE O'Reilly Book
> "Graph Databases" is the definitive new guide to graph databases and their
> applications. Written by three acclaimed leaders in the field,
> this first edition is now available. Download your free book today!
> http://p.sf.net/sfu/13534_NeoTech
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Jean-Paul Kogelman]

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



On Mar 12, 2014, at 08:55 AM, Pavol Rusnak <stick@gk2.sk> wrote:

On 03/12/2014 04:45 PM, Jean-Paul Kogelman wrote:
Yes I am. There are some differences between BIP 39 and my proposal though.
- BIP 39 offers an easy list of words, no gnarly string of case sensitive letters and numbers.

Which is better IMO. I can't imagine anyone writing down a long Base58
encoded string.
 
That depends on your use case. A list of words is totally fine for someone to write down, a long string of case sensitive letters is easier to put into a QR code.


- BIP 39 only offers one fixed length of entropy, always 12 words, no option to increase or decrease the length.

Not true, BIP39 supports 12/18/24 words (= 128/192/256 bits of entropy).
 
I stand corrected.


- BIP 39 doesn't have a genesis date field, so no optimization during blockchain rescan.

This is nice addition, indeed. But we needed to limit the data as
possible in order not to increase the number of words needed to be noted
down.
 
My proposal didn't have this either initially, but it was deemed an essential feature for SPV clients.


- BIP 39 doesn't have password typo detection. No easy way to recover a password if you know most of it.

It has a detection. Not correction though.
 
If I understand the code correctly (and please correct me if I'm wrong), the validation only happens on the mnemonic list, not on the password:

"Described method also provides plausible deniability, because every passphrase generates a valid seed (and thus deterministic wallet) but only the correct one will make the desired wallet available"

So upon entering a password with a typo, the user will not be notified of an error, but be presented with a wallet balance of 0, after the blockchain has been scanned. I'm sorry, but that's not the kind of experience I would want to present to my users.


- BIP 39 does not have a user selectable KDF, only 2048 round PBKDF2-HMAC-SHA512.
- BIP 39 can't outsource the KDF computation to a 3rd party.

True, but having one or two solid options are better than having
gazillions of possible options.
 
5 defined KDFs out of a possible 32 is hardly "gazillions".

- BIP 39 wallet implementors can use their own word lists, breaking cross wallet compatibility.

True, but they are encouraged to use the list provided. Possibility to
outsource KDF outside of your "standard" breaks much more compatibility
than this.
 
Would you care to elaborate how optional outsourcing of the KDF breaks compatibility?

jp


[-- Attachment #2.1: Type: text/html, Size: 4502 bytes --]

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Jean-Paul Kogelman]

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



On Mar 12, 2014, at 09:49 AM, Gary Rowe <g.rowe@froot.co.uk> wrote:

Jean-Paul, it may be worth noting that the BIP39 word list is integrated into Bitcoinj so will likely become the de facto standard for Android, Trezor web and several desktop wallets. Anyone deviating from that word list would likely find themselves in an isolated pocket.

Regarding the timestamp, MultiBit HD uses a simple timestamp of "number of days since midnight of Bitcoin genesis block in UTC with modulo 97 checksum appended". Thus a new seed generated on 27 January 2014 would have "1850/01" as its checksum.
 
I'm a bit confused, are you changing the way the checksum is calculated, or fudging the input seed to produce a specific checksum? Or is checksum in this case another value calculated over the mnemonic list?


When creating a new wallet the users are tested that they have written the timestamp down along with the associated 12/18/24 words.

So this is specific to MultiBit HD? Wouldn't it be better to include this into the BIP? 


[-- Attachment #2.1: Type: text/html, Size: 1423 bytes --]

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Pavol Rusnak]

On 03/12/2014 08:26 PM, Jean-Paul Kogelman wrote:
> So upon entering a password with a typo, the user will not be notified of an 
> error, but be presented with a wallet balance of 0, after the blockchain has 
> been scanned. I'm sorry, but that's not the kind of experience I would want to 
> present to my users.

Sure, you can have either plausible deniability or typo checking, not
both at the same time.

> Would you care to elaborate how optional outsourcing of the KDF breaks 
> compatibility?

I'm afraid one would end up with code generated in one client that is
unusable in a different client, because the client's developer thought
that using fancier algorithm instead of the proposed ones was a good idea.


-- 
Best Regards / S pozdravom,

Pavol Rusnak <stick@gk2.sk>

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Gary Rowe]

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

This is purely a MultiBit HD thing. Nothing to do with the BIP, unless the
wider community felt that it would be generally useful.

It has nothing to do with internal word list checking and is purely an
additional check to reduce the blockchain search load for SPV clients when
restoring wallets.


On 12 March 2014 19:35, Jean-Paul Kogelman <jeanpaulkogelman@me.com> wrote:

>
>
> On Mar 12, 2014, at 09:49 AM, Gary Rowe <g.rowe@froot.co.uk> wrote:
>
> Jean-Paul, it may be worth noting that the BIP39 word list is integrated
> into Bitcoinj so will likely become the de facto standard for Android,
> Trezor web and several desktop wallets. Anyone deviating from that word
> list would likely find themselves in an isolated pocket.
>
> Regarding the timestamp, MultiBit HD uses a simple timestamp of "number of
> days since midnight of Bitcoin genesis block in UTC with modulo 97 checksum
> appended". Thus a new seed generated on 27 January 2014 would have
> "1850/01" as its checksum.
>
>
> I'm a bit confused, are you changing the way the checksum is calculated,
> or fudging the input seed to produce a specific checksum? Or is checksum in
> this case another value calculated over the mnemonic list?
>
>
> When creating a new wallet the users are tested that they have written the
> timestamp down along with the associated 12/18/24 words.
>
>
> So this is specific to MultiBit HD? Wouldn't it be better to include this
> into the BIP?
>
>

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[William Yager]

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

On Wed, Mar 12, 2014 at 2:39 PM, Pavol Rusnak <stick@gk2.sk> wrote:

> On 03/12/2014 08:26 PM, Jean-Paul Kogelman wrote:
> > So upon entering a password with a typo, the user will not be notified
> of an
> > error, but be presented with a wallet balance of 0, after the blockchain
> has
> > been scanned. I'm sorry, but that's not the kind of experience I would
> want to
> > present to my users.
>
> Sure, you can have either plausible deniability or typo checking, not
> both at the same time.
>
>
The proposed BIP uses a bloom filter, so it has both plausible deniability *and
*typo checking. The bloom filter is optimized for two elements and will
catch something like 99.9975% of typos, despite allowing two different
passwords.

> Would you care to elaborate how optional outsourcing of the KDF breaks
> > compatibility?
>
> I'm afraid one would end up with code generated in one client that is
> unusable in a different client, because the client's developer thought
> that using fancier algorithm instead of the proposed ones was a good idea.
>
>
This is clearly in violation of the spec. You could argue this about
anything in Bitcoin. What if a developer decided to replace SHA256 with
SHA3 in their implementation of a Bitcoin client? Obviously this would
cause issues.

Will

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Pavol Rusnak]

On 03/12/2014 08:55 PM, William Yager wrote:
> The proposed BIP uses a bloom filter, so it has both plausible deniability *and
> *typo checking. The bloom filter is optimized for two elements and will
> catch something like 99.9975% of typos, despite allowing two different
> passwords.

Ok, I see. So the spec allows one real and one fake password. That is
something I don't consider plausible deniability. I am not saying that
this solution is wrong, I find it quite interesting, but it's not
plausible deniability. ;-)

>> I'm afraid one would end up with code generated in one client that is
>> unusable in a different client, because the client's developer thought
>> that using fancier algorithm instead of the proposed ones was a good idea.
>>
>>
> This is clearly in violation of the spec. 

Ah, I misunderstood. I thought that outsourcing the KDF means allowing
the 3rd party to use any KDF instead of the specified ones. What would
be the reason to outsource if this is not possible, anyway?

-- 
Best Regards / S pozdravom,

Pavol Rusnak <stick@gk2.sk>

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[William Yager]

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

On Wed, Mar 12, 2014 at 3:04 PM, Pavol Rusnak <stick@gk2.sk> wrote:

> On 03/12/2014 08:55 PM, William Yager wrote:
> > The proposed BIP uses a bloom filter, so it has both plausible
> deniability *and
> > *typo checking. The bloom filter is optimized for two elements and will
> > catch something like 99.9975% of typos, despite allowing two different
> > passwords.
>
> Ok, I see. So the spec allows one real and one fake password. That is
> something I don't consider plausible deniability. I am not saying that
> this solution is wrong, I find it quite interesting, but it's not
> plausible deniability. ;-)
>

It's a little more nuanced than that. There are *always* at least two
passwords. If the user doesn't want a second password, a random one is
generated for them. A wallet with two known encryption keys and only one
known encryption key are indistinguishable. If compelled to decrypt, there
is no way to prove that the user actually knows a second password.


>
> >> I'm afraid one would end up with code generated in one client that is
> >> unusable in a different client, because the client's developer thought
> >> that using fancier algorithm instead of the proposed ones was a good
> idea.
> >>
> >>
> > This is clearly in violation of the spec.
>
> Ah, I misunderstood. I thought that outsourcing the KDF means allowing
> the 3rd party to use any KDF instead of the specified ones. What would
> be the reason to outsource if this is not possible, anyway?
>
>
Yes, the "outsourcing" terminology is a little confusing. The idea is this:
You have a little device, like a Trezor. It has very little RAM and very
little CPU power. However, you want to use a powerful key-stretching
algorithm (like the maximum Scrypt KDF defined in the spec). One way to
implement this is to allow semi-trusted devices (like desktop PCs) to do
all the "heavy lifting". The way the spec is defined, it is easy to have a
more powerful device do all the tough key stretching work without
significantly compromising the security of the wallet.

Will

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Pavol Rusnak]

On 03/12/2014 09:10 PM, William Yager wrote:
> implement this is to allow semi-trusted devices (like desktop PCs) to do
> all the "heavy lifting". The way the spec is defined, it is easy to have a
> more powerful device do all the tough key stretching work without
> significantly compromising the security of the wallet.

By disclosing "preH" to compromised computer (between steps 4 and 5) you
make further steps 5-9 quite less important.

Too bad you started to work on spec just recently. :-/

-- 
Best Regards / S pozdravom,

Pavol Rusnak <stick@gk2.sk>

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[William Yager]

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

On Wed, Mar 12, 2014 at 3:24 PM, Pavol Rusnak <stick@gk2.sk> wrote:

> On 03/12/2014 09:10 PM, William Yager wrote:
> > implement this is to allow semi-trusted devices (like desktop PCs) to do
> > all the "heavy lifting". The way the spec is defined, it is easy to have
> a
> > more powerful device do all the tough key stretching work without
> > significantly compromising the security of the wallet.
>
> By disclosing "preH" to compromised computer (between steps 4 and 5) you
> make further steps 5-9 quite less important.
>
>
Yes, that was my chief complaint as well. A compromised computer removes
most of the extra security offered by key stretching (should you choose to
outsource the bulk of your key stretching).

However, I think we have a good compromise, which is the inclusion of a
number of PBKDF2-HMAC-SHA512 based KDFs. For anyone who doesn't want to
trust any external device, but also wants to use memory-contrained devices
(that group of people includes me), PBKDF2-HMAC-SHA512 is very easy to
implement even on devices that only have a few kB of RAM, and even though
our number of rounds is very aggressive (2^16 and 2^21), it will still run
in reasonable time even on very slow embedded ARM processors.

Will

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Pavol Rusnak]

On 03/12/2014 09:37 PM, William Yager wrote:
> (that group of people includes me), PBKDF2-HMAC-SHA512 is very easy to
> implement even on devices that only have a few kB of RAM, and even though
> our number of rounds is very aggressive (2^16 and 2^21), it will still run
> in reasonable time even on very slow embedded ARM processors.

To give you some numbers: TREZOR (120MHz ARM) does 1024 rounds of
PBKDF2-HMAC-SHA512 in around 1 second.

So 2^16 is around one minute, 2^21 is around half an hour.

-- 
Best Regards / S pozdravom,

Pavol Rusnak <stick@gk2.sk>

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[William Yager]

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

On Wed, Mar 12, 2014 at 3:42 PM, Pavol Rusnak <stick@gk2.sk> wrote:

> On 03/12/2014 09:37 PM, William Yager wrote:
> > (that group of people includes me), PBKDF2-HMAC-SHA512 is very easy to
> > implement even on devices that only have a few kB of RAM, and even though
> > our number of rounds is very aggressive (2^16 and 2^21), it will still
> run
> > in reasonable time even on very slow embedded ARM processors.
>
> To give you some numbers: TREZOR (120MHz ARM) does 1024 rounds of
> PBKDF2-HMAC-SHA512 in around 1 second.
>
> So 2^16 is around one minute, 2^21 is around half an hour.
>
>
Precisely. And since the target of this BIP is generally storage wallets
(just like BIP 0038), we figured these were reasonable time scales for
encryption/decryption on slow devices.

Let's say you're implementing a Raspberry Pi based cold wallet printer.
Having the user wait 10 seconds to several minutes is not unreasonable for
a one-time activity, especially when at least this much time is used to
generate entropy, print the wallet, etc.

The same goes for phones. If you're importing a heavily encrypted wallet
into your device, the user won't mind waiting a few seconds or even a few
minutes.

Plus, as an added bonus, the amount of time it will take to encrypt/decrypt
is highly deterministic, so it's easy to add a nice progress bar to a UI.

Will

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[Jean-Paul Kogelman]

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



On Mar 12, 2014, at 01:24 PM, Pavol Rusnak <stick@gk2.sk> wrote:

On 03/12/2014 09:10 PM, William Yager wrote:
implement this is to allow semi-trusted devices (like desktop PCs) to do
all the "heavy lifting". The way the spec is defined, it is easy to have a
more powerful device do all the tough key stretching work without
significantly compromising the security of the wallet.

By disclosing "preH" to compromised computer (between steps 4 and 5) you
make further steps 5-9 quite less important.
 
Agreed, this is a valid concern. This could possibly allow a 3rd party to crack the password, but then again, they would not gain access to any key material. So yes, you could expose your password, but your key would still be safe.

If people feel strongly about this vulnerability, we can revisit step 4 and adjust it to make password recovery more expensive.

jp

[-- Attachment #2.1: Type: text/html, Size: 1517 bytes --]

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[William Yager]

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

On Wed, Mar 12, 2014 at 4:08 PM, Jean-Paul Kogelman <jeanpaulkogelman@me.com
> wrote:

>
> Agreed, this is a valid concern. This could possibly allow a 3rd party to
> crack the password, but then again, they would not gain access to any key
> material. So yes, you could expose your password, but your key would still
> be safe.
>
> If people feel strongly about this vulnerability, we can revisit step 4
> and adjust it to make password recovery more expensive.
>
>
Just to clarify on J.P.'s comments:

*If* you choose to outsource StrongH calculation, and *If* that machine is
compromised, then the security of your password is reduced to a single
round of salted PBKDF2-HMAC-SHA512. Your private key remains on the trusted
device, no matter what.

Regrettable, but not catastrophic.

Will

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[William Yager]

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

Gmaxwell pointed out that we could safely front-load all the key
pre-stretching. The spec has been updated to take advantage of this.

The user's password is now protected by 10,000 rounds of salted
PBKDF2-HMAC-SHA512, as well as the main KDF (which ranges from scrypt
2^14/8/8 to scrypt 2^18/16/16 and PBKDF2-HMAC-SHA512 2^16 to 2^21).

Will

On Mon, Apr 21, 2014 at 7:05 PM, William Yager <will.yager@gmail.com> wrote:

>
> The idea is that more powerful devices (mobile phones, laptops, etc.) can
> do all the key-stretching on their own, whereas weaker devices with access
> to another device with more computing power (like Trezors) do a fair amount
> of key-stretching on their own, but can safely export the rest of the
> key-stretching to the other device.
>

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

Re: [Bitcoin-development] [RFC] Proposal: Base58 encoded HD Wallet root key with optional encryption

[William Yager]

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

The spec has been updated a bit.

Even if the bulk of the key-stretching work has been outsourced to another
device, and that device is compromised, the passphrase is now protected by
minimum 8192 rounds of salted PBKDF2-HMAC-SHA512.

The idea is that more powerful devices (mobile phones, laptops, etc.) can
do all the key-stretching on their own, whereas weaker devices with access
to another device with more computing power (like Trezors) do a fair amount
of key-stretching on their own, but can safely export the rest of the
key-stretching to the other device.

Will

On Tue, Mar 11, 2014 at 10:17 PM, Jean-Paul Kogelman <
jeanpaulkogelman@me.com> wrote:

> Hi everyone,
>
> We've been hard at work updating the spec to include features that were
> requested. We've removed the Scrypt dependency that was present in the
> initial drafts, added new KDFs, added plausible deniability and have a
> reference implementation.
>
>
> Kind regards,
>
>
> Jean-Paul Kogelman
>

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