Format for encrypted private keys in protobuf wallets

[Jim Burton]

Hello All,

I have started thinking about the format for the encryption of the private keys in bitcoinj protobuf wallets.

I know you have probably all been in the office today so please just flag this email and have a read of it later on in the week when you are in the mood.

* How to support encrypted private keys in the bitcoin.proto *

If you look at the bitcoin.proto . . .

http://code.google.com/p/bitcoinj/source/browse/core/src/bitcoin.proto?name=release-0.5

. . .you can see (line 39) that Mike has already put in enum for the type of key, with the current type as ORIGINAL.

We can extend this enum.

* What we need to do to support encrypted bitcoinj wallets *

I think to support a pan-bitcoinj encryption format for the private keys we 'just' have to:

+ agree a format for the encryption

+ document it

+ add in another enum type to the bitcoin.proto

+ code it up

+ test it thoroughly.

+ roll it out with UI updates to all our clients.

* Not so much a proposal, more a concrete example to look at *

Mainly so that we have something concrete to think about, I have been looking at the EncrypterDecrypter class I use in MultiBit for the encrypt/ decrypt of the private key export files. It is AES256 with 8 bytes of salt and is byte compatible with openssl (a particular invocation of openssl obviously - see the comments in the code below).

I have added a . . .

    byte[] encrypt(byte[] plainBytes, char[] password) 

and corresponding: 

    byte[] decrypt(byte[] cipherBytes, char[] password) 

. . . as I think that is what we want for storing in the wallet.

The code is here:

    https://github.com/jim618/multibit/blob/password/src/main/java/org/multibit/crypto/EncrypterDecrypter.java

and the test is here:

    https://github.com/jim618/multibit/blob/password/src/test/java/org/multibit/crypto/EncrypterDecrypterTest.java

The format for encrypting a 32 byte private key with a char[] password is:

1) Create 8 bytes salt with a SecureRandom.

2) Generate an encryption key (256 bytes) and initialisation vector (128 bytes) using the key and salt in exactly the same way as openssl.

3) Encrypt the private key with AES-CBC using the encryption key to create the encrypted bytes.

4) To the 8 bytes of salt concatenate the encrypted bytes. This is the result.

(It is probably easier just to have a look at the code.)

The idea of being openssl compatible is so that other devs can read our protobuf wallets and decrypt the keys easily if they want to.

* Next steps *

Let me know if you think I am on the right track. I am kind of assuming we all want a pan-bitcoinj format we can use to encrypt/ decrypt our private keys with maximum interoperability.

[Mike Hearn]

All that sounds totally reasonable and your EncrypterDecrypter class looks good.

The main design points to consider, beyond the crypto itself (I'll try and get some people I trust to examine that, to ensure we got it right):

1. If you do an operation on an encrypted wallet, like creating a spend, what happens? Do we have a Wallet.unlock(String passphrase) option? Throw an exception if the passphrase was not provided?
2. Do we require every key in the wallet to be encrypted under the same passphrase? I'd assume for simplicity the answer must be yes. 
3. Do we allow wallets to contain a mix of encrypted and unencrypted keys? I'd assume no, for simplicity.
4. If something in the background wants to add new keys to the wallet, and the wallet is locked, what happens?
5. We should probably implement keypooling first. Otherwise wallet backups become invalid very quickly.
6. What PBKCS settings make sense on desktops vs mobile phones?

--

Mike Hearn |

Senior Software Engineer |

he...@google.com |

Account security team

[Mike Hearn]

Oh, another thing to consider, is the key generation function.

Rather than the normal algorithm, scrypt may prove a better choice. It's designed to be resistant to GPU based brute forcing as it's memory bound. There is a Java implementation here, with both pure java + JNI versions. An ARM binary for Android is even included!

https://github.com/wg/scrypt

[Miron Cuperman]

Another possible approach is to generated one 256 bit random master
for the wallet, and then encrypt that with the password before
storage. The wallet keys can then be encrypted with the master key.

What is the purpose of the salt in your scheme? I believe that a salt
is only used to prevent dictionary attacks for password files so that
the attacker can't compare the hashed password with a pre-built
dictionary of hashed words. But this is not the case here. I think
the IV is enough. I will read a bit more about PBE to make sure.

Lastly, you need to store the IV with the encrypted data. Perhaps
BufferedBlockCipher does that for you.

[Miron Cuperman]

This was a reply to the OP, not to mike.

[Jim]

I have started a Google doc for the encrypted private keys
discussion and included Mike's and Miron's comments and some
replies by me.

https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#

Everyone with the link should be able to edit it.

It can start off quite freeform and then mature to a proper
specification
document. Feel free to add any ideas or issues to it.


Note: There is no mention of deterministic key generation in the doc
at this stage. I thought we should concentrate on the narrower case
of standalone encrypted private keys first and then look to see
where we need to extend it to cover HD wallets (and potentially
the Electrum deterministic wallet format too). Let's leave that
until later.

--
http://multibit.org Money, reinvented

[Jim Burton]

I have reworked the Google doc on Bitcoinj encrypted private keys adding:

+ both the salt and the IV to the stored information

+ a section on how to use the Wallet using methods lock() and unlock()

If you could have a look at it over the next few days/ week I would appreciate it.

It is here:

https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#

[Jim Burton]

I have done some more work on encrypted private keys, specifically on the Wallet changes.

I think I have come up with something workable. It is still a bit unfinished but have a look.

There are two main changes:

1) There is now an EncryptableECKey extend ECKey which you can encrypt and decrypt.

Because keychain is a public field in Wallet options are limited in what refactoring you can do.

Code:

https://github.com/jim618/multibit/blob/v0.5/src/main/java/org/multibit/crypto/EncryptableECKey.java

Test:

https://github.com/jim618/multibit/blob/v0.5/src/test/java/org/multibit/crypto/EncryptableECKeyTest.java

