[RFC] In-memory key encryption scheme

[Pieter Wuille]

First of all, sorry this idea is only formed after a working encryption patch was already developed, but I believe the following scheme would be perfect for encryption of wallets.

There is one wallet-wide master key, itself symmetrically encrypted (aes-cbc-256) with a passphrase. We use public-key encryption here, to allow encryption of wallet privkeys without knowledge of the passphrase, while requiring a passphrase for decrypting them.

The only place in the source where the actual private keys are needed, is while signing. This means only for that operation the passphrase would be required. New keys can be generated and stored without passphrase.

It may not make sense cryptographically, but since N-bit EC cryptography only offers N/2 bits of security, I would suggest using a stronger curve than secp256k1 ("only" 128 bits of security) - let's say secp384r1 - for the master encryption.

Thus, for the whole wallet a master secp384r1 keypair must be stored - the pubkey unencrypted, the privkey encrypted. When using point compression and only storing the private parameter itself, that requires 49 bytes + 48 bytes per passphrase.

Each walletkey then, will be encrypted using a separate 256-bit AES key derived using ECDH from the master key and a per-walletkey ephemeral secp384r1 key (=EC-IES). As IV a hash of the pubkey can be used. Since we're upgrading the wallet format anyway, we can immediately switch to only storing the private parameter of the wallet privkey (32 bytes) instead of the full openssl-encoded form (279 bytes). We will need to add the pubkey part of the ephemeral key though, adding 49 bytes (when using point compression). Hence, encrypted wallet privkeys can be stored using 81 bytes per key.

Advantages:
* keys can be generated and stored in encrypted form without knowing the passphrase
* multiple passphrases can be present in a single wallet (by storing the private master key more than once)
* changing a passphrase is trivial
* private keys can remain encrypted in memory, decrypting them only when creating a transaction
* when combined with switching to a more efficient representation of private keys and using point compression, storage/memory requirements for private keys still go down a factor 3

Questions:
* Is it cryptographically sound?
* Does it make sense to use a larger EC curve for the master key / encryption of privkeys themselves?
* Is using point compression an option? I heard there are patents on it, but it is implemented in OpenSSL. If not, the master key will require 97 bytes + 48 bytes per passphrase, and wallet privkeys will require 129 bytes.

[kgo]

I was thinking about a patch to encrypt wallets, but I'm still learning the codebase.   Could you let me know where the existing encryption patch is?  I'm new to all this.

My gripe only gripe with your strategy, why do you think creating a private-key is a safe option and public key encryption is a good idea?  I think you would want to ensure you're the only person who could create a new keypair.  If not, a malicious user could create a key where they have the private portion, and insert it into the wallet.  Then eventually you get your 99th key, and someone has a copy.

My idea was a salted-iterated master passhphrase which gets used as an AES256 key.  This is similar to the way OpenPGP encrypts it's secret keys, so I think the approach has been thought out.

Take password, append salt, hash it with SHA265 X times, where you have a default value X=128, but users can up this.  In json form, you end up with:

{ "master_key": {"salt":"AA","iterations":128,"crypted-key","SDFSDFSDGSGDSDGSGDSGDGSD"}}

And then the ECC keys are (de)crypted accordingly.

Alternately, the master-key could sign the subkeys, just like OpenPGP uids, but that would still need to be encrypted symmetrically.

[Matt Corallo]

I was thinking about a patch to encrypt wallets, but I'm still learning the codebase.   Could you let me know where the existing encryption patch is?  I'm new to all this.

https://github.com/bitcoin/bitcoin/pull/203.

Also, Gavin brought up a good point on IRC earlier, if one can add a key without knowledge of the password, can an attacker not add a number of their own private keys to your wallet's keypool so that the next time the client sends to one of the keypool addresses, the attacker gets the coins.  It was then discussed as to whether or not this attack should really be considered as write access to bitcoin's data files might mean other exploits as well.  I tend to disagree as a merchant who is running a bitcoin instance to be as secure as possible might have more restrictive access to writing binaries (such as modifying the bitcoin binary to be malicious) and no matter what you do, the attacker cannot make bitcoin spend its coins unless it can trick a human into doing it or unless it can modify bitcoin in some way (in ram/on disk, whatever)

[Hal]

One way to deal with the key-addition attack would be to store a MAC (keyed crypto checksum) with the encrypted data (priv keys). The MAC key could be either an alternate hash of the encryption passphrase, or a hash of a separate MAC passphrase. The MAC passphrase would have to be entered whenever the client started, and the MAC key would be stored in memory while running.

[Matt Corallo]

The only problem I have with that idea, is that users will almost guaranteedly use the same password for both, and that gets rid of the whole point of sipa's suggestion as now you might as well just store the password to the private keys in ram and not bother with the whole public-key encryption of keys.

[Pieter Wuille]

I was specifically trying to avoid the necessity of needing to enter a password for normal operation, except for sending
transactions. Of course, there is another option for those who are more paranoid, and guarantee that the private keys
cannot be tampered with without knowing some (possibly different) password, by using a scheme such as Hal suggests.
However, as soon as an attacker has write access to your wallet.dat (or other files), he can do a lot more, such as overwriting known addresses, giving you a fake block chain (not sure how viable that is), or even overwriting the bitcoin binary. As such, I'm not sure how realistic it is to protect against that scenario.

[Matt Corallo]

I was specifically trying to avoid the necessity of needing to enter a password for normal operation, except for sending
transactions. Of course, there is another option for those who are more paranoid, and guarantee that the private keys
cannot be tampered with without knowing some (possibly different) password, by using a scheme such as Hal suggests.
However, as soon as an attacker has write access to your wallet.dat (or other files), he can do a lot more, such as overwriting known addresses, giving you a fake block chain (not sure how viable that is), or even overwriting the bitcoin binary. As such, I'm not sure how realistic it is to protect against that scenario.

Hm. I disagree.  As I stated above, if I were a properly implementing merchant, my bitcoin node would simply watch for new transactions to my addresses and never spend those coins.  Hence it should have no knowledge of the password (as your suggestion allows).  However, if I were implementing properly, no one would have write access in any way to my bitcoin binary (or any other binary on my system for that matter).  If someone were to be able to run code on my machine under the bitcoin user, they would only have access to writing to the wallet.dat which helps them none, because they don't get my coins, and I have a backup of my wallet.dat which is read-only.

[Pieter Wuille]

Hm. I disagree.  As I stated above, if I were a properly implementing merchant, my bitcoin node would simply watch for new transactions to my addresses and never spend those coins.  Hence it should have no knowledge of the password (as your suggestion allows).  However, if I were implementing properly, no one would have write access in any way to my bitcoin binary (or any other binary on my system for that matter).  If someone were to be able to run code on my machine under the bitcoin user, they would only have access to writing to the wallet.dat which helps them none, because they don't get my coins, and I have a backup of my wallet.dat which is read-only.

Of course, there are various stages of write access an attacker may get. Addr.dat and wallet.dat while stored on offline media would be a first step, write access to the binary a last one. I guess what I was trying to say is that once one gets some write access, all kinds of things are possible, and those may be not realistic to defend against.

What we're trying to solve here, is that if an attacker only has read access to wallet.dat, he cannot spend your coins. To a limited extent, it can try to minimize leaking of keys into swap/memory dumps, but that's already harder to guarantee.

[Pieter Wuille]

By the way, Hal, do you have any specific comments about the scheme, or the key sizes used?

[Matt Corallo]

What we're trying to solve here, is that if an attacker only has read access to wallet.dat, he cannot spend your coins. To a limited extent, it can try to minimize leaking of keys into swap/memory dumps, but that's already harder to guarantee.

I disagree there too.  I want to keep an attacker from spending my coins no matter what kind of access they have.  If I never enter my password, I don't want them to be able to spend my coins even if they modify the bitcoin binary.  If I'm a merchant running bitcoin to handle payment verification, that is possible.  The only problem is if someone has write access to the bitcoin binary (on disk/in memory/etc) they can trick you into thinking they paid.  I don't see such an attack given write access to only ~/.bitcoin (aside from possibly some kind of sybil after modifying the blockchain + addr.dat, but that might die eventually as bitcoin could make a connection to IRC/peer exchange node and then you are fine).  In either case, they still can't spend my coins.

[Steve]

I like love the usability aspect (only needing to enter a passphrase when sending bitcoins)...it makes perfect sense.  As for the concerns over the adding key attack...it might be of some concern to a merchant, but I think for a normal user, it's fine.  It's important to think about these users separately as their needs will no doubt be quite different...more advanced security features that might unnecessarily impair the usability for the average user could be an optional configuration that is off by default.

(note, I have not given much thought about possible holes in this scheme, but on a quick read it seems like a good use of asymmetric cryptography to create a simple, but more secure user experience)

[Matt Corallo]

I like love the usability aspect (only needing to enter a passphrase when sending bitcoins)...it makes perfect sense.  As for the concerns over the adding key attack...it might be of some concern to a merchant, but I think for a normal user, it's fine.  It's important to think about these users separately as their needs will no doubt be quite different...more advanced security features that might unnecessarily impair the usability for the average user could be an optional configuration that is off by default.

(note, I have not given much thought about possible holes in this scheme, but on a quick read it seems like a good use of asymmetric cryptography to create a simple, but more secure user experience)

I suppose its pretty much decided that passwords will be entered at send-time.  The question is how to do the encryption...Do we keep it symmetric (better IMHO) or go asymmetric, like sipa's suggestion here.  The only real difference is how keys are added.  In my scheme, keys are added to the keypool when you send coins, or when calling a topupkeypool rpc command (which requires the wallet password).  If the keypool is empty and the client needs a new address, it has to cycle back around and get an old address (or I suppose it could return an error, but I prefer cycling).  This means you get slightly less anonymity by default, and could mean your backups don't contain as large a keypool as you might like (you should call topupkeypool before backing up for that reason). 
In sipa's scheme, keys can be added freely as they are encrypted asymmetrically.  However, I think the key-addition attack is too big a problem for the potential advantages. 

[Hal]

Sorry I haven't responded, communicating is hard for me these days. This seems to be a very good and sound approach. I would not bother to use longer keys for the master key, chances are the user passphrase will be the weakest part. Also I would stay away from point compression for patent reasons.