Proposal: Base58 encoded HD Wallet root key with optional encryption

[adam3us]

We're assuming that the attacker somehow has your encrypted wallet key. He's trying to guess your password, and he's previously done KDF work for you.

The attacker guesses your password is "bob", now he generates the resulting KDF queries and sees that they match the work you asked him to do. He goes and simulates your full process, looks up his saved kdf results, and can now steal your coin.

Yes you are right.  It was written in great haste as I was leaving, figured this out shortly afterwards.

The problem is the network can be expected to cache your correct password result after KDF.

Therefore the only thing this could be good for is a one use signature (eg a big stash that you dont touch except once to sell it).

Or if you have a seed encrypted 1000 times with each different salt and the same password, and you securely delete the respective encrypted seed after each use.

50 choose 100 doesnt seem to help that picture.

The problem there is because the process is deterministic given your password and the wallet seed he can just regenerate the correct queries and ignore the chaff ones. (Unless you have a KDF which has some homomorphism that allows blinding, and I think thats both asking too much of implementors and escaping from the realm of memory hard KDFs that we'd prefer to use)

I think the Rivest & Wagner time-lock puzzle (which I extended with blinding) might be somewhat memory hardenable if one used bigger RSA key than necessary for security.  Not really tried to analyse it from that perspective so far, there may also be some parallelization opportunities or TMTOs.

The basic RSA blind signature is rather simple, eg used in the coinjoin protocol right.  The blinding variant I use for blinding the time-lock puzzle is quite similar.  Maybe it wouldnt be so bad if a simple reference implementation in OpenSSL were provided.

Adam

[callem]

Standardizing wallet root key encryption is a good idea. The proposal looks solid.

My only concern is this: If this proposal is adopted to replace single-key encryption as defined in BIP38, it should maintain the ability to decode those formats to the extent possible. This because BIP38, while still technically a 'draft', has proven very useful and has already been widely adopted for paper wallet encryption, many applications already use BIP38 in production. In addition to some applications for physical bitcoins (i.e. Casascius coins), other applications are also being proposed which rely on heavily on BIP38 'standards' (i.e. OpenCXP, POS using NFC, etc).

Should BIP38 (single key) encryption perhaps be maintained on its own since it already has specific applications? - Or is this intended to supercede or somehow merge with BIP38?

[riplin]

I never intended for my proposal to replace BIP 38.

In fact, I contacted Mike prior to posting my proposal to integrate it into BIP 38. He felt that it was different enough to warrant its own BIP, so I went ahead with that. Having said that, I can see why people would want to replace BIP 38 with this one, but there's one key feature that this proposal doesn't offer that makes BIP 38 still a very useful standard and that's 3rd party key generation (with the passphrase / confirmation codes). I don't think that's something this BIP can offer, so even if this BIP were to replace BIP 38, there would still be use cases for BIP 38 to thrive.

[gmaxwell]

Well, I certainly intend it to replace BIP38.  BIP38 was dropped onto the wiki without any public review or discussion and contains a number of unfortunate shortcomings which are corrected here.

The WRT third party generation, I think this proposal does accommodate that in a not-quite 1:1 manner... in that you can send someone off your encrypted key to transcribe.  Though even if it doesn't thats just a single use case— the fact that BIP38 can only accommodate a single address is a reason something should replace it even for that use case. Though I'm not sure how common that usecase will be in the future considering recent regulatory activity.

[wyager]

"4 bytes: SHA256(SHA256(master_bitcoin_public_address))[0...3], used both for typo checking and as part of the salt."

Possible scenario:

The police or mafia or whoever find your cold wallet. They iterate over all known addresses in the blockchain and find that an address with a hash matching your master public Bitcoin address has been used before. Maybe they want the owner of that address for some crime (like money laundering). Maybe they think you owe them protection money. Either way, they have some very strong, 32-bit evidence that you own the master address for this wallet.

Possible solutions:

1. Use a random salt and encrypt these 4 bytes along with everything else. Unfortunately, this increases length.

2. Use SHA256(SHA256(privkey))[0:3] or something instead. The information leak is much less useful that way. The absolute worst possible case (if SHA2 is broken completely, which is another issue) is that they've reduced the security of your master private key by 32 bits. Not a big deal.

[riplin]

Though I'm not sure how common that usecase will be in the future considering recent regulatory activity.

I think the issue was more the fact that Mike was selling loaded coins and not the wallet aspect of it.

I haven't updated the spec yet to support 3rd party hashing. Hopefully I'll get around to that the coming weeks.

The police or mafia or whoever find your cold wallet. They iterate over all known addresses in the blockchain and find that an address with a hash matching your master public Bitcoin address has been used before. Maybe they want the owner of that address for some crime (like money laundering). Maybe they think you owe them protection money. Either way, they have some very strong, 32-bit evidence that you own the master address for this wallet.

You're right, however, this only applies to the first key generated off the salt. I'll update the spec to mention this issue and to avoid using the top level key pair.

[wyager]

On a similar vein, I would prefer it if the date was an optional field or wasn't present at all.

For one, it's an information leak. They know roughly when I created the address, which could be used as evidence.

Second off, how are clients supposed to use it? What happens if the clock on the computer you used was wrong? Does the client just not look for old transactions? IMO, anyone who is really concerned about reducing blockchain scan time can use some kind of data structure suited to the task. It's a good idea, but I think the risks and potential software problems associated outweigh the benefits.

We can also shave off two bytes, or just use it for a random salt.

[riplin]

On a similar vein, I would prefer it if the date was an optional field or wasn't present at all.

First off, it's an information leak. They know roughly when I created the address, which could be used as evidence.

How could this be used as evidence? It can be easily changed to include a different date if you prefer or you can just set it to 0. If you don't use the top key pair, there's no way to tie any transactions to this key. The date doesn't prove anything in and of itself.

Second off, how are clients supposed to use it? What happens if the clock on the computer you used was wrong? Does the client just not look for old transactions?

You can pull the date from the top block in the blockchain when creating the key.

[wyager]

How could this be used as evidence? It can be easily changed to include a different date if you prefer or you can just set it to 0. If you don't use the top key pair, there's no way to tie any transactions to this key. The date doesn't prove anything in and of itself.

You can pull the date from the top block in the blockchain when creating the key.

I can't change it after the fact if it's used in the salt, and I doubt most implementations would add the extra dialogue option to fake the date. And what if I accidentally changed it to the wrong date, well after the first actual transaction? As for use as evidence: "Mr. Smith, one of our suspects, created this new wallet the same week our perp received a thousand BTC... awfully suspicious."

I don't intend to use this algorithm on a networked computer, so I can't use the blockchain or ntpd. In fact, my target is a Raspberry Pi with no network connection (and also no RTC), so the fact that the date is integrated into the spec would be kind of a pain.

Like I said, it's a good idea, but I don't think it will end up being worth the hassle. Someone could always just write on their cold wallet "I made this on December 3" and then if the client supports after-date lookups they can use that feature.

[riplin]

I can't change it after the fact if it's used in the salt, and I doubt most implementations would add the extra dialogue option to fake the date. And what if I accidentally changed it to the wrong date, well after the fact? As for use as evidence: "Mr. Smith, one of our suspects, created this new wallet the same week our perp received a thousand BTC... awfully suspicious."

I don't intend to use this algorithm on a networked computer, so I can't use the blockchain or ntpd. In fact, my target is a Raspberry Pi with no network connection (and also no RTC), so the fact that the date is integrated into the spec is kind of a pain.

Then set the date to 0, problem solved. You can write your own implementation or you can modify an (eventually) existing one if you want.

[wyager]

I can't change it after the fact if it's used in the salt, and I doubt most implementations would add the extra dialogue option to fake the date. And what if I accidentally changed it to the wrong date, well after the fact? As for use as evidence: "Mr. Smith, one of our suspects, created this new wallet the same week our perp received a thousand BTC... awfully suspicious."

I don't intend to use this algorithm on a networked computer, so I can't use the blockchain or ntpd. In fact, my target is a Raspberry Pi with no network connection (and also no RTC), so the fact that the date is integrated into the spec is kind of a pain.

Then set the date to 0, problem solved. You can write your own implementation or you can modify an (eventually) existing one if you want.

Let's look at the pros and cons of having a date field.

Pros:

If the wallet generator implements the date field, and if the user wants to use the date field, and if the Bitcoin client they're importing to supports the date field, and if they don't put the wrong date in, they can save maybe a few minutes on a block chain rescan.

Cons:

It's an information leak.

It increases the size of the string by two bytes.

It will break things if the generator has an incorrect clock.

It will increase software complexity a little bit on the generator side and possibly a *lot* on the Bitcoin client side.

[riplin]

It's an information leak.

I disagree. Even if you feel it's an information leak, you can set it to 0 and the problem is solved.

It increases the size of the string by two bytes.

True, but I consider that a minor issue.

It will break things if the generator has an incorrect clock.

The resolution is a week. Your clock would have to be off by that much into the future before it becomes an issue.

It will increase software complexity a little bit on the generator side and possibly a *lot* on the Bitcoin client side.

This is simply not true. Iterating over the blockchain to find the scan start point requires minimal effort. In fact, it's no different than doing a full scan, the only difference is when you actually start parsing the transactions in a block.

[wyager]

I disagree. Even if you feel it's an information leak, you can set it to 0 and the problem is solved.

True, but I consider that a minor issue.

The resolution is a week. Your clock would have to be off by that much into the future before it becomes an issue.

This is simply not true. Iterating over the blockchain to find the scan start point requires minimal effort. In fact, it's no different than doing a full scan, the only difference is when you actually start parsing the transactions in a block.

What if the software I'm using doesn't let me set it to zero? Yes, I can change it, but can every end-user?

Those two bytes could either be shaved off or used for something more useful.

What if my platform doesn't have a clock *at all*? I might need to automate this process.

What are client devs to do if the date is wrong? Do they throw an error? Crash? In some cases, they can't even know that the date is wrong without scanning the entire blockchain anyway. How would you propose working around that?

I really don't see the benefit of the date field. There are only a few situations where it will be useful at all, and even when it is useful, it saves minutes at most. Why is that so important?

[riplin]

What if the software I'm using doesn't let me set it to zero? Yes, I can change it, but can every end-user?

You're the first to bring up this issue whereas I've had several requests to include a time field to limit blockchain rescan. It's a non-issue. If you really want it to be zero, that's a feature you can request from developers of the client of your choice.

What if my platform doesn't have a clock *at all*? I might need to automate this process.

I have yet to encounter a single computer that doesn't have a clock.

What are client devs to do if the date is wrong? Do they throw an error? Crash? In some cases, they can't even know that the date is wrong without scanning the entire blockchain anyway. How would you propose working around that?

You don't need to scan the entire blockchain to figure out the time. You only need to look at the top block.

I really don't see the benefit of the date field. There are only a few situations where it will be useful at all, and even when it is useful, it saves minutes at most. Why is that so important?

It might save minutes now, but the blockchain will only get bigger and this will become a bigger issue.



The date field stays.

[wyager]

You're the first to bring up this issue whereas I've had several requests to include a time field to limit blockchain rescan. It's a non-issue. If you really want it to be zero, that's a feature you can request from developers of the client of your choice.

I have yet to encounter a single computer that doesn't have a clock.

You don't need to scan the entire blockchain to figure out the time. You only need to look at the top block.

It might save minutes now, but the blockchain will only get bigger and this will become a bigger issue.

The date field stays.

Requests from whom?

The Raspberry Pi doesn't have a clock. It's one of the most popular computer platforms out there.

I don't think you're seeing the issue; What if the encrypted wallet has an incorrect date string? How is the client to know? If it just skips ahead to the date listed on the encrypted wallet, it could miss a whole bunch of important transactions. How do you propose we deal with that without re-scanning the entire blockchain anyway? Any solution I can think of removes the utility of a date code in the first place.

As the blockchain gets bigger, computers get faster. If it was ever really an issue, we could just have an auxiliary data structure that records first transaction date for any given address (which means no date code is needed).

Why are you speaking like this is so final? You haven't really given a compelling argument for the necessity of the date field, and I think I've given several strong arguments against it. I'd like to hear from others what they think.

[gmaxwell]

Requests from whom?

From myself and probably any SPV wallet author too. This is a common feature in wallets which makes an _enormous_ performance difference for both full nodes and SPV nodes, and anything else without an enormous disk wasting historical index.

Dates with keys is a feature already supported in every SPV wallet, as well as Bitcoin-qt. It makes a huge impact on rescanning speed.

What if the encrypted wallet has an incorrect date string? How is the client to know? If it just skips ahead to the date listed on the encrypted wallet, it could miss a whole bunch of important transactions. How do you propose we deal with that without re-scanning the entire blockchain anyway? Any solution I can think of removes the utility of a date code in the first place.

If it's incorrect and you're able to scan without it, then go ahead and ignore it. Asking for an approximately correct date while generating a key is simply not a burden. If you're unable to handle this then you're going to garble up the addresses and send coins off into space.

Why are you speaking like this is so final? You haven't really given a compelling argument for the necessity of the date field, and I think I've given several strong arguments against it. I'd like to hear from others what they think.

Because it's a major requested feature and you can simply opt out of it either on the generation (set to 0) or use (ignore it) side.

[wyager]

Requests from whom?

From myself and probably any SPV wallet author too. This is a common feature in wallets which makes an _enormous_ performance difference for both full nodes and SPV nodes, and anything else without an enormous disk wasting historical index.

Dates with keys is a feature already supported in every SPV wallet, as well as Bitcoin-qt. It makes a huge impact on rescanning speed.

What if the encrypted wallet has an incorrect date string? How is the client to know? If it just skips ahead to the date listed on the encrypted wallet, it could miss a whole bunch of important transactions. How do you propose we deal with that without re-scanning the entire blockchain anyway? Any solution I can think of removes the utility of a date code in the first place.

If it's incorrect and you're able to scan without it, then go ahead and ignore it. Asking for an approximately correct date while generating a key is simply not a burden. If you're unable to handle this then you're going to garble up the addresses and send coins off into space.

Why are you speaking like this is so final? You haven't really given a compelling argument for the necessity of the date field, and I think I've given several strong arguments against it. I'd like to hear from others what they think.

Because it's a major requested feature and you can simply opt out of it either on the generation (set to 0) or use (ignore it) side.

Fair enough. I can see the big advantage with SPV nodes.
 

I do worry about determining whether or not the reported "creation date" is far ahead of the actual "creation date". It's possible to miss transactions that occurred before the "creation date" and fail silently.

[riplin]

Requests from whom?

Request for a date field from Mike Hearn: http://sourceforge.net/p/bitcoin/mailman/message/31201149/

Request for a date field from Tamás Blummer : https://bitcointalk.org/index.php?topic=258678.msg2766686#msg2766686

The Raspberry Pi doesn't have a clock. It's one of the most popular computer platforms out there.

Then set it to 0 on the Pi.

I don't think you're seeing the issue; What if the encrypted wallet has an incorrect date string?

Even if the computer that generated the seed was off by several days, it would still cover it. The date field is by week. And if you find mismatching transaction history (funds being spent that haven't been found during the scan), you can default back to whole chain scanning.

As the blockchain gets bigger, computers get faster.

It's not about speed it's about touching lots of data. You don't want to have to go through the entire blockchain in an SPV client, especially on a mobile platform.

[wyager]

I don't think you're seeing the issue; What if the encrypted wallet has an incorrect date string?

Even if the computer that generated the seed was off by several days, it would still cover it. The date field is by week. And if you find mismatching transaction history (funds being spent that haven't been found during the scan), you can default back to whole chain scanning.

Alright, understood. But this still bugs me. What if there *is* no mismatching transaction history? The address could have done a bunch of stuff before the "creation" date. As long as no txouts generated in that time period are used by the wallet after the "creation" date, you would never know. There would be no indication that you had to default back to whole chain scanning.

But I admit, this is a much smaller issue than the other ones I brought up (which have been addressed).

[wyager]

Implemented it here: https://github.com/wyager/Encrypted-HD-wallet

I followed the suggestion of the checksum being SHA256(SHA256(private_key))[0:3] instead of SHA256(SHA256(bitcoin_address))[0:3].

It's not heavily tested, but as far as I can tell it works fine.