2) The Wallet needs to keep track of whether it is of type ENCRYPTED or UNENCRYPTED. This is the WalletType enum which is already in the (proposed) proto. In addition if it is an ENCRYPTED Wallet, it now tracks whether its keys are **currently** encrypted with a boolean:

    isLocked() = true       means the Wallet's keys are currently encrypted.

    isLocked() = false     means the Wallet's keys are currently decrypted (and hence you can, say, sign a tx).

There are new methods to encrypt a Wallet, decrypt it and remove its encryption entirely (changing it to type UNENCRYPTED).

This state management could go in Wallet but as this class is pretty crowded I have created a separate WalletEncrypterDecrypter to do it.

Code:

https://github.com/jim618/multibit/blob/v0.5/src/main/java/org/multibit/crypto/WalletEncrypterDecrypter.java

Test:

https://github.com/jim618/multibit/blob/v0.5/src/test/java/org/multibit/crypto/WalletEncrypterDecrypterTest.java

I think with this functionality it will hook into the MultiBit GUI ok.

As a bonus feature, an encrypted key has its private key bytes wiped for security and hence looks very similar to a watch only ECKey (i.e. public address but no private key) so dealing with these is one step closer to supporting watch only Wallets.

Let me know if you think this is the right approach or not.

[Mike Hearn]

This is looking promising.

Don't worry about keychain being public. The bitcoinj API is not stable and users need to accept that it can change. Andreas Petersson wanted to make it into a map as well. So if there's a better way to do it that involves keychain not being public, go right ahead and implement that.

I'm not sure about the WalletEncrypterDecrypter class. It's no big deal to have this functionality in Wallet. Yes, it's a large class, but in future I'm intending to refactor code out of it into separate classes.

When you encrypt the wallet, the old file needs to be securely wiped. I have an autosave branch that I've been working on at the hackathon - before doing anything in this area wait until I've merged it in, so you can ensure that encrypting an auto-saved wallet does the right thing.

I have been thinking that we need a TransactionSigner abstraction that knows how to sign with various kinds of keys - for example, encrypted keys or keys that are on other devices (for 2-factor coins). If we do this, having the wallet call into a TransactionSigner that knows how to decrypt keys on demand seems to make more sense than having a global "locked" vs "unlocked" state. That way, you could register a subclass of a EncryptedKeyTransactionSigner with the wallet to do blocking UI calls, eg to ask the user for their passphrase. Then we could also easily support having a wallet contain a mix of encrypted and unencrypted keys. Though the complexities around things like what to do with change outputs may mean this is not the way to go, in the end.

[Jim]

Thanks for your feedback Mike.

I think that for encrypted + unencrypted wallets an ArrayList<ECKey> is
ok. If it heterogeneous hardly anything will notice. I can see it
needing beefing up to something like a KeyManager when deterministic
wallets need supporting but that is still in the future yet. (I am not a
great believer in over-abstracting prematurely).

Re: locking and unlocking wallets. Perhaps this in the application
domain and should be in a LockableWallet extends Wallet. As long as
everything in Wallet is at least protected the subclass can then
implement the specific state management with 'guard methods' that then
call to the super if appropriate or throw state exceptions.

Subclassing leaves other users of bitcoinj with a 'purer' Wallet that
concentrates on Wallet-ey things.

The Wallet saving I will leave for now to see what you do.

I think also the EncryptableECKey should be created wih an interface to
do the encrypting/ decrypting so that other KDFs etc can be used in the
future.

With the TransactionSigner the keys being encrypted or not also affects
(in MultiBit at least) adding keys, importing, exporting etc. I think as
long as the keys expose if they are encrypted or not the application can
figure out what it wants to do I guess.

I will spend some time this week getting all the bits in the next
version of MultiBit talking to each other (even if it is not the
ultimate solution) to see what else pops up. I don't expect to release
it with encryption (other than alpha versions) until encryption goes
into bitcoinj as it would be a pain to have multiple not-quite-finished
encryption regimes. Life is too short for that !

> >> https://docs.google.com/**document/d/**1Z7kUZJePDS274mawMlMgQwN7C-**
> >> W88f_ITL4l0F5SVDY/edit#<https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#>

> >>
> >>
> >>
> >>
> >>> I have started a Google doc for the encrypted private keys
> >>> discussion and included Mike's and Miron's comments and some
> >>> replies by me.
> >>>

> >>> https://docs.google.com/**document/d/**1Z7kUZJePDS274mawMlMgQwN7C-**
> >>> W88f_ITL4l0F5SVDY/edit#<https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#>

> >>> > >> http://code.google.com/p/**bitcoinj/source/browse/core/**
> >>> src/bitcoin.proto?name=**release-0.5<http://code.google.com/p/bitcoinj/source/browse/core/src/bitcoin.proto?name=release-0.5>

