Wallet encryption issue

[memvola]

I seem to remember seeing some software at one point that securely overwrites all empty space in a filesystem. That was for Windows

well you could:

Code:

dd if=/dev/random of=/junkfile
sync
rm /junkfile

it will consume all free space on your root fs.

I like the dd solution better, but if you like the feeling of a dedicated tool:

Code:

bcwipe -Fvmz ~/.bitcoin/

It will locate the device that the specified directory is located. It supports several wiping techniques in case you're paranoid.

In the case of dd, I'd create the junkfile in ~/.bitcoin to be sure it's the correct device. Also, with dd, it would be helpful to keep in mind that you'll run out of free space; so shut down any programs that might need extra disk space (e.g. bitcoin) and run dd as root if you have quotas or whatever to make sure all free space is utilized.

Regarding the issue with clear keys, making transactions over the network for such a trivial thing is obviously not a sane solution. I'm sure there is a way to wash the wallet at the time of encryption.

[deepceleron]

The best way to encrypt an old wallet with the least amount of data leakage would be to have a second database open a wallet.tmp file, encrypt all the wallet info into the new file, bit verify and test that every private key still turns into the address (that nothing was corrupted from bad sectors, gamma rays, etc), rename wallet.dat->wallet.unencrypted and wallet.tmp->wallet.dat, and then prompt the user "wallet encryption complete, delete unencrypted wallet backup?", then, if they confirm, 0-wipe the whole unencrypted file, rename it to a random bunch of characters, and then delete the old wallet.

[Gavin Andresen]

Code review and testing for the proposed fix is welcome:
  https://github.com/gavinandresen/bitcoin-git/tree/encryptionbug

Here's how I tested:

I dumped private keys from an unencrypted wallet (using bitcointools).

I wrote a little tool that took a list of private keys and a filename and reported whether or not the 32-bytes of any of the private keys appears anywhere in the file.

I also hacked a copy of bitcoin to dump any newly-generated-private keys into debug.log before they are encrypted and written to disk.

I verified that new keys for an encrypted wallet are never written to any of the Berkeley DB database files by encrypting the wallet, invalidating all of the existing keypool keys, generating new, encrypted keypool keys, sending bitcoins to a new, encrypted key, and checking all of the files for any unencrypted copies of the new private key.

So the problem became how to deal with old, previously-unencrypted keys that were ending up in the wallet.dat file.

I hoped that telling Berkeley DB to 'compact' the file would remove the 'slack' space that contained the old data (the root of the problem is BDB doesn't actually completely delete/overwrite data when you delete a key/value pair; if I missed a setting that makes it do that, please let me know). Doing that reduced the number of old private keys found by my tool, but didn't eliminate the problem.

Pieter worked on a different solution in parallel-- completely rewriting the database to a new file when encryption is turned on, then, assuming the rewrite succeeds (we trust BDB to do what a database is designed to do-- reliably write data to the disk), replace the old wallet.dat with the new wallet.dat.rewrite. During that process, all keypool keys are marked as 'used' (which actually means just not writing a 'pool' entry for them in wallet.dat.rewrite).

That works-- no old private keys made it into the new wallet.dat.

But during testing I ran into two issues:

1) The wallet.dat file isn't the only place the old private keys were found; the database transaction log (database/log.000..N) and some of the __db.00N files also contained them.  Adding a call to remove() the database environment at shutdown fixed the __db.00N issue; I had to write code to remove the database/log.000..N file on clean shutdown.

2) If more wallet database operations were performed after the rewrite (I had written code to top-up the keypool with new, secure keys before locking the wallet), old private keys could end up in the new wallet.dat.

To fix both of those issues, we modified the code so that a shutdown happens after wallet re-encryption.

... which reminds me of something else I need to test:  if you startup with a wallet encrypted by bitcoin versions 0.4.0 or 0.5.0, the wallet is re-encrypted and all of your old keypool keys are considered used.  (I believe it does not shutdown after doing that, though, but it should)

We've never made any guarantees that unencrypted private keys will not end up on your hard disk; if you have a virus on your system that can directly read blocks off your hard disk then it can almost certainly also read system memory, and could steal your wallet passphrase the first time you sent bitcoins.

Filling up free space on your disk (as suggested in this thread) might work, but it is a much better idea to send all of your bitcoins to new, 'born-encrypted' keys. Once fixed binaries are available, that will be easy-- just upgrade and then send all of your bitcoins to yourself, using newly-generated addresses.
Suggestions for more radical solutions, like storing private keys in a separate file, are out of scope. We got what we got; I personally think that a really good "deterministic private keys" solution, where the private keys for your wallet are derived from a passphrase that is only in your head (and maybe written down and stored in your safe deposit box) would be a better use of developer time rather than reworking how we store private keys on disk.

