I'm having trouble seeing any value whatsoever in wallet encryption.
Given the amount of computing power available to attackers (botnets, GPU mining farms, etc), you'd need to use scrypt parameters so onerous (multiple days on a regular PC) that there would be a significant chance of a single-bit error occurring during the calculations.
Topic: Proposal: Base58 encoded HD Wallet root key with optional encryption - page 8. (Read 21001 times)
July 23, 2013, 01:10:03 AM
July 22, 2013, 11:56:08 PM
Interesting idea, but I'm not sure why KDF strength should be linked to seed length?
A 128-bit seed is suitable given the overall BIP32 design; you can make it bigger but it doesn't really buy you anything. If 128-bits isn't enough, much bigger things are probably broken.
A stronger KDF, on the other hand, is all about deterring brute-force attacks. It might be perfectly reasonable for it to take 60 seconds or longer to run the KDF when I'm restoring my HD wallet from cold storage.
Ultimately the difficulty factor for the KDF will have to change over time to respond to advances in hardware and software, so it's definitely "planned obsolescence" to pick a fixed difficulty. In other words, the entire proposal becomes less and less secure over time (easier to brute-force) if users or implementers can't scale up the difficulty.
It's less clear how well 'scrypt' itself will scale over time, but at least it "should" be able to scale up, barring any fundamental weakness being discovered in its design. So exposing some degree of control of the scrypt parameters should mean the proposal can still protect against brute-force attacks as well 5 years from now as it does today.
For what it's worth, I read that LTC uses scrypt with 10-1-1 and right now the network is doing 24GH/s.
My last thought is KDF speed also varies with the use case. If I'm encrypting/decrypting the seed every time I unlock my smartphone and open up my wallet app, obviously that's going to need to run a lot faster than if I'm backing up my "life savings cold wallet" from a desktop app which I only plan to make deposits to over the next 10 years. So different apps could expose radically different timings to the end user (I'm not saying the end-user would/should know enough to pick the timings themselves).
Does anyone know how fast 14-8-8 even runs on an older Android or a Raspberry Pi? For all I know, even though I'd like something slower than 14-8-8 on my desktop, the same could be totally unusable for mobile.
A 128-bit seed is suitable given the overall BIP32 design; you can make it bigger but it doesn't really buy you anything. If 128-bits isn't enough, much bigger things are probably broken.
A stronger KDF, on the other hand, is all about deterring brute-force attacks. It might be perfectly reasonable for it to take 60 seconds or longer to run the KDF when I'm restoring my HD wallet from cold storage.
Ultimately the difficulty factor for the KDF will have to change over time to respond to advances in hardware and software, so it's definitely "planned obsolescence" to pick a fixed difficulty. In other words, the entire proposal becomes less and less secure over time (easier to brute-force) if users or implementers can't scale up the difficulty.
It's less clear how well 'scrypt' itself will scale over time, but at least it "should" be able to scale up, barring any fundamental weakness being discovered in its design. So exposing some degree of control of the scrypt parameters should mean the proposal can still protect against brute-force attacks as well 5 years from now as it does today.
For what it's worth, I read that LTC uses scrypt with 10-1-1 and right now the network is doing 24GH/s.
My last thought is KDF speed also varies with the use case. If I'm encrypting/decrypting the seed every time I unlock my smartphone and open up my wallet app, obviously that's going to need to run a lot faster than if I'm backing up my "life savings cold wallet" from a desktop app which I only plan to make deposits to over the next 10 years. So different apps could expose radically different timings to the end user (I'm not saying the end-user would/should know enough to pick the timings themselves).
Does anyone know how fast 14-8-8 even runs on an older Android or a Raspberry Pi? For all I know, even though I'd like something slower than 14-8-8 on my desktop, the same could be totally unusable for mobile.
July 22, 2013, 07:35:22 PM
How about:
3c) Base the settings on seed length? There are currently 3 seed lengths: 128bit, 256bit and 512bit.
128bit seed: 14,8,8
256bit seed: 16,16,16
512bit seed: 18,16,16
Additionally, I could add more seed lengths to the proposal, like 192bit and 384bit.
July 22, 2013, 07:09:24 PM
I think a standard format for encrypted backup of the key material (not the hierarchy) is useful.
The heart of any password-based encryption is the KDF -- in this case you've chosen scrypt with n=2^14, r = 8, p = 8. Just a quick benchmark on my desktop shows this runs at about 25 iters / sec, using about 12MB of RAM per thread, which may be "slow enough", but hard to say definitively. By comparison n=16, r = 16, p = 16 which runs at about 2 iter / sec, using 100MB of RAM for per thread... or even n = 18, r = 16, p = 16 which runs at 0.5 / sec, using 500MB of RAM per thread.
Since we're talking about backing up 128 bits, I think it's reasonable to assume the end-user could either just memorize a 128-bit mnemonic (e.g. BIP39), and then they don't need a password (or a backup) at all, or alternatively they would use a password with most likely, significantly less than 128-bits of entropy.
The trade-off of using stricter 'scrypt' parameters is some devices may not be suitable for running even a single iteration. The problem is, if you target your settings to make these devices usable, you're throwing away a lot of the benefit of 'scrypt' -- to make brute-force attacks expensive across a wide range of devices, including GPU and ASIC.
A couple possible options:
1) Do nothing -- Keep 14/8/8 as the standard hard-coded settings for the KDF as it's "slow enough"
2) Increase difficulty -- Then we need to decide what the "right" settings are, including what the maximum RAM requirement should be
3) Provide some means of using different difficulties since there's no one-size-fits-all
Ultimately #3 would come down to somehow encoding the KDF/difficulty -- there are a few ways to do it...
3a) Add a one or two byte KDF enum -- 00 could mean "scrypt/14-8-8". 01 = "scrypt/16-16-16", 02 = "scrypt/18-16-16", etc. This has the advantage of allowing us to keep the format and use KDFs other than scrypt if desired. Possibly include a default of "scrypt/14-8-8" if these bytes were not present.
3b) Hard code assumption that the KDF is scrypt, and give a 2 or 3 byte encoding of the scrypt parameters that were used. Possibly include a default of 14-8-8 if these bytes were not present.
The heart of any password-based encryption is the KDF -- in this case you've chosen scrypt with n=2^14, r = 8, p = 8. Just a quick benchmark on my desktop shows this runs at about 25 iters / sec, using about 12MB of RAM per thread, which may be "slow enough", but hard to say definitively. By comparison n=16, r = 16, p = 16 which runs at about 2 iter / sec, using 100MB of RAM for per thread... or even n = 18, r = 16, p = 16 which runs at 0.5 / sec, using 500MB of RAM per thread.
Since we're talking about backing up 128 bits, I think it's reasonable to assume the end-user could either just memorize a 128-bit mnemonic (e.g. BIP39), and then they don't need a password (or a backup) at all, or alternatively they would use a password with most likely, significantly less than 128-bits of entropy.
The trade-off of using stricter 'scrypt' parameters is some devices may not be suitable for running even a single iteration. The problem is, if you target your settings to make these devices usable, you're throwing away a lot of the benefit of 'scrypt' -- to make brute-force attacks expensive across a wide range of devices, including GPU and ASIC.
A couple possible options:
1) Do nothing -- Keep 14/8/8 as the standard hard-coded settings for the KDF as it's "slow enough"
2) Increase difficulty -- Then we need to decide what the "right" settings are, including what the maximum RAM requirement should be
3) Provide some means of using different difficulties since there's no one-size-fits-all
Ultimately #3 would come down to somehow encoding the KDF/difficulty -- there are a few ways to do it...
3a) Add a one or two byte KDF enum -- 00 could mean "scrypt/14-8-8". 01 = "scrypt/16-16-16", 02 = "scrypt/18-16-16", etc. This has the advantage of allowing us to keep the format and use KDFs other than scrypt if desired. Possibly include a default of "scrypt/14-8-8" if these bytes were not present.
3b) Hard code assumption that the KDF is scrypt, and give a 2 or 3 byte encoding of the scrypt parameters that were used. Possibly include a default of 14-8-8 if these bytes were not present.
July 22, 2013, 04:31:56 PM
Added creation date field to proposal.
July 21, 2013, 05:57:17 AM
But as stated earlier, I'm open to suggestions on how one could efficiently serialize a hierarchical wallet structure, even though that's slightly off topic.
Each key is identified by a variable length sequence of integers. Those sequences can be efficiently compressed since they form a tree (repeating prefixes). I am interested in the topic but do not have the time to work on it now. July 21, 2013, 04:08:24 AM
We do not need a new key serialization,
We?
I am pretty sure the hierarchy used could be encoded very efficiently, since you only need to store the index tree used.
I'm open to suggestions.
This is getting dumb.
You asked for comments but can't handle them. I should have said I and you should not have picked on "We" as if this would have been qualifying the content of my comment.
I can handle comments just fine. We were having a good discussion about the timestamp for example. I just find it a bit strange that you are so dismissive about this proposal to the point of using 'we' as if you speak for the entire community. But ok, let's ignore that.
It's an informative BIP, so you are free to ignore it.
It's obvious from several of your comments that you are looking for a solution that can serialize an entire hierarchical wallet, yet I've made it clear that this proposal does not cover that.
But as stated earlier, I'm open to suggestions on how one could efficiently serialize a hierarchical wallet structure, even though that's slightly off topic.
July 21, 2013, 03:54:16 AM
We do not need a new key serialization,
We?
I am pretty sure the hierarchy used could be encoded very efficiently, since you only need to store the index tree used.
I'm open to suggestions.
This is getting dumb.
You asked for comments but can't handle them. I should have said I and you should not have picked on "We" as if this would have been qualifying the content of my comment.
July 21, 2013, 02:20:48 AM
We do not need a new key serialization,
We?
I am pretty sure the hierarchy used could be encoded very efficiently, since you only need to store the index tree used.
I'm open to suggestions.
July 21, 2013, 01:59:32 AM
You either switched on higher level of error correction or your QR encoding tool creates suboptimal encoding since I get this for your BIP32 key:
http://imgur.com/YsnmI5N
http://imgur.com/YsnmI5N
I just grabbed the first online QR encoder that came up in google.
32 bit unix stamp will become a problem http://en.wikipedia.org/wiki/Year_2038_problem, milliseconds is certainly an overkill but IMHO the 64bit in milliseconds is new standard for unix time.
Have you read my edit? I think it's probably sufficient to store weeks (or months) since genesis, rather than a full timestamp.
I know your proposal is not trying to solve the wallet serialization, and that is a pity since that problem is unsolved.
It's just too much data, I think that's a problem best left to specific wallet implementations.
Standards are better built on top of other standards, therefore I would not invent a new time format. The amount of trees you save with those bytes is negligible.
I am pretty sure the hierarchy used could be encoded very efficiently, since you only need to store the index tree used.
However, your proposal is an intermediary step between key and wallet serialization and that is my original point. We do not need a new key serialization, but we need a wallet serialization.
July 21, 2013, 01:46:45 AM
You either switched on higher level of error correction or your QR encoding tool creates suboptimal encoding since I get this for your BIP32 key:
http://imgur.com/YsnmI5N
http://imgur.com/YsnmI5N
I just grabbed the first online QR encoder that came up in google.
32 bit unix stamp will become a problem http://en.wikipedia.org/wiki/Year_2038_problem, milliseconds is certainly an overkill but IMHO the 64bit in milliseconds is new standard for unix time.
Have you read my edit? I think it's probably sufficient to store weeks (or months) since genesis, rather than a full timestamp.
I know your proposal is not trying to solve the wallet serialization, and that is a pity since that problem is unsolved.
It's just too much data, I think that's a problem best left to specific wallet implementations.
July 21, 2013, 01:31:58 AM
You either switched on higher level of error correction or your QR encoding tool creates suboptimal encoding since I get this for your BIP32 key:
http://imgur.com/YsnmI5N
32 bit unix stamp will become a problem http://en.wikipedia.org/wiki/Year_2038_problem, milliseconds is certainly an overkill but IMHO the 64bit in milliseconds is new standard for unix time.
I know your proposal is not trying to solve the wallet serialization, and that is a pity since that problem is unsolved.
http://imgur.com/YsnmI5N
32 bit unix stamp will become a problem http://en.wikipedia.org/wiki/Year_2038_problem, milliseconds is certainly an overkill but IMHO the 64bit in milliseconds is new standard for unix time.
I know your proposal is not trying to solve the wallet serialization, and that is a pity since that problem is unsolved.
July 21, 2013, 12:56:31 AM
The current solution of extended public and private keys requires you to store this:
xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6Ln F5kejMRNNU3TGtRBeJgk33yuGBxrMPHi
versus my proposal of storing this:
wsHb15443fYPmneEXskd6wUZeP15fCiA69n
xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6Ln F5kejMRNNU3TGtRBeJgk33yuGBxrMPHi
versus my proposal of storing this:
wsHb15443fYPmneEXskd6wUZeP15fCiA69n
Yes, it is shorter but that alone would not justify to define a new standard,
You are ignoring the optional encryption.
since the BIP32 serialization fits into a QR code square that is only 13% taller and wider than your code.
The QR code of the extended private key is ~50% taller and wider and has ~75% more surface area than the master seed.
Master seed QR code:
Extended private key QR code:
Offline storage of the entire hierarchy of an HD wallet is outside of the scope of this proposal.
That is my point. Being able to recreate the wallet master key from encrypted seed is nice,
And that's all this is. A way to efficiently store the master seed with the option to encrypt it. Nothing more.
but I think need more to be able to efficiently recreate the wallet.
1. Importing of a private key into the wallet is rather expensive without knowing the key inception time point (that would limit the scan to blocks thereafter), hence the suggestion with key@inception
1. Importing of a private key into the wallet is rather expensive without knowing the key inception time point (that would limit the scan to blocks thereafter), hence the suggestion with key@inception
I'm sorry, English isn't my first language, so I may have overlooked that you were proposing I add a time field. My bad.
That's doable, although 64bit is pretty fine grained, considering that blocks are generated roughly every 10 minutes and transactions don't have timestamps, Something like a 32bit field would do just fine, maybe it's possible to go even smaller.2. The seed alone is not sufficient to recreate the wallet since scanning for all possible hierarchies is prohibitively expensive.
This is true. However, that's not what this proposal is trying to solve. Also, the extended private key doesn't solve this problem either.
Edit: If we allow overscanning a little bit, say a weeks worth of blocks (shouldn't take too long), then you'd be able to get to the year 3265 if you stored 2 bytes worth of weeks since the genesis block. If you allowed for overscanning by a month, you'd get to the year 7470 with a 2 byte timestamp.
July 21, 2013, 12:12:14 AM
The current solution of extended public and private keys requires you to store this:
xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6Ln F5kejMRNNU3TGtRBeJgk33yuGBxrMPHi
versus my proposal of storing this:
wsHb15443fYPmneEXskd6wUZeP15fCiA69n
xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6Ln F5kejMRNNU3TGtRBeJgk33yuGBxrMPHi
versus my proposal of storing this:
wsHb15443fYPmneEXskd6wUZeP15fCiA69n
Yes, it is shorter but that alone would not justify to define a new standard, since the BIP32 serialization fits into a QR code square that is only 13% taller and wider than your code.
Offline storage of the entire hierarchy of an HD wallet is outside of the scope of this proposal.
That is my point. Being able to recreate the wallet master key from encrypted seed is nice, but I think need more to be able to efficiently recreate the wallet.
1. Importing of a private key into the wallet is rather expensive without knowing the key inception time point (that would limit the scan to blocks thereafter), hence the suggestion with key@inception
2. The seed alone is not sufficient to recreate the wallet since scanning for all possible hierarchies is prohibitively expensive.
July 20, 2013, 10:08:09 AM
I think this is somewhat missing the needs.
Serialization of BIP32 is given and is sufficient for cold storage
Serialization of BIP32 is given and is sufficient for cold storage
I respectfully disagree.
The current solution of extended public and private keys requires you to store this:
xprv9s21ZrQH143K3QTDL4LXw2F7HEK3wJUD2nW2nRk4stbPy6cq3jPPqjiChkVvvNKmPGJxWUtg6Ln F5kejMRNNU3TGtRBeJgk33yuGBxrMPHi
versus my proposal of storing this:
wsHb15443fYPmneEXskd6wUZeP15fCiA69n
This is for a 128 bit seed. A 256 bit seed (more than sufficient entropy) would only require this:
wsFp1uM2gFhd2PuRzmNFReRud71hgmVwPoc7cGpxuvgETRsv8J1wHNANJ
Please note that these wallet seeds can be (and the ones shown above are) encrypted, whereas private extended keys are always in clear form.
perhaps with the addition of sipa's suggestion in a IRC:
key@inception where key is BIP32 serialization and inception is unix time (I suggest in milliseconds and 64 bit assumed).
Serialization of HD Wallets would need more than the seed, but e.g. also the hierarchy used.
key@inception where key is BIP32 serialization and inception is unix time (I suggest in milliseconds and 64 bit assumed).
Serialization of HD Wallets would need more than the seed, but e.g. also the hierarchy used.
Offline storage of the entire hierarchy of an HD wallet is outside of the scope of this proposal.
I'm not sure if representing a tree of sufficient complexity in human readable form is even desirable, but that's my personal opinion.
I think that the hierarchy is a great place for people to innovate. As you said, sequencing on the unix time is a great place to start, however, you have 256 levels at your disposal so you could simply write out your sub tree in readable form: .../2013/07/20/18/45/16/... would work too.
July 20, 2013, 02:59:48 AM
i hope there will be a consensus across wallets how to expand the hierachy.
that way you could deduct the hierachy from the blockchain. im some cases additional hierachy metadata is still neccessary. (if you generate millions of nodes without ever using them, for example)
that way you could deduct the hierachy from the blockchain. im some cases additional hierachy metadata is still neccessary. (if you generate millions of nodes without ever using them, for example)
July 20, 2013, 01:37:18 AM
I think this is somewhat missing the needs.
Serialization of BIP32 is given and is sufficient for cold storage, perhaps with the addition of sipa's suggestion in a IRC:
key@inception where key is BIP32 serialization and inception is unix time (I suggest in milliseconds and 64 bit assumed).
Serialization of HD Wallets would need more than the seed, but e.g. also the hierarchy used.
Serialization of BIP32 is given and is sufficient for cold storage, perhaps with the addition of sipa's suggestion in a IRC:
key@inception where key is BIP32 serialization and inception is unix time (I suggest in milliseconds and 64 bit assumed).
Serialization of HD Wallets would need more than the seed, but e.g. also the hierarchy used.
July 19, 2013, 10:25:46 AM
Reserved.
July 18, 2013, 02:03:17 PM
Recent changes:
24-04-2014 - Changed the preH and PostH calculation. Again.
21-04-2014 - Changed the preH and postH calculation.
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
Authors: Jean-Paul Kogelman, William Yager
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: RK1uXsCQAKqaa2s7YBDeaLS2KTqZcNjjQSgdSfDv4fqGkTw8KBfZ2ND4Cp7vHdzhjJ2C2Jtf4CwgScR nXvpzuQT2W4Vj2SgCyfBgpTzF (based on 0xFB 0xB3 plus seventy 0x00's)
Maximum value: RK3B9TMn55dey3an1oHpwB81FPZboakivYtqFvCaeknPzPK4iTvoFKzxVWKcD9YfJwjkyS36bqnSqji bUurcQ7J2EsQww5zPpJNzqjkw (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: rk48BmQWeQbATSXbP5U6XVsXRJTs4Ea1TVZBbHLPPsboCFyxDj2Jaz2JAJno97hq6dq2bANLuWydY8Q SZgKVGhPRZazXt1swPXwzVLw1QnVAz (based on 0x4E 0xB4 plus seventy-four 0x00's)
Maximum value: rkCRtT9R9kuAapCaLQFif5uo8gUrjgKsvYmGGTpX2ZTjTfwe9M7A6KezTh7f4FDxfZFVbHypodMNnNd mWYb8mzTokHXVR1u7KicrLLFFu7GJW (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:
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" = PBKDF2-HMAC-SHA512(key = salt, msg = passphrase, iterations = 10000, output_len = 64)
5. Calculate "strongH" = KDF(msg = preH[0:32], salt = preH[0:32], output_len = 64) This step can be outsourced to a 3rd party, if desired.
6. Calculate "H" = PBKDF2-HMAC-SHA512(msg = preH, salt = strongH, iterations = 1, output_len = len(root_key) + 32)
7. Calculate "whitened_key" = root_key XOR H[0:len(root_key)]
8. Calculate "encrypted_key" = AES256Encrypt(message = whitened_key, key = HR), where HR is the last 32 bytes of H
9. Calculate "fake_key" by decrypting encrypted_key with fake_passphrase
10. 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 6 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).
Reference implementation
Python reference implementation: https://github.com/wyager/Encrypted-HD-wallet
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
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.
Clarification:
Root Key: The BIP32 root key.
Private Key: IL in BIP32 parlance.
Salt Entropy: The random data used to generate the salt. With this, wallet generation can be tested deterministically. If you use this salt data, your encrypted wallets should *exactly* match the encrypted wallets listed here.
Test 1:
Test 2:
Test 3:
Test 4:
24-04-2014 - Changed the preH and PostH calculation. Again.
21-04-2014 - Changed the preH and postH calculation.
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
Authors: Jean-Paul Kogelman, William Yager
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: RK1uXsCQAKqaa2s7YBDeaLS2KTqZcNjjQSgdSfDv4fqGkTw8KBfZ2ND4Cp7vHdzhjJ2C2Jtf4CwgScR nXvpzuQT2W4Vj2SgCyfBgpTzF (based on 0xFB 0xB3 plus seventy 0x00's)
Maximum value: RK3B9TMn55dey3an1oHpwB81FPZboakivYtqFvCaeknPzPK4iTvoFKzxVWKcD9YfJwjkyS36bqnSqji bUurcQ7J2EsQww5zPpJNzqjkw (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: rk48BmQWeQbATSXbP5U6XVsXRJTs4Ea1TVZBbHLPPsboCFyxDj2Jaz2JAJno97hq6dq2bANLuWydY8Q SZgKVGhPRZazXt1swPXwzVLw1QnVAz (based on 0x4E 0xB4 plus seventy-four 0x00's)
Maximum value: rkCRtT9R9kuAapCaLQFif5uo8gUrjgKsvYmGGTpX2ZTjTfwe9M7A6KezTh7f4FDxfZFVbHypodMNnNd mWYb8mzTokHXVR1u7KicrLLFFu7GJW (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 = 214, r = 8, p = 8 |
| 0x01 | scrypt | n = 216, r = 16, p = 16 |
| 0x02 | scrypt | n = 218, 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" = PBKDF2-HMAC-SHA512(key = salt, msg = passphrase, iterations = 10000, output_len = 64)
5. Calculate "strongH" = KDF(msg = preH[0:32], salt = preH[0:32], output_len = 64) This step can be outsourced to a 3rd party, if desired.
6. Calculate "H" = PBKDF2-HMAC-SHA512(msg = preH, salt = strongH, iterations = 1, output_len = len(root_key) + 32)
7. Calculate "whitened_key" = root_key XOR H[0:len(root_key)]
8. Calculate "encrypted_key" = AES256Encrypt(message = whitened_key, key = HR), where HR is the last 32 bytes of H
9. Calculate "fake_key" by decrypting encrypted_key with fake_passphrase
10. 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 6 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).
Reference implementation
Python reference implementation: https://github.com/wyager/Encrypted-HD-wallet
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
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.
Clarification:
Root Key: The BIP32 root key.
Private Key: IL in BIP32 parlance.
Salt Entropy: The random data used to generate the salt. With this, wallet generation can be tested deterministically. If you use this salt data, your encrypted wallets should *exactly* match the encrypted wallets listed here.
Test 1:
| Root Key | 000102030405060708090a0b0c0d0e0f |
| Private Key | e8f32e723decf4051aefac8e2c93c9c5b214313817cdb01a1494b917c8436b35 |
| Creation Date | 04-02-2014 |
| Cleartext Wallet | RK6nEaou4eFQC4SfrHtdh9jpnEme4K9dt2jBmG |
| Password | Satoshi |
| Second Password | Alpaca |
| Salt Entropy | abcd |
| Encrypted with KDF 0 | rk354bQrbuzi9tVCt48rv9CCrc1Mi7sk9m3Yykpt3 |
| Second Private Key 0 | cf345038e7b0068d50e796756a3df60314f6edb7bc47c9ee7b4d73678668cdcb |
| Encrypted with KDF 1 | rk354bf4mvtwNXcLdcfppZECW4AoUBvTB8S23agNs |
| Second Private Key 1 | 632c122124ba9905be5e02078d36ba63b7588edd2c68f1b385b9d6c2ca3e0817 |
| Encrypted with KDF 8 | rk354dNXRL2jSEL5Neh6ndDsxNgvRoP3Tt4oMqLTV |
| Second Private Key 8 | a44ca5f6b4f38385e4a5cc751ace5d2117e3305aee52827286cbc981f00e80da |
| Encrypted with KDF 9 | rk354dcjNKEyDFwVgYrdCQnkZYpUWzhyjMY16enLT |
| Second Private Key 9 | 29e35fd44226c74117022b7e3079687bc2fa6391998753bc978509a8d9c5c323 |
Test 2:
| Root Key | 7f0ad7d595be13e6fe4cf1fa0fbb6ae9c26c5d9b09920709414982b6363d5844 |
| Private Key | 08965cb883e1c8783d72b65a0b7104d64baa9412eb655a6f05c5aaa6103781be |
| Creation Date | 04-02-2014 |
| Cleartext Wallet | RK22qqMb3CozsQfTTbSVsLEgXcjekut99SuSHn6urU4vWxjiQneHWVYabWgv |
| Password | Nakamoto |
| Second Password | hunter2 |
| Salt Entropy | defg |
| Encrypted with KDF 0 | rk2cMHcqyHdHNudopX8ZXwbrXgXK182FXpQJgiNdJbDGZXUpdWjfayTqi9tryTbS |
| Second Private Key 0 | 7645740391ba1c5ef56286a1f43e8f95ac0b66de3bffb5ad3922ec140b7ad28f |
| Encrypted with KDF 1 | rk2cMJD2R82kefxdoLEmXM3B8ox336pr2mbUNasLvEGKpZHzUMToWQyWmn6Y7szk |
| Second Private Key 1 | ffd47e0d8fa64a9a696b4c3b7128fe416f1363aee1ddf6acfd2dd433c2e6bee6 |
| Encrypted with KDF 8 | rk2cMNLHXGrjxDyBtQvM1Ef5AxiGgtHympDceeMoCqj9mhqteoeFtPRpc1PXXMfd |
| Second Private Key 8 | 96b831152e40d5461470729b88429c340de9c117c0d2af7564f91eb7e5f18443 |
| Encrypted with KDF 9 | rk2cMNvTy3VED3dCysRmZ6JswXAN2eYtA5oWegufDYNr7YQx2QHLbp3iie49u9Wf |
| Second Private Key 9 | 391edef21757317e5bf1df133c0000ae86f982ad3b340ab5876a33fb057930a8 |
Test 3:
| Root Key | fffcf9f6f3f0edeae7e4e1dedbd8d5d2cfccc9c6c3c0bdbab7b4b1aeaba8a5a29f9c999693908d8 a8784817e7b7875726f6c696663605d5a5754514e4b484542 |
| Private Key | 4b03d6fc340455b363f51020ad3ecca4f0850280cf436c70c727923f6db46c3e |
| Creation Date | 04-02-2014 |
| Cleartext Wallet | RK2BvY13FUD6bX25tA7XDyfAn7zbXSL8pR6TRE3EHZZ8qBm9qEyZRih8x1XhhcZwjcTfpe1Qjydn4KU dia8Wf1NshUusP1D38i88MLU9 |
| Password | Vires In Numeris |
| Second Password | Quis Custodiet Ipsos Custodes? |
| Salt Entropy | hijk |
| Encrypted with KDF 0 | rk5ySVNYwdRMDLnyxs1pXCdN3wrcBdPziWUudFidmwSfcJaZKPH8U24WSegPhidQiD7tXejMNQfxrAR h9JG8jLFtMY39fo9unpB4PsPSKymqy |
| Second Private Key 0 | 0625f1c1e50cb7c3f302ff37d5eaa0fe20f45b10eb13634f4403b71dd3e49526 |
| Encrypted with KDF 1 | rk5ySW9NGHgAxs48UvF5oWvb6PHsZte43p1vjKmYuybLyGNrSMVHAkypTfb9qLFNTFixfCrxqnT3a8V c5UoTcBzRxjLQAwYMoB7YcmzCWdVtD |
| Second Private Key 1 | 4a525d10640a9ccd26bbcc1af8a4803803e97628b7e7b6f0db5376c94021c83b |
| Encrypted with KDF 8 | rk5ySbZ5WuX3ba2Pudt1HE6iDQf7cSMg4zTsWbMKdFhucAwJEjNwH48oqCC52mbh3jxTQEGXN294Azx YsDbJowkiHSocGqWh7SFy24sE9KHGn |
| Second Private Key 8 | 83d025017755701dbfcf5b50d07a95a99d517c15f40f0bec5529ae1cc3e39ba0 |
| Encrypted with KDF 9 | rk5yScKtqZmWe5FAB54x7WvvuxDSnNg81J3CADPdh4GJ4t2QaHckv8iuWF2spbC6uDC7DSM3GkYSQvN tz88su2h89vj9yUpmECmeELH2TkzM5 |
| Second Private Key 9 | c16e82babbf14512c9acde344a817693d2f401d2c73c7aeacdd21c455a9d5dd8 |
Test 4:
| Root Key | 6ca4a27ac660c683340f59353b1375a9 |
| Private Key | f544dd076ffe8fb68aa81ca9a33059946e9a91f8d95258ae1b7a1db6215ce51a |
| Creation Date | 04-02-2014 |
| Cleartext Wallet | RK6nEmXZj2nqgtCVWk3s7Suvz2XtWrdhDPpJqS |
| Password | 聡中本 |
| Second Password | Bitcoin |
| Salt Entropy | lmno |
| Encrypted with KDF 0 | rk354bWG9c8dupPhhYsKgFEcZ8uqxV7JKbvbsmnzh |
| Second Private Key 0 | b5af32696fe4bd75015d55f52a5bec16af4de74c256458ba8fdba7702509b7ca |
| Encrypted with KDF 1 | rk354bkUKo7gu3vhdadunrCUSSjJuQrQwyRXoydTE |
| Second Private Key 1 | de80aba55dee465b979a71a90d43c9a1f594eaaa30086944b8280603783ff4b8 |
| Encrypted with KDF 8 | rk354dTvdLGCSSPHP8tjFeLXMhwybvE47szr2jUPH |
| Second Private Key 8 | 54b9fbe968a76327b452d0f7af1c74dfff34cddc4884ec6c65d1d1f66b3df79d |
| Encrypted with KDF 9 | rk354di8idN7qLmnbYSsFgjPbeHQ4b9CxSSviqXiH |
| Second Private Key 9 | 247f6877db617c7a28a45c44a97041d055f0c664f109e2b6c1f3d9702dcaaeaa |
Jump to: