Bitcoin Forum

2012 Update:  It's now been a few months since this event, so I think it's safe to describe, for the record, what actually happened.  The Bitcoin wallet file is managed by BSDDB, which is a database engine.  Presumably, a database engine was used, in order to ensure ACID transactions (atomicity, consistency, isolation, durability), which makes sure that the database won't be corrupted by inconveniently-timed power outtages, etc.  Most importantly, it should protect your private keys from ever getting corrupted.

The problem with a database manager, though, is that it does its own thing with the file storage.  It's a black box in terms of its behavior when you tell it to "delete" something.  You'd hope it would actually remove the data, or at least blank it out, but that's not necessarily true.  In the case of BSDDB, when Satoshi client says "delete this key and replace it with the encrypted key" it seems to not actually do that.  Instead, it simply marks the entry deleted, and then appends the new data to the end of the file.  It doesn't even overwrite the original data.  

From the user perspective, this is completely transparent, because the user must ask the BSDDB interface for the data, and BSDDB reports that it's gone, since the pointer to the data was discarded.  But, it's still in the binary file!

Before wallet encryption, I had written a pure-binary key-extractor script, to pull my private keys out of the wallet file (it was an elaborate search using the ECDSA library to find public-keys and find the associated private-key nearby).  After Bitcoin 0.4.0 was released with wallet encryption, I re-ran my script for fun.  To my surprise, it found 36 of 112 private keys!  Whoops!

I wasn't too involved in the fix for the problem, since I have no experience with BSDDB.  But the solution had to do with convincing the database to actually remove/overwrite the data, and allow for wallets to be "born" encrypted to avoid any risk of it happening again.   I don't know the gory details though, you'd have to ask the devs for specific details about how they fixed it.




Original Post:
I think I might've found a bug in the wallet encryption.

Edit: This problem has been fixed in the client version 0.5.0.  Please see the release notes (http://bitcoin.org/releases/2011/11/21/v0.5.0.html) for information on fixing your wallet.   The most important information is:

Wow. That is a problem. So we still need to encrypt our wallet file, even if it is encrypted by the client?

If you move all your coins out of the old keys and only use new keys (created after encrypting the wallet), there should be no problem.

- Joel

This is where casascius' recommendation for "sweepprivkey" becomes extremely useful.  

If that is true then the implementation is "borked".  Nothing in client docs indicate that limitation.  Users should at least be warned, even better would be for the client to recommend a transfer of all balances to a "new" address.

Discussing how to fix this in IRC now.

This IS a show-stopper issue for the 0.5 release.

Has anyone verified this?  I don't want to stop any shows unless someone else can confirm it.

BTW, I am on Ubuntu 10.04, 64-bit, if that matters...

When I read this, I thought it was a report about the encryption in the existing 0.4 client. With Gavin's comment that it's holding up 0.5, it makes me unsure what version(s) this may be issue for.

This is a 0.4.0 issue.  Gavin was trying to release 0.5 in the immediate future, but I think he wants to hold it up until we find a fix for this problem.  We should get this fixed ASAP.

I seem to recall that this was a known issue at the time wallet encryption was first implemented - was there meant to be something that fixed it since then?

fix:
load all keys in to memory.
delete wallet file.
make new encrypted wallet.
put back keys from memory.

That will of course leave behind unencrypted copies of the keys in the unallocated space on the disk - not to mention the risk of data loss if Bitcoin or the computer crashes at the wrong moment - but it might be better than nothing.

I think a better method is to load all keys in to memory, flag all existing keys as "potentially insecure", create new set of keys and transfer all balances to new set of keys.  Then encrypt all keys.

Granted you still run the risk of receiving money on an old "insecure" key but your current balances are secure and the client could ensure it never re-used one of those old addresses again.

then delete the wallet file after putting back back keys from memory.

for unencrypted keys on freespace on disks:
DO NOT TRY THIS AT HOME.

I seem to remember seeing some software at one point that securely overwrites all empty space in a filesystem. That was for Windows and I no longer even remember the name of the program. Something like that would be ideal to suggest to people who wish to secure their hard drives.

Would anyone happen to know the names of programs that can do this?

well you could:
it will consume all free space on your root fs.

The one for windows is called sdelete. I remember reading somewhere that this utility wasn't possible to do identically in linux because of the file system for some reason.

And the power goes out...

Other option is to remove the ability to encrypt an old wallet.
You can only create a new encrypted one.

As by definition if you had an un-encrypted wallet the keys will be spread all over your hard disk so encrypting it just gives you a false sense of security.

Use case would be:
1) If no wallet file there offer user option to create new unencrypted or encrypted wallet.

2) If unencrypted wallet there and user clicks on encrypt wallet show screen with instructions on how to create a new wallet then send coins from old to new.

3) If encrypted wallet there and was from version v0.4 show a warning box every time you open it telling you to move to a new wallet and explain why.

I don't know if this was meant as a joke, but it's probably worth pointing out that this will overwrite all the partitions on the first hard drive with random junk, not just the "freespace".

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


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.

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.

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.

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

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.

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:  

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.

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).


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".

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.

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.

This is a good solution.

Thx for your answer :-)

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.

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.

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

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.

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.

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.