Even better would be further work on multisignature/multidevice solutions so even if your private keys are compromised an attacker can't spend your coins.

[beckspace]

1) The wallet.dat file isn't the only place the old private keys were found; the database transaction log (database/log.000..N) and some of the __db.00N files also contained them.

I thought that private keys were only stored in 'wallet.dat'. Does them show up when/after you send coins? Is it true for earlier versions?


thanks by the work btw

[DeathAndTaxes]

I personally think that a really good "deterministic private keys" solution, where the private keys for your wallet are derived from a passphrase that is only in your head (and maybe written down and stored in your safe deposit box) would be a better use of developer time rather than reworking how we store private keys on disk.

Even better would be further work on multisignature/multidevice solutions so even if your private keys are compromised an attacker can't spend your coins.

Thanks for the detailed explanation.  Once new version is available I think the smart option is to move to a completely new wallet which is encrypted from day one.

Longer term I agree with idea of a deterministic private "keyset".  If keys can be recreated from the passphrase there is no need to ever store the private keys, or have a keypool.  If you need a key simply create the next private key in the "sequence", calculate the public key, and store only the public key in the wallet along with some details that allow recreation of the private key (like sequence number).  To sign a transaction recreate the private key on the fly.  

I have already been doing some work on deterministic wallets but I was really just using it to create a "traditional wallet". The quoted excerpt made me just realize the "end game" wouldn't be using a deterministic function to make a traditional wallet but rather create and recreate keys as needed eliminating the need for the wallet to hold any secure information.

[etotheipi]

I have already been doing some work on deterministic wallets but I was really just using it to create a "traditional wallet". The quoted excerpt made me just realize the "end game" wouldn't be using a deterministic function to make a traditional wallet but rather create and recreate keys as needed eliminating the need for the wallet to hold any secure information.

I have been doing some work on this myself.  I don't see how we can get away with not storing any key data in the wallet at all.  What if someone wants to change their passphrase?   If the passphrase is actually determining their wallet keys, then they're stuck with that passphrase even if there's evidence of compromise.  They have to create a new wallet from a new passphrase and throw away all their old addresses.  Not to mention, some people might want to import non-generated keys in their wallet (there's a variety of reasons for this).  I think the answer is in "simple" wallets, with straightforward binary representations, and all handling of data is controlled by the developer, not some magical DB library.

For this reason, I'm doing the following in my client:  The determinstic generator is in the header of the wallet file:  

Code:

AES-IV | PrivateKeyGenerator | Chksum

This is AES-encrypted by a key generated from a passphrase by a memory-hungry, compute-heavy key-derivation function.  Once unencrypted, you can get to any of your generated private keys.  AND this same encryption key can be used to encrypt/decrypt imported keys into the wallet.  They would be appended to the file the same way as the privkey generator, but with unique bytes identifying the encryption state and IV of this new key.  

By doing it this way, the wallet is much more flexible/versatile, there's no ambiguity about where key data is and isn't, you can support arbitrary key generation as well as importing keys, and you control the file format, instead of using an external library with unknown behaviors under-the-hood.  Maybe I'm naive, but I think this is the way to go.

[DeathAndTaxes]

I have been doing some work on this myself.  I don't see how we can get away with not storing any key data in the wallet at all.  What if someone wants to change their passphrase?   If the passphrase is actually determining their wallet keys, then they're stuck with that passphrase even if there's evidence of compromise.  They have to create a new wallet from a new passphrase and throw away all their old addresses.  Not to mention, some people might want to import non-generated keys in their wallet (there's a variety of reasons for this).  I think the answer is in "simple" wallets, with straightforward binary representations, and all handling of data is controlled by the developer, not some magical DB library.

True there are some issues but I am optimistic.  You are right that changing the passphrase would require a new wallet and that non-generated addresses wouldn't be included however I think there are solutions to that.

1) You could import non-generated addresses (vanity addresses, old public signature wallet addresses, etc) and the private key would need to be stored so that would be slightly less secure.  However you could design a client which when it detects funds in a "legacy address" does a transaction to move it to a generated-address.

2) Alternatively could see relay services.  Granted you need to trust a third party but at most the could only steal 1 transaction and if they steal from anyone it would be obvious.  To use the service you would give them your legacy address (public & private key) and a public deterministic key from your new wallet.  When they receive funds they would forward them to you (taking a small fee of course).

For this reason, I'm doing the following in my client:  The determinstic generator is in the header of the wallet file:  

Code:

AES-IV | PrivateKeyGenerator | Chksum