> >>> > >> https://github.com/jim618/**multibit/blob/password/src/**
> >>> main/java/org/multibit/crypto/**EncrypterDecrypter.java<https://github.com/jim618/multibit/blob/password/src/main/java/org/multibit/crypto/EncrypterDecrypter.java>

> >>> > >> and the test is here:
> >>> > >>

> >>> > >> https://github.com/jim618/**multibit/blob/password/src/**
> >>> test/java/org/multibit/crypto/**EncrypterDecrypterTest.java<https://github.com/jim618/multibit/blob/password/src/test/java/org/multibit/crypto/EncrypterDecrypterTest.java>

[Mike Hearn]

OK, great.

If you look at my clones master branch you can see the autosave work, along with other stuff.

[Miron Cuperman]

Does anybody know what is the purpose of the salt in the KDF?  Seems like always using an IV would obviate the need for a salt.

[Jim]

Hi Miron,

I think without it an attacker can take a dictionary and then precompute
the AES keys using scrypt (slow). But then once they have the AES keys
of their attack dictionary they can quickly test them against ciphertext
that they have obtained.

The IV is part of the AES compute and hence is quick so does not slow
the attacker down.

On Tue, Jul 17, 2012, at 05:10 PM, Miron Cuperman wrote:
> Does anybody know what is the purpose of the salt in the KDF? Seems like
> always using an IV would obviate the need for a salt.
>
>
> On Tue, Jul 10, 2012 at 1:47 PM, Jim Burton <jim...@fastmail.co.uk>
> wrote:
>
> > I have reworked the Google doc on Bitcoinj encrypted private keys adding:
> >
> > + both the salt and the IV to the stored information
> > + a section on how to use the Wallet using methods lock() and unlock()
> >
> > If you could have a look at it over the next few days/ week I would
> > appreciate it.
> > It is here:
> >
> >
> > https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#
> >
> >
> >
> >
> >> I have started a Google doc for the encrypted private keys
> >> discussion and included Mike's and Miron's comments and some
> >> replies by me.
> >>

> >> https://docs.google.com/**document/d/**1Z7kUZJePDS274mawMlMgQwN7C-**
> >> W88f_ITL4l0F5SVDY/edit#<https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#>

> >> > >> http://code.google.com/p/**bitcoinj/source/browse/core/**
> >> src/bitcoin.proto?name=**release-0.5<http://code.google.com/p/bitcoinj/source/browse/core/src/bitcoin.proto?name=release-0.5>

> >> > >> https://github.com/jim618/**multibit/blob/password/src/**
> >> main/java/org/multibit/crypto/**EncrypterDecrypter.java<https://github.com/jim618/multibit/blob/password/src/main/java/org/multibit/crypto/EncrypterDecrypter.java>

> >> > >> and the test is here:
> >> > >>

> >> > >> https://github.com/jim618/**multibit/blob/password/src/**
> >> test/java/org/multibit/crypto/**EncrypterDecrypterTest.java<https://github.com/jim618/multibit/blob/password/src/test/java/org/multibit/crypto/EncrypterDecrypterTest.java>

[Jim]

Thinking about it more:
You only need one KDF salt per wallet, not per key (as it is described
now).

With one salt per wallet you only need to calculate scrypt once per
wallet.
With it per key you need to run scrypt for every key.There could easily
be thousands so this is a bad idea.

Perhaps the KDF salt needs to be on ScryptParameters and not on the key.

[Miron Cuperman]

Your explanation makes sense, thank you.

And one salt per wallet seems like the way to go.

[Jim Burton]

I have got the encryption working on the dev version of MultiBit !

The encryption has been updated in line with having one KDF salt per wallet.

The proto looks like this:

https://github.com/jim618/multibit/blob/v0.5/src/bitcoin.proto

The main classes/ tests  are:

EncryptableECKey:

https://github.com/jim618/multibit/blob/v0.5/src/main/java/org/multibit/crypto/EncryptableECKey.java

https://github.com/jim618/multibit/blob/v0.5/src/test/java/org/multibit/crypto/EncryptableECKeyTest.java

EncryptableWallet:

https://github.com/jim618/multibit/blob/v0.5/src/main/java/org/multibit/crypto/EncryptableWallet.java

https://github.com/jim618/multibit/blob/v0.5/src/test/java/org/multibit/crypto/EncryptableWalletTest.java

WalletProtobufSerializer:

https://github.com/jim618/multibit/blob/v0.5/src/main/java/com/google/bitcoin/store/WalletProtobufSerializer.java

I have also updated the google doc:

https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#heading=h.clwmv2kkooip

There is still plenty of testing to do and I will probably change how some of the MultiBit actions manipulate the wallet but it is progress.

[Mike Hearn]

Awesome! Keep going!

[Jim]

Thanks Mike!

There is one aspect of the design that I do not like but cannot think of
an improvement. I am hoping someone can come up with a better way.

The main workhorse classes are:
EncryptableECKey extends ECKey
and
EncryptableWallet extends Wallet

Most of the time everything is typed as the super but when I want to do
"encrypt-ey" things there are a number of instanceofs and casts to the
implementation class. It would be nice to eliminate those.

The 'non-encrypt-ey' code just sees ECKeys and Wallets as it should be.

> >>> > > > https://docs.google.com/**document/d/**1Z7kUZJePDS274mawMlMgQwN7C-
> >>> **W88f_ITL4l0F5SVDY/edit#<https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#>

> >>> > > >
> >>> > > >
> >>> > > >
> >>> > > >
> >>> > > >> I have started a Google doc for the encrypted private keys
> >>> > > >> discussion and included Mike's and Miron's comments and some
> >>> > > >> replies by me.
> >>> > > >>

> >>> > > >> https://docs.google.com/****document/d/****
> >>> 1Z7kUZJePDS274mawMlMgQwN7C-**<https://docs.google.com/**document/d/**1Z7kUZJePDS274mawMlMgQwN7C-**>
> >>> > > >> W88f_ITL4l0F5SVDY/edit#<https:**//docs.google.com/document/d/**
> >>> 1Z7kUZJePDS274mawMlMgQwN7C-**W88f_ITL4l0F5SVDY/edit#<https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#>

> >>> > > >> > >> http://code.google.com/p/****bitcoinj/source/browse/core/**<http://code.google.com/p/**bitcoinj/source/browse/core/**>
> >>> > > >> src/bitcoin.proto?name=****release-0.5<http://code.**
> >>> google.com/p/bitcoinj/source/**browse/core/src/bitcoin.proto?**
> >>> name=release-0.5<http://code.google.com/p/bitcoinj/source/browse/core/src/bitcoin.proto?name=release-0.5>

> >>> > > >> > >> https://github.com/jim618/****multibit/blob/password/src/**<https://github.com/jim618/**multibit/blob/password/src/**>
> >>> > > >> main/java/org/multibit/crypto/****EncrypterDecrypter.java<http**

> >>> s://github.com/jim618/**multibit/blob/password/src/**
> >>> main/java/org/multibit/crypto/**EncrypterDecrypter.java<https://github.com/jim618/multibit/blob/password/src/main/java/org/multibit/crypto/EncrypterDecrypter.java>
> >>> >
> >>> > > >> > >> and the test is here:
> >>> > > >> > >>

> >>> > > >> > >> https://github.com/jim618/****multibit/blob/password/src/**<https://github.com/jim618/**multibit/blob/password/src/**>
> >>> > > >> test/java/org/multibit/crypto/****EncrypterDecrypterTest.java<**

[Mike Hearn]

I think the fix for that is, as I said previously, to just not use a subclass. You can merge it all into the Wallet and ECKey classes.

I agree that the wallet class is too large and does many things, but it's the most central object in Bitcoin. I don't know if being feature rich is avoidable. Parts of it can and will be refactored out over time, but not for making the class smaller for its own sake, mostly because I want to allow more customization of its behavior.

The only issue with the wallet being large is that the API could become a bit overwhelming, but as long as the methods are reasonably independent and intelligently named/documented, I think we'll be OK.

[Jim]

I will do that.
Will clean up the code nicely.

[Gary Rowe]

Looking really good, Jim. Great effort!

[Jim Burton]

I have updated the Google doc with the proposed Bitcoinj encrypted wallet format:

https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#

There are now defaults on the ScryptParameters and the salt is one-per-wallet.

I think it is essentially complete now.

In prototyping the MultiBit encryption code I also came across a 'gotcha' that (for MultiBit) could destroy the private bytes so have put in some header bytes to get round it. The details are in the doc. These probably do not want to go in the formal spec if we can avoid it but I will probably have to live with it in MultiBit.

In the MultiBit v0.5 branch is a more-or-less working version of MultiBit with all the encryption UI and functionality working. I hope to release an alpha in a few days so it would be great if a few people could try it out.  I will mail out the details (together with necessary precautions!) when it is ready.

[Jim Burton]

Miron came up with a good solution to the 'gotcha' I noticed in the previous version of the encrypted wallet protobuf by introducing the idea of a VersionableWallet (= wallet + majorWalletVersion + minorWalletVersion).

The problem was that earlier versions of MultiBit that are in the wild could 'zap' the users encrypted private keys. There are full details in the doc.

I have now updated the encrypted wallet proto definition document and the MultiBit v0.5.0alpha code accordingly. In tests of the MultiBit v0.5.0alpha code it all works fine.

I have also taken the liberty of proposing the existing MultiBit version numbers for the majorWalletVersion/ minorWalletVersion of bitcoinj wallets that exist so far.

@Andreas - if you have added anything similar in Bitcoin Android Wallet you might want to have a look to see if it is compatible with what you have done.

[Andreas Schildbach]

I just read through your document again.

Some notes:

1. If you already anticipate WalletType to contain more than 3 values,
why not chose a more specific name for ENCRYPTED. For example:
ENCRYPTED_SCRYPT_AES.

2. Format of encrypted byte data, field "final block length". Is 1 byte
of length enough? Probably for AES256, but what if we upgrade to AES512
sometime?

3. Regarding the "TODO Andreas", what kind of test do you need? Can this
be made independant of BitCoinJ implementation? (if not, which version
is it rebased on currently?)

4. The sketch of API in "schematic usage" looks a bit suboptimal IMHO.
First of all, do operations 1 and 3 persist to disk?

If yes, they should only be used for user-initiated migrating of Wallets
from/to encrypted/decrypted states. Common operations like spending
should never persist keys in its plaintext form IMHO.

If no, why is step 3 needed at all?

5. KeyPooling. Can we defer this to a separate change/document. IMHO
this is not related. BitCoinJ currently does not even support
multiple/dynamic change addresses. An alternative to key pooling could
be deterministic keys.

6. VersionableWallet. Rather than wrapping a version around a Wallet,
why not just put it into the Wallet itself?

Cheers,

Andreas

> <jim...@fastmail.co.uk <mailto:jim...@fastmail.co.uk>>

> > > > wrote:
> > > >
> > > > > I have got the encryption working on the dev version
> of MultiBit !
> > > > >
> > > > > The encryption has been updated in line with having
> one KDF salt per
> > > > > wallet.
> > > > >
> > > > > The proto looks like this:
> > > > >
> https://github.com/jim618/multibit/blob/v0.5/src/bitcoin.proto
> <https://github.com/jim618/multibit/blob/v0.5/src/bitcoin.proto>
> > > > >
> > > > >
> > > > > The main classes/ tests are:
> > > > >
> > > > > EncryptableECKey:
> > > > >
> > > > >
> > >
> https://github.com/jim618/multibit/blob/v0.5/src/main/java/org/multibit/crypto/EncryptableECKey.java

> <https://github.com/jim618/multibit/blob/v0.5/src/main/java/org/multibit/crypto/EncryptableECKey.java>
> > > > >
> > > > >
> > >
> https://github.com/jim618/multibit/blob/v0.5/src/test/java/org/multibit/crypto/EncryptableECKeyTest.java

> <https://github.com/jim618/multibit/blob/v0.5/src/test/java/org/multibit/crypto/EncryptableECKeyTest.java>
> > > > >
> > > > > EncryptableWallet:
> > > > >
> > > > >
> > >
> https://github.com/jim618/multibit/blob/v0.5/src/main/java/org/multibit/crypto/EncryptableWallet.java

> <https://github.com/jim618/multibit/blob/v0.5/src/main/java/org/multibit/crypto/EncryptableWallet.java>
> > > > >
> > > > >
> > >
> https://github.com/jim618/multibit/blob/v0.5/src/test/java/org/multibit/crypto/EncryptableWalletTest.java

> > > jim...@fastmail.co.uk <mailto:jim...@fastmail.co.uk>>

> <http://docs.google.com/document/d/**>
> > > > >>> 1Z7kUZJePDS274mawMlMgQwN7C-**W88f_ITL4l0F5SVDY/edit#<
> > >
> https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#

> > > > >>> mi...@google.com <mailto:mi...@google.com>>

> > > > >>> jim...@fastmail.co.uk <mailto:jim...@fastmail.co.uk>>

> > > > >>> > > >> wrote:
> > > > >>> > > >> > >> Hello All,
> > > > >>> > > >> > >>
> > > > >>> > > >> > >> I have started thinking about the
> format for the
> > > encryption
> > > > >>> of the
> > > > >>> > > >> private
> > > > >>> > > >> > >> keys in bitcoinj protobuf wallets.
> > > > >>> > > >> > >> I know you have probably all been in
> the office today so
> > > > >>> please just
> > > > >>> > > >> flag
> > > > >>> > > >> > >> this email and have a read of it later
> on in the week
> > > when
> > > > >>> you are
> > > > >>> > > >> in the
> > > > >>> > > >> > >> mood.
> > > > >>> > > >> > >>
> > > > >>> > > >> > >>
> > > > >>> > > >> > >> * How to support encrypted private
> keys in the
> > > bitcoin.proto
> > > > >>> *
> > > > >>> > > >> > >> If you look at the bitcoin.proto . . .
> > > > >>> > > >> > >>
> > > > >>> > > >> > >>
> > >
> http://code.google.com/p/****bitcoinj/source/browse/core/**

> <http://code.google.com/p/****bitcoinj/source/browse/core/**><
> > >
> http://code.google.com/p/**bitcoinj/source/browse/core/**

> <http://code.google.com/p/**bitcoinj/source/browse/core/**>>
> > > > >>> > > >>
> src/bitcoin.proto?name=****release-0.5<http://code.**
> > > > >>>
> google.com/p/bitcoinj/source/**browse/core/src/bitcoin.proto?**

> <http://google.com/p/bitcoinj/source/**browse/core/src/bitcoin.proto?**>
> > > > >>> name=release-0.5<
> > >
> http://code.google.com/p/bitcoinj/source/browse/core/src/bitcoin.proto?name=release-0.5

> <https://github.com/jim618/****multibit/blob/password/src/**><
> > >
> https://github.com/jim618/**multibit/blob/password/src/**

> <https://github.com/jim618/**multibit/blob/password/src/**>>
> > > > >>> > > >>
> > >
> main/java/org/multibit/crypto/****EncrypterDecrypter.java<http**
> > > > >>>
> s://github.com/jim618/**multibit/blob/password/src/**

> <http://github.com/jim618/**multibit/blob/password/src/**>
> > > > >>>
> main/java/org/multibit/crypto/**EncrypterDecrypter.java<
> > >
> https://github.com/jim618/multibit/blob/password/src/main/java/org/multibit/crypto/EncrypterDecrypter.java

> <https://github.com/jim618/multibit/blob/password/src/main/java/org/multibit/crypto/EncrypterDecrypter.java>
> > > >
> > > > >>> >
> > > > >>> > > >> > >> and the test is here:
> > > > >>> > > >> > >>
> > > > >>> > > >> > >>
> > >
> https://github.com/jim618/****multibit/blob/password/src/**

> <https://github.com/jim618/****multibit/blob/password/src/**><
> > >
> https://github.com/jim618/**multibit/blob/password/src/**

[Jim]

Comments inline.

On 3 Aug 2012, at 13:11, Andreas Schildbach <and...@schildbach.de> wrote:

> I just read through your document again.
>
> Some notes:
>
> 1. If you already anticipate WalletType to contain more than 3 values,
> why not chose a more specific name for ENCRYPTED. For example:
> ENCRYPTED_SCRYPT_AES.
>

Good point. Will do.

> 2. Format of encrypted byte data, field "final block length". Is 1 byte
> of length enough? Probably for AES256, but what if we upgrade to AES512
> sometime?

Had not thought of that. Will bump to 2 bytes, little endian.

>
> 3. Regarding the "TODO Andreas", what kind of test do you need? Can this
> be made independant of BitCoinJ implementation? (if not, which version
> is it rebased on currently?)
>

Currently the code is in the MultiBit v0.5 branch only. Perhaps wait until I prep a pull to bitcoinj ? The purpose is to get a good default of N that is reasonable on mobiles. As you can store the ScryptParameters you can store any value you want. The default value at the moment of 16k just feels a bit small so I would like to increase it whilst keeping it reasonable for mobile CPUs.

> 4. The sketch of API in "schematic usage" looks a bit suboptimal IMHO.
> First of all, do operations 1 and 3 persist to disk?
>

I think I will remove this - I only do a full decrypt and encrypt in MultiBit when people add/ remove their password. I am sure other code will be similar. I will just describe the methods available neutrally.

> If yes, they should only be used for user-initiated migrating of Wallets
> from/to encrypted/decrypted states. Common operations like spending
> should never persist keys in its plaintext form IMHO.
>
> If no, why is step 3 needed at all?
>
> 5. KeyPooling. Can we defer this to a separate change/document. IMHO
> this is not related. BitCoinJ currently does not even support
> multiple/dynamic change addresses. An alternative to key pooling could
> be deterministic keys.
>

Agreed - I will take it out of this doc as it is separate to the wallet persistence.

> 6. VersionableWallet. Rather than wrapping a version around a Wallet,
> why not just put it into the Wallet itself?
>

It is to make it intentionally NOT backwards compatible! If the fields are put in Wallet, older versions of MultiBit (that I cannot change) will then read the encrypted wallets and subsequently write them out WITHOUT the encrypted private keys (as they do not know about them). Result: blank private keys (wiped when wallet is encrypted) and blank encrypted private keys (wiped when older MultiBits write). Result: all bitcoin lost + lynch mob for Jim forms.

Having the VersionableWallet with non-overlapping message ids means that it is incompatible with the previous proto and they do not load in older MultiBits. It is a kludge but the best Miron and I can come up with.

If you do not have the backwards compatibility issue you can just use Wallet and only bother with VersionableWallet for interoperation with MultiBit wallets. The code to do it is not too bad - daisy chaining methods in WalletProtoSerializer.

END OF COMMENTS

On the code front - I am close to releasing a MultiBit 0.5.0alpha so that people can test it out. This will be a download from github only - not on multibit.org . In the readme I explain that we still might change the wallet format and to keep their test wallets separate.

[Andreas Schildbach]

On 08/03/2012 04:35 PM, Jim wrote:

>> 3. Regarding the "TODO Andreas", what kind of test do you need? Can this
>> be made independant of BitCoinJ implementation? (if not, which version
>> is it rebased on currently?)
>>
> Currently the code is in the MultiBit v0.5 branch only. Perhaps wait until I prep a pull to bitcoinj ?

Ok, then I'll wait.

>> 4. The sketch of API in "schematic usage" looks a bit suboptimal IMHO.
>> First of all, do operations 1 and 3 persist to disk?
>>
> I think I will remove this - I only do a full decrypt and encrypt in MultiBit when people add/ remove their password. I am sure other code will be similar. I will just describe the methods available neutrally.

I think we'll need 3 operations:

boolean Wallet.isEncrypted()
Returns true if wallet is encrypted.

boolean Wallet.unlock(String passphrase)
Unlocks wallet in memory only (!), returns success.

void Wallet.encrypt(String passphrase)
Encrypts wallet with key based on passphrase, null means remove
encryption. If wallet was encrypted before, needs to be unlocked prior
to using this call. Wallet is persisted to disk.

>> 6. VersionableWallet. Rather than wrapping a version around a Wallet,
>> why not just put it into the Wallet itself?
>>
> It is to make it intentionally NOT backwards compatible! If the fields are put in Wallet, older versions of MultiBit (that I cannot change) will then read the encrypted wallets and subsequently write them out WITHOUT the encrypted private keys (as they do not know about them). Result: blank private keys (wiped when wallet is encrypted) and blank encrypted private keys (wiped when older MultiBits write). Result: all bitcoin lost + lynch mob for Jim forms.
>
> Having the VersionableWallet with non-overlapping message ids means that it is incompatible with the previous proto and they do not load in older MultiBits. It is a kludge but the best Miron and I can come up with.

One alternative could be just using different filenames. I chose this
path for Java serialization to Protobuf migration.

I think Bitcoin Wallet is affected by this problem as well; however
Google Play does not allow downgrading apps.

Cheers,

Andreas

[Miron Cuperman]

On Fri, Aug 3, 2012 at 7:35 AM, Jim <jim...@fastmail.co.uk> wrote:

Comments inline.

On 3 Aug 2012, at 13:11, Andreas Schildbach <and...@schildbach.de> wrote:

> 2. Format of encrypted byte data, field "final block length". Is 1 byte
> of length enough? Probably for AES256, but what if we upgrade to AES512
> sometime?

Had not thought of that. Will bump to 2 bytes, little endian.

AES512 is 512 *bits*.  But making it a int16 won't hurt.

 

>
> 3. Regarding the "TODO Andreas", what kind of test do you need? Can this
> be made independant of BitCoinJ implementation? (if not, which version
> is it rebased on currently?)
>

Currently the code is in the MultiBit v0.5 branch only. Perhaps wait until I prep a pull to bitcoinj ? The purpose is to get a good default of N that is reasonable on mobiles. As you can store the ScryptParameters you can store any value you want. The default value at the moment of 16k just feels a bit small so I would like to increase it whilst keeping it reasonable for mobile CPUs.

I created https://github.com/devrandom/scryptbot/ScryptBot for Android testing of scrypt speed.  On my Galaxy Nexus, N=32768 gives around 1 second of CPU time.  We could have it even higher if we think that the user is willing to wait longer to open the wallet.  We could even have a slider and have the user choose password security level.  I can imagine that even 1000 seconds would be fine for some use cases. 

[Andreas Schildbach]

On 08/03/2012 07:25 PM, Miron Cuperman wrote:

> I created https://github.com/devrandom/scryptbot/ScryptBot for Android
> testing of scrypt speed. On my Galaxy Nexus, N=32768 gives around 1
> second of CPU time. We could have it even higher if we think that the
> user is willing to wait longer to open the wallet. We could even have a
> slider and have the user choose password security level. I can imagine
> that even 1000 seconds would be fine for some use cases.

Oh wow. In this case we probably think of some way to make key
derivation asynchronous. Android pops up the ANR dialog after about 5
seconds of not letting go of the UI thread. Even 1 second is quite
borderline.

[Miron Cuperman]

Oh, looks like the max heap size that we can count on is 16MB.  Also, the doc says that the target running time is 5s.  So should leave N at 16,384 and increase p to 8 or so.

[Miron Cuperman]

Good point.  It's probably best to wrap the wallet create/open with an AsyncTask on Android.

[Andreas Schildbach]

The point of how we design wallet encryption is that unlocking is only
needed for several (uncommon) operations. So unlocking will happen while
the user doing something, like spending. Opening the wallet will not
need the passphrase. (Creating the wallet is a special case; most likely
I will continue creating unencrypted wallets by default.)

Given that encryption/decryption is reasonably fast, and only key
derivation is slow by design, I propose to split out key derivation as
follows:

Key <Helper>.deriveKey(String passphrase)
Derive key from passphrase, can take very long

boolean Wallet.unlock(Key key)

Unlocks wallet in memory only (!), returns success.

void Wallet.encrypt(Key key)
Encrypts wallet with key, null means remove encryption. If wallet was

encrypted before, needs to be unlocked prior to using this call. Wallet
is persisted to disk.

This way, we can run deriveKey() asynchronously and when its finished,
unlock the wallet synchronously. The idea is that deriving keys does
need any kind of synchronisation, while unlocking the wallet needs most
likely to synchronize on the wallet.

With deriveKey(), we'd also have the option to return a future, allowing
for progress.

[Jim Burton]

Three points:

1) I have updated the doc with all your comments.

2) Andreas - what do you mean by 'unlock' exactly ? For the MultiBit code all the only things I need the password for are:

+ encrypt all the private keys, simultaneously clearing the unencrypted key bytes in memory for security.

+ add new encrypted keys (for create new receiving addresses, wallet import)

+ clone the encrypted private keys, then decrypt them before spending/ exporting keys/ checking if I already have the key. Clear the unencrypted  cloned keys after use for security.

+ to completely remove the encryption I need the user to reenter the password to decrypt the keys. The password is not being stored in memory so I cannot decrypt the keys otherwise.

For most things like transaction management, fork management etc everything uses the key's pubkey and hence is completely uninterested in whether the key is encrypted, decrypted or (in the future) watch-only.

3) If the major and minor wallet fields were of general interest then perhaps they should go into the Wallet type. Then rather than a VersionableWallet I would just have an extra 'wrapping' message (to avoid my specific MultiBit problem) as:

message WrappedWallet {

    required Wallet wallet = 1000;

}

This would make the major and minor wallet versions of general use on Wallet. I imagine most bitcoinj users would ignore the WrappedWallet message entirely.

[Jim Burton]

Looking at the EncrypterDecrypterScrypt code, there is already a private method:

KeyParameter getAESPasswordKey(char[] password)

that is functionally equivalent to the deriveKey Andreas mentions. (The time consuming one to generate the key from the password).

It would be straightforward to expose this as public and then have the encrypt/ decrypt methods take the KeyParameter rather than the password as the parameter. This would meet Andreas's requirements and other users can just call encrypt(deriveKey(password)). Hardly a problem.

I will change the EncrypterDecrypterScrypt accordingly.

[Andreas Schildbach]

On 08/03/2012 08:37 PM, Jim Burton wrote:

> 2) Andreas - what do you mean by 'unlock' exactly ? For the MultiBit
> code all the only things I need the password for are:
> + encrypt all the private keys, simultaneously clearing the unencrypted
> key bytes in memory for security.
> + add new encrypted keys (for create new receiving addresses, wallet import)
> + clone the encrypted private keys, then decrypt them before spending/
> exporting keys/ checking if I already have the key. Clear the
> unencrypted cloned keys after use for security.
> + to completely remove the encryption I need the user to reenter the
> password to decrypt the keys. The password is not being stored in memory
> so I cannot decrypt the keys otherwise.
>
> For most things like transaction management, fork management etc
> everything uses the key's pubkey and hence is completely uninterested in
> whether the key is encrypted, decrypted or (in the future) watch-only.

"Unlocking" means preparing the wallet for operations that need access
to Bitcoin private keys, like spending. I'd rather not name this
"decrypt", because this sounds like its the opposite of encrypt, which
it isn't. Most importantly, it does not persist any decrypted keys to
disk but keeps them in memory only.

I don't understand the need for cloning. Can you explain? Your other
points look good to me. The Satoshi client can sign arbitrary messages;
something like this would also need to unlock the wallet.

> 3) If the major and minor wallet fields were of general interest then
> perhaps they should go into the Wallet type.

My feeling is that a version - if we need it at all - should go into
Wallet directly.

WalletType is an enum anyway. Actually I'd rename it to EncryptionType.

> Then rather than a
> VersionableWallet I would just have an extra 'wrapping' message (to
> avoid my specific MultiBit problem) as:
>
> message WrappedWallet {
> required Wallet wallet = 1000;
> }
>
> This would make the major and minor wallet versions of general use on
> Wallet. I imagine most bitcoinj users would ignore the WrappedWallet
> message entirely.

Indeed.

I wonder what exactly do you want to achieve? You want to prevent
encrypted wallets from being loaded by old implementations. What will
happen in this case? (just an exception?)

Will you be able to load _un_encrypted wallets by old implementations?

Cheers,

Andreas

[Jim]

On Fri, Aug 3, 2012, at 09:49 PM, Andreas Schildbach wrote:
>
> On 08/03/2012 08:37 PM, Jim Burton wrote:
>
> > 2) Andreas - what do you mean by 'unlock' exactly ? For the MultiBit
> > code all the only things I need the password for are:
> > + encrypt all the private keys, simultaneously clearing the
> > unencrypted key bytes in memory for security.
> > + add new encrypted keys (for create new receiving addresses, wallet
> > import)
> > + clone the encrypted private keys, then decrypt them before
> > spending/ exporting keys/ checking if I already have the key.
> > Clear the unencrypted cloned keys after use for security.
> > + to completely remove the encryption I need the user to reenter the
> > password to decrypt the keys. The password is not being stored in
> > memory so I cannot decrypt the keys otherwise.
> >
> > For most things like transaction management, fork management etc
> > everything uses the key's pubkey and hence is completely
> > uninterested in whether the key is encrypted, decrypted or (in the
> > future) watch-only.
>
> "Unlocking" means preparing the wallet for operations that need access
> to Bitcoin private keys, like spending. I'd rather not name this
> "decrypt", because this sounds like its the opposite of encrypt, which
> it isn't. Most importantly, it does not persist any decrypted keys to
> disk but keeps them in memory only.

I see. After an unlock the unencrypted private keys are available in
memory for whatever you want to do. Makes sense as the password -> key
step is expensive on a mobile. I presume you do it just once.

>
> I don't understand the need for cloning. Can you explain? Your other
> points look good to me. The Satoshi client can sign arbitrary
> messages; something like this would also need to unlock the wallet.

In MultiBit I have a background TimerTask that writes out 'dirty'
wallets. Also there are various threads for the Swing UI, block replay,
background tasks etc. For this reason and for general security I want to
minimise the time the Wallet keys are decrypted and in memory. For
instance, to sign a spend I :

1) Clone the wallet's encrypted keys.
2) Pass the cloned encrypted keys and the password to the signing code.
3) In the wallet signing method I:
+) Decrypt the cloned keys
+) Sign
+) Clear the password and cloned keys' decrypted private keys.

By 'clear' I mean overwrite the bytes/ chars with zeroes.

By doing this:
1) The wallet's keys (i.e. the ECKey objects referenced in the Wallet)
are never decrypted. There is no way another thread can write the
plaintext private key to disk.
2) The decrypted private keys are in memory for the absolute minimum
time before the decrypted data is destroyed. The objects only exist
in the bottom, local method scope so will be garbage collected
promptly.
3) The password is in memory for the absolute minimum time before it is
destroyed.


Good point about signing messages a la Satoshi. That would also need the
wallet password too.

>
> > 3) If the major and minor wallet fields were of general interest
> > then perhaps they should go into the Wallet type.
>
> My feeling is that a version - if we need it at all - should go into
> Wallet directly.

I will move it into Wallet. (Though I think it is currently more
of a MultiBit thing. Hmmm).

>
> WalletType is an enum anyway. Actually I'd rename it to
> EncryptionType.

Yes - that is clearer. Will do.

>
> > Then rather than a VersionableWallet I would just have an extra
> > 'wrapping' message (to avoid my specific MultiBit problem) as:
> >
> > message WrappedWallet { required Wallet wallet = 1000; }
> >
> > This would make the major and minor wallet versions of general use
> > on Wallet. I imagine most bitcoinj users would ignore the
> > WrappedWallet message entirely.
>
> Indeed.
>
> I wonder what exactly do you want to achieve? You want to prevent
> encrypted wallets from being loaded by old implementations. What will
> happen in this case? (just an exception?)
>

That is *exactly* what I am trying to achieve. Unfortunately my code in
previous MultiBits is a little too zealous in recovering from exceptions
and the encrypted wallets DO load. They load, but have blank private
keys. (There is data in the encrypted key field but the old MultiBits do
not understand that field so they ignore it). When the wallets are
stored (MultiBit is again quite zealous in storing the Wallets) the code
writes out the blank private keys ONLY. The encrypted private keys DO
NOT get written. All the private key data is lost.

This is not a theorectical thing - I have done it in real life and lost
BTC ! [only 100 millis :-) ] It is just not acceptable to release code
that does that.

> Will you be able to load _un_encrypted wallets by old implementations?

Yes - the unencrypted wallets are written out with the private key bytes
all there and the previous MultiBits load it happily.

I guess that is wny I find a monotonically increasing wallet version
useful. The current production code looks up the wallet version and
knows it can deal with 'wallet versions up to 2'. Anything higher than
that is from the future so it just will not load it. In a year when
someone fires up an old copy of MultiBit from a USB drive and tries
to load a 'wallet version 5' it will have no idea what that wallet is
but will know not to load it.

Jim

[Jim Burton]

I think I have done all the changes to the bitcoinj.proto, namely:

+ There is now a deriveKey method in EncrypterDecrypter with signature:

    KeyParameter deriveKey(char[] password)

    The encrypt and decrypt now take the KeyParameter.

+ WalletType -> EncryptionType

+ EncryptedPrivateKey is a new child message in Key with iv and encrypted private key bytes. final_block_length has been eliminated (no longer required). The fiddling around chopping up the encrypted byte array has all gone.

+ major and minor version are now on Wallet

+ VersionableWallet is now WrappedWallet and only has a Wallet in it (this will probably only ever used by MultiBit).

The google doc has been updated.

All the consequent code changes are in the MultiBit v0.5 branch and appear to work ok.

I am going to have a 'test day' tomorrow (Sun) and hopefully get the v0.5.0alpha out on Monday.

:-)

[Andreas Petersson]

A few ideas to consider:

To keep wallets secure and portable it should be as small as possible.
(in kb File size) To achieve this you could split the information kep in
two parts:
(A) - The actual private keys with all neccesary metadata for importing
(creation date, in case of deterministic keys iterations, forks)
(B) - the public data extracted from the blockchain that is relevant for
a wallet (outputs, transactions, confidence levels..)

the data set (A) should be small enough to print int easily on a sheet
of paper, or even store it in your brain.
the data set (B) should not contain any security critical data, it
should only be protected to preserve user privacy. all of its content
could potentially be reconstructed from the p2p network.

something i noticed while implementing BIP11 support (M-of-N) transactions:
currently, if you only have partial keys in your wallet, bitcoinJ will
check with external services if they are able to sign an input based on
a transaction output.
the actual private keys are not known by bitcoinJ, it only requests a
boolean response for each ouput and a signing request once it tries to
spend it.
the way it is implemented now is that there are the "internal" keys
managed as before and the "external" keys that are used for multisg TX.

it would make sense (optionally) to have all keys treated as external
and let the BitcoinJ library user program (Multibit, Android Wallet, POS
app) handle their keys themselves. that way the bitcoinj library only
maintains data of type (B) and the lib user type (A). of course, this
means that a "TransactionSigner" will also communicate to BitcoinJ which
type of outputs he is willing to sign (pubkey, address, bip11 and in the
future bip16)

[Andreas Schildbach]

On 08/06/2012 05:03 PM, Andreas Petersson wrote:

> To keep wallets secure and portable it should be as small as possible.

I believe wallets will never be really portable, because of the
different storage needs different types of client have.

However, import/export formats should be portable. We agreed on a format
already some months ago, and yes it contains only keys no transactions.

Cheers,

Andreas

[Jim Burton]

Using Mike's suggestion of using mandatory extensions, I have simplified the bitcoinj Wallet proto for encrypted wallets.

It no longer has the WrappedWallet message in it.

The updated google doc is:

https://docs.google.com/document/d/1Z7kUZJePDS274mawMlMgQwN7C-W88f_ITL4l0F5SVDY/edit#

Next week I will produce a MultiBit 0.5.1alpha using this proto for the encrypted wallets and start preparing a bitcoinj patch with the relevant files in it. I think we are pretty close on the Wallet proto definition now so we can start trying to make the actual code as bulletproof as possible,

Note to testers: If you have any encrypted MultiBit 0.5.0alpha wallets you will be able to simply remove the encryption - using 0.5.0alpha - and then load them as 'regular, unencrypted' wallets in 0.5.1alpha.