This is AES-encrypted by a key generated from a passphrase by a memory-hungry, compute-heavy key-derivation function.  Once unencrypted, you can get to any of your generated private keys.  AND this same encryption key can be used to encrypt/decrypt non-generated/imported keys into the wallet.  They would be appended to the file the same way as the privkey generator, but with unique bytes identifying the encryption state and IV of this new key.  

In this way, there's no ambiguity about where key data is, you can support arbitrary key generation as well as importing keys, and you control the file format, instead of using an external library with unknown behaviors under the hood.  Maybe I'm naive, but I think this is the way to go.

I like that idea too but I think a system which stores no private keys (except optionally legacy keys) would have some interest from the community.  If combined w/ 2 factor authentication like a smart card or RSA token (and possibly a virtual keyboard) it would provide real security to "normal users".

[etotheipi]

Perhaps we're both right.  I see use in both applications, and it seems like the kind of thing the user should decide.  I think, by default, the no-sensitive-data-regardless-if-it's-encrypted method would be the default.  Just make sure there's a unique salt so that users who pick the same passphrase don't end up sharing funds.    

At the same time, I think there are plenty of users who are not concerned about encrypted key data, and should have the ability to use the more flexible, wallet (can change passphrase and import keys).  Personally, if the US gov't is okay with encrypting top secret data with AES-256, I'm happy protecting my funds with it.  Of course, only if it's done right -- and I think it can be as long as we write the code from the outset to be secure and done properly.

Perhaps it's too much change for the Satoshi client, in which case, we should divert our discussion back to how to deal with the current Satoshi implementation issue.  Personally, I believe the best thing to do is rewrite the entire file, "born encrypted", and try to zero out the old file before deleting it.  It sounds like Gavin has pretty much proposed this, already.

I know that when you delete/overwrite files, it doesn't necessary remove the old data (depending on FS), but there's a good chance if you actually open the file in "rw" mode and seek to the keys to overwrite the bytes in place?  I would expect that if we manually find all the private keys, and zero/randomize them, that it will almost be guaranateed to modify the file in-place.  As Gavin said, it's outside of scope to worry too much about this data left on the HDD, but it doesn't hurt to try.

[robocop]

one dummy question.
I don´t use the new client and I want know if the encrypted wallet is optional and could deactivate/activate by user?
I prefer to encrypt my wallet byself with different methods. ;-)

[mndrix]

one dummy question.
I don´t use the new client and I want know if the encrypted wallet is optional and could deactivate/activate by user?
I prefer to encrypt my wallet byself with different methods. ;-)

Good question.  Yes, wallet encryption is optional.  You must explicitly enable it.  I don't use the client's built-in encryption; instead storing my wallet in a TrueCrypt volume.

[robocop]

instead storing my wallet in a TrueCrypt volume

This is a good solution.

Thx for your answer :-)

[Mageant]

I assume that if I take a backup version of my wallet.dat that was not encrypted and then encrypt that with the new 0.5 version of bitcoin that it will encrypt it properly this time.

This would work better for me because I don't want to transfer all my Bitcoins to a new address.

[zellfaze]

Don't suppose someone could edit the first post to include a description of the problem again now that it has been fixed?  Might be a good idea to include some bolded text as well stating that the problem has been fixed if someone does edit the post.

Just thought it would be a good idea to have it in there for historical reasons.  Some people (me) are interested in what the problem was.

[etotheipi]

Hi zellfaze,

Not that it's entirely secret, but I have no interest in posting a HOWTO-exploit-users-who-haven't-updated-yet....  I will, for historical and educational reasons, update it in a couple weeks after there has been more time for people to become aware of the updated client and fix their wallet.   Remind me if I haven't done it by then.

Perhaps I'm being too conservative, but I did make this issue public a little earlier than I should have, and realized I should've disclosed it to the devs first instead of posting here.  I don't want to post information on the attack vector earlier than "necessary", whatever that means.

-Eto

[zellfaze]

That is completely understandable.  I'll make sure that I send you a reminder in a few weeks once people have had time to switch to the new version.

[etotheipi]

So, that was a good idea about editing the original post to explain that this problem has been fixed.  I just did that and included a quote from the release notes about corrective actions to protect your wallet.

[etotheipi]

FYI, I finally remembered to update the original post about the encryption issue.  Should be complete now.

[gmaxwell]

FYI, I finally remembered to update the original post about the encryption issue.  Should be complete now.

There actually turned out to be no way to convince the database system to actually purge the data. The cleanup is handled by creating a new database, copying the data over, and deleting the original one. Doing this completely even requires shuttdown the library so all the databases can be cleanly closed.  A real pain.