Password-protected private key export format

[samr7]

Private keys in base-58 export format are great for moving between bitcoin wallets, or for safe keeping outside of wallet.dat.  They are currently used by several 3rd party systems, including BitBills, vanitygen, and pywallet.  However, they are very vulnerable to being leaked or stolen if certain security measures aren't taken.  While the built-in bitcoin wallet.dat encryption is able to encrypt private keys stored in wallet.dat, this protection does not extend to exported keys.  The format proposed here is an extension to the base-58 export format with integrated password protection.

This format uses strong encryption and multi-iteration password-based key derivation to encrypt a bitcoin private key.  As with any format of this type, the password can be cracked.  However, by current standards, it is very difficult, of similar difficulty to cracking passwords for WiFi WPA2-PSK.  Complex passwords with no dictionary words of at least nine characters will require more than three years to crack for a very resourceful attacker.

Updated: The current scheme is as follows.  Thanks go to pixelglow for smart suggestions.

privkey = 32-byte EC private key, big-endian form
param = Parameter descriptor byte.

• 0: Brief format -- unpadded cipher, 4-byte salt, HMAC-SHA256 password check value
  
  • pbhash = HMAC-SHA256
  • pbiter = 4096
  • cipher = AES-256-CBC
• 16: PKCS#7-compliant format -- padded cipher, 8-byte salt
  
  • pbhash = HMAC-SHA256
  • pbiter = 4096
  • cipher = AES-256-CBC

For Brief format:
salt = 4-byte random value
key = PBKDF2(password, salt, pbhash, iter)
(key is then split into cipherkeyiv and hmackey.  hmackey is 16 bytes long.)
pwcheck = HMAC-SHA256(hmackey, privkey)
protkey = param | cipher(privkey, cipherkeyiv, unpadded) | pwcheck[0:64] | salt
Result is 45 bytes for most ciphers

For PKCS#7-compliant format:
salt = 8-byte random value
cipherkey = PBKDF2(password, salt, pbhash, iter)
protkey = param | cipher(privkey, cipherkey) | salt
Result is 58 bytes for most ciphers

The protkey value then has a data class byte (32 or 79) prefixed to the beginning, and is base-58 encoded as per the bitcoin function EncodeBase58Check().  Below is an example of a private key password-protected using this scheme, with a test password password1:

Address: 1HacknYhLRpttqGAiBew1fQAKRGnMorkxk
Privkey: 5JmsuCoDBDTPT8oBxx1Vv4cy9Fw14456rt7hvMKmvQY1DES2w6z

Protkey: PsQg61gLtNX6bg7PG8Kw9bpdFEfuP8h1Ri8dAoBjRpV1i1rPPx72EYrGgi7CfWWkbutH
Protkey: 2uhT7zkgeGXpVEw4aYTnCyAvTQ9G1hqSGPPNS5EpC4W62J28euHT8o9CQnKrZCqYwhcHgrxBASsWzYT bF3Qcx
(Careful: the long form above has an extra space added by the forum)

The Brief representation makes some specific compromises to maintain a short representation.  In this mode, the block cipher is performed with no PKCS#7 padding at the end.  Since the padding provides a way to verify the correctness of the password, the HMAC value pwcheck is computed and added to the output.  The pwcheck value is computed using the HMAC-SHA256 hash of the plaintext private key, using 16 bytes of key material taken from the PBKDF2 function as the message key.  This saves a few bytes in the final representation.  The salt value is also only four bytes long, shorter than the recommended eight.

This scheme, unless somebody can poke a big hole in it or recommend a useful change, will show up as an optional output format in the next release of vanitygen, along with a password codec.

A JavaScript example of the password codec is available here.  It does run in your browser but does not transmit keys or passwords over the network.

Bounty: I don't have many bitcoins to throw at this, but 5 BTC go to the first person who can remove the protection from the key below:

1NPHardFPnejsycvne2gvirm5MCr9gnAbf
PsV8XM6n5FvjonHPwwjzqvzA6UXruAAJfQ5VwbXFCJrSQEiQ4gyNNDhuYfL8JUBt6mxt

To sweeten the deal: the password is 14 characters long, with upper and lower case letters only, and contains at least one dictionary word.

[error]

NPHard. Funny.

My first question is, why are you bothering to save 4 bytes here and there? It's not like we're running out of space on our floppy drives?

[dogisland]

NPHard. Funny.

My first question is, why are you bothering to save 4 bytes here and there? It's not like we're running out of space on our floppy drives?

It's useful if you need to type the private key into an import dialog. For example you may keep your private keys in a  paper wallet.

[error]

NPHard. Funny.

My first question is, why are you bothering to save 4 bytes here and there? It's not like we're running out of space on our floppy drives?

It's useful if you need to type the private key into an import dialog. For example you may keep your private keys in a  paper wallet.

Hm, in this case the overall length isn't as important as having visual breaks. Think about the way Microsoft prints its product keys that people have to type in to activate Windows.

[kjj]

The difference between an 8 byte salt and a 4 byte salt isn't 4 bytes, and it isn't a factor of 2.  It is a factor of over 4 billion.  It is the difference between "Got a minute?" and "Sometime after the end of the universe".

In reality, it is probably not that big of a deal.  Precomputing AES tables isn't a trivial task, and even 4 or 5 bits of salt is probably enough to make it impractical for well beyond the potential lifetime of one of these protected keys.

But cryptosystems are designed with defense in depth for very good reasons.  When a weakness in one part is discovered, it is usually not a catastrophe because we have added redundant security measures.

So, the question is:  Is saving a few keystrokes, maybe several times per year for maybe a couple billion users, worth the slight risk that an AES break won't be "phew, gotta upgrade", but instead be "All your addresses are belong to us"?  I would vote for the extra keystrokes, but that might just be me.

By the way, this is a nifty idea.  One thought that came to mind was embedding metadata into the key itself using DER.  Since these keys are not usable on the network, they should maybe not be assigned a key version prefix.

[samr7]

Hm, in this case the overall length isn't as important as having visual breaks. Think about the way Microsoft prints its product keys that people have to type in to activate Windows.

This is a very good point.  Segmentation like this is something that regular bitcoin addresses could benefit from as well -- typing in 34 characters is difficult enough.

So, the password-protected key above could look something like:

PAYxy8-B9zhSG-pbyC7Z-29KRS7-rsPzAc-TF3zSP-myAigb-AJYamt-9GmNws-FT9E95-dGfp6Ri

And the address:

1Hackn-YhLRpt-tqGAiB-ew1fQA-KRGnMo-rkxk

The breaks sure make it easy to remember where you left off, and they're a heck of a lot easier to transcribe to and from paper, or between screens!  But, the password-protected key now only barely fits into an 80-column terminal, and with anything prefixed at the beginning of the line, it will overflow.   

Maybe this idea deserves its own thread.

[casascius]

The difference between an 8 byte salt and a 4 byte salt isn't 4 bytes, and it isn't a factor of 2.  It is a factor of over 4 billion.  It is the difference between "Got a minute?" and "Sometime after the end of the universe".

In reality, it is probably not that big of a deal.  Precomputing AES tables isn't a trivial task, and even 4 or 5 bits of salt is probably enough to make it impractical for well beyond the potential lifetime of one of these protected keys.

But cryptosystems are designed with defense in depth for very good reasons.  When a weakness in one part is discovered, it is usually not a catastrophe because we have added redundant security measures.

So, the question is:  Is saving a few keystrokes, maybe several times per year for maybe a couple billion users, worth the slight risk that an AES break won't be "phew, gotta upgrade", but instead be "All your addresses are belong to us"?  I would vote for the extra keystrokes, but that might just be me.

By the way, this is a nifty idea.  One thought that came to mind was embedding metadata into the key itself using DER.  Since these keys are not usable on the network, they should maybe not be assigned a key version prefix.

I think this argument sort of sidesteps the purpose of salt however.  The salt is not secret - it's coded plainly into the encrypted key and freely available to an attacker - so beyond a certain point, it doesn't really matter how many bits it is.  The whole point of salt if I understand correctly is just to make it infeasible to crack a whole batch at the same time with the same effort (such as with a pre-generated rainbow table), forcing the attacker to concentrate on cracking one key at a time.  If I am right, then the salt needs only enough bits so as to be unlikely to collide with other codes that might be acquired by the same attacker and cracked within the same batch.

EDIT: I would even recommend that fewer bits went into the password check.  Like, maybe as few as 8.  This will make it even more expensive to brute force passwords, as it will result in an enormous number of false positives that can only be checked by doing a time-consuming EC multiply (to derive the bitcoin address) and a database lookup (to see if there are any coins at that address, only to find there are none).  In the event of a typo, even with 8 bits, still a >99% chance it will still be caught.  The password check as it stands is probably just a gift to an attacker.

[samr7]

The difference between an 8 byte salt and a 4 byte salt isn't 4 bytes, and it isn't a factor of 2.  It is a factor of over 4 billion.  It is the difference between "Got a minute?" and "Sometime after the end of the universe".

In reality, it is probably not that big of a deal.  Precomputing AES tables isn't a trivial task, and even 4 or 5 bits of salt is probably enough to make it impractical for well beyond the potential lifetime of one of these protected keys.

But cryptosystems are designed with defense in depth for very good reasons.  When a weakness in one part is discovered, it is usually not a catastrophe because we have added redundant security measures.

You make some very good points about this.

In terms of the purpose of the salt, what would be the usage model for any sort of precomputed table for this problem?  It seems like it would be limited to creating a list of AES keys derived from possible passwords, each of which would have to be tested, still requiring exponential time in the length of the password, but allowing the attacker to circumvent running the expensive PBKDF function for each test.  Is there something sneaker and more devious that an attacker could do with this particular problem?  I don't think this is like trying to build a table for a hash function, where the outputs depend on only the password and the salt, in which case the attacker can index the outputs to the inputs and build a true lookup table or a rainbow table.

Anyway, if that's true, then at 48 bytes per AES key + IV, and 2^32 salt variations of each, the attacker would need to be able to store 192GB per precomputed password.  At least, without some clever way of compressing the keys.  That is a lot easier than 2^64 variants of each, but still seems intractable.

The tradeoff to having four extra bytes of hash would be six extra characters in the encoded output.  Example side-by-side is below:

PAYxy8B9zhSGpbyC7Z29KRS7rsPzAcTF3zSPmyAigbAJYamt9GmNwsFT9E95dGfp6Ri
3W3qzi2Sow4o7LP7jwwnrmqiiGxyMcwLdubKxYhNy4J63eigN3jz7avYqSWfGwxz3nMDDXwwc

Edit: It's possible, using a smaller value for the type byte, to reduce it to five extra characters.

Your point about weakness mitigation is well taken though, and the tradeoff may be worth it.

EDIT: I would even recommend that fewer bits went into the password check.  Like, maybe as few as 8.  This will make it even more expensive to brute force passwords, as it will result in an enormous number of false positives that can only be checked by doing a time-consuming EC multiply (to derive the bitcoin address) and a database lookup (to see if there are any coins at that address, only to find there are none).  In the event of a typo, even with 8 bits, still a >99% chance it will still be caught.  The password check as it stands is probably just a gift to an attacker.

The PBKDF function here requires 8192 rounds of the SHA256 hash function, so it should already be a lot more expensive than computing the bitcoin address and looking it up in a list.  Even if the attacker was using a table, having to do an EC operation as often as every 2^8 keys probably won't cause a big slowdown.  But, it will make the password cracker a bit more complicated.

For the one person who gets a letter of their password wrong, and is unlucky enough to have it silently accepted and mapped to the wrong account, and either the bitcoin address isn't known or isn't compared to the expected value, they better hope the password-protected version of their key wasn't discarded.

[pixelglow]

The scheme that I proposed to dogisland of the StrongCoin project is as follows.

privkey = 32-byte EC private key, big-endian form
salt = 4-byte random salt value
symkey = PBKDF(password, salt, SHA256, 4096)
pwcheck = SHA256(SHA256(privkey | salt))
protkey = AES-CBC-256(privkey, symkey) | pwcheck[0:64] | salt

The 44-byte protkey value then has a type byte (136) prefixed to the beginning, and is base-58 encoded as per the bitcoin function EncodeBase58Check().  

Interesting, although your layering/composing of different cryptographic schemes may come back to bite you.

As I see it, you want to encrypt the password and also verify that the encrypted bits are unchanged. Here's a slight modification of the above:

privkey = 32-byte EC private key, big-endian form
salt = 4-byte random salt value
symkey = PBKDF2(HMAC-SHA1, password, salt, 4096, 64)
cryptedprivkey = (privkey XOR symkey[0:32])
pwcheck = HMAC-SHA1(symkey[33:64],cryptedprivkey)
protkey = cryptedprivkey | pwcheck | salt

• You should use the more recent PBKDF2 (http://www.di-mgt.com.au/cryptoKDFs.html), which allows you to produce arbitrary length keys. In this case we're generating a 64-byte length key, half of which we'll use for encryption and the other half for authentication.
• Next we encrypt the privkey with half the symkey by XOR'ing them together, a simple stream cipher. This avoids the use of AES in client code (slow in Javascript?, missing an initialization vector, plaintext length < AES block size of 128 bits) and should be pretty safe. Stream ciphers like RC4 are simply a random keystream XOR with the plaintext and are difficult to break, provided the random keystream is truly unpredictable and you never repeat the key. The trouble with stream ciphers then manifests when you have a large enough chunk of data to encode, then without a proper CPRNG like RC4 the keystream may repeat etc. and thus block ciphers under CBC become useful. Since we have a 32-byte private key and a 32-byte symkey to XOR together, this should not be the issue.
• We then use a MAC, specifically a HMAC-SHA1, to act as the password check against modification. We use the second half of the symkey as the secret. HMAC's are particularly designed for message authentication.

Alternatively (safer/more paranoid) you could use two salts to produce two 32-byte keys, one for the encryption, one for the authentication.

[samr7]

Interesting, although your layering/composing of different cryptographic schemes may come back to bite you.

As I see it, you want to encrypt the password and also verify that the encrypted bits are unchanged. Here's a slight modification of the above:

privkey = 32-byte EC private key, big-endian form
salt = 4-byte random salt value
symkey = PBKDF2(HMAC-SHA1, password, salt, 4096, 64)
cryptedprivkey = (privkey XOR symkey[0:32])
pwcheck = HMAC-SHA1(symkey[33:64],cryptedprivkey)
protkey = cryptedprivkey | pwcheck | salt

• You should use the more recent PBKDF2 (http://www.di-mgt.com.au/cryptoKDFs.html), which allows you to produce arbitrary length keys. In this case we're generating a 64-byte length key, half of which we'll use for encryption and the other half for authentication.
• Next we encrypt the privkey with half the symkey by XOR'ing them together, a simple stream cipher. This avoids the use of AES in client code (slow in Javascript?, missing an initialization vector, plaintext length < AES block size of 128 bits) and should be pretty safe. Stream ciphers like RC4 are simply a random keystream XOR with the plaintext and are difficult to break, provided the random keystream is truly unpredictable and you never repeat the key. The trouble with stream ciphers then manifests when you have a large enough chunk of data to encode, then without a proper CPRNG like RC4 the keystream may repeat etc. and thus block ciphers under CBC become useful. Since we have a 32-byte private key and a 32-byte symkey to XOR together, this should not be the issue.
• We then use a MAC, specifically a HMAC-SHA1, to act as the password check against modification. We use the second half of the symkey as the secret. HMAC's are particularly designed for message authentication.

Alternatively (safer/more paranoid) you could use two salts to produce two 32-byte keys, one for the encryption, one for the authentication.

Excellent!!

Pixelglow, you really seem to know your stuff, are you a pro??

The PBKDF that I've been using isn't exactly PKCS#5 v1, it's actually OpenSSL's EVP_BytesToKey().  It's similar but will produce arbitrarily large key material.  Otherwise, there certainly wouldn't be enough key material for an AES IV using SHA256.

Regardless, using PBKDF2 with an HMAC function would seem to be a very desirable change, and also appears to be very easy to get with OpenSSL.

Regarding pwcheck, the use of an HMAC function there with some additional key material also seems like the appropriate tool for the job, more so than my hacked-together mess.  Can't really say no to that either.

Would you recommend HMAC-SHA1 over HMAC-SHA256?

Somebody smart said that a work is finished not when everything that can be added to it has been added, but when everything that can be removed has been removed.  AES may fit into this category.  However, other similar password-protection schemes, including bitcoin's built-in wallet encryption, also use AES for fixed-size private keys, and it's nerve-racking to replace it with XOR, even though it may be the correct thing to do.

Thank you very much!!

[pixelglow]

Pixelglow, you really seem to know your stuff, are you a pro??

I'm only a regular programmer with a math background, hence the interest in cryptography. I once worked on a font DRM scheme which used crypto, and I'm currently working on an Australian bitcoin exchange that will feature crypto as well. The rest of it is just google  .

The PBKDF that I've been using isn't exactly PKCS#5 v1, it's actually OpenSSL's EVP_BytesToKey().  It's similar but will produce arbitrarily large key material.  Otherwise, there certainly wouldn't be enough key material for an AES IV using SHA256.

http://www.openssl.org/docs/crypto/EVP_BytesToKey.html seems to indicate you should move to PKCS#5 v2.0, which is PBKDF2.

Regardless, using PBKDF2 with an HMAC function would seem to be a very desirable change, and also appears to be very easy to get with OpenSSL.

Indeed, there is the PKCS5_PBKDF2_HMAC_SHA1 function in OpenSSL. I just submitted a patch to node.js to incorporate this: https://github.com/joyent/node/pull/1491

Regarding pwcheck, the use of an HMAC function there with some additional key material also seems like the appropriate tool for the job, more so than my hacked-together mess.  Can't really say no to that either.

Would you recommend HMAC-SHA1 over HMAC-SHA256?

RFC 2104 (http://tools.ietf.org/html/rfc2104) seems to think that any half-decent cryptohash will do, even MD5 (!), since HMAC has a secret key which greatly expands the amount of computation you need to do to break it. I suggested HMAC-SHA1 since the PBKDF2 in OpenSSL is based on it (symmetry!), it seems to be used often enough (newer schemes have less cryptanalysis done, could have flaws you don't anticipate esp. used in tandem like with HMAC) and produces a smaller output.

Somebody smart said that a work is finished not when everything that can be added to it has been added, but when everything that can be removed has been removed.  AES may fit into this category.  However, other similar password-protection schemes, including bitcoin's built-in wallet encryption, also use AES for fixed-size private keys, and it's nerve-racking to replace it with XOR, even though it may be the correct thing to do.

Indeed. Simple schemes work best sometimes in crypto since less can go wrong. As for using XOR, check out wikipedia's article on Vernam ciphers: http://en.wikipedia.org/wiki/Vernam_cipher. TL;DR: so long as the key is truly random, as large as the plaintext and never reused in whole or part, it should be unbreakable. Obviously we can't get the first one 100% since we're starting with a human password and PBKDF2 I think doesn't make any guarantees about the randomness of the result. The second requirement is true. The last requirement should be ensured by the use of random salts.

Does bitcoin encryption use AES with a single key on the entire wallet, or AES on individual keys (without an IV or starting at the same point)? The former is pretty sensible. The latter can be dangerous since you are effectively reusing the key.

[Pieter Wuille]

I'm not sure what your use case is here. Encrypted dumps of the wallet are obviously useful, but I think they come in two categories:

1) combined with encrypted wallet, just a dump of the encrypted keys therein. This would allow you to export and import dumps without providing a password. I believe this is the safest option, but it would be inherently implementation-specific (the encryption inside bitcoin, as planned for 0.4.0, uses EVP-SHA512 keys derived from a password, used to encrypt a 256-bit master key using AES256-CBC, the wallet keys themselves are encrypted using this master key using AES256-CBC, with the hash of their pubkey as IV).

2) a portable format for exchanging wallets (hopefully between several applications). if the encryption is independent from that of the wallet storage itself, that means exporting requires knowledge of the wallet passphrase + another key to encrypt the dump with. Although there is definitely merit in doing this inside bitcoin itself, i don't think there is anything better than doing a normal wallet dump + GPG/OpenSSL/... encrypting it.

[dogisland]

I'm not sure what your use case is here. Encrypted dumps of the wallet are obviously useful, but I think they come in two categories:

It's not about dumping the wallet but a shared scheme for encrypting private keys.

A possible use case

You could generate an offline paper wallet containing a number of public Bitcoin addresses and their corresponding private keys. The private keys will be encrypted with a password only you know but in a standard format.

The main reason to have a standard encryption for the private key is that when you want to redeem coins against those addresses the bitcoin client or an online wallet will be able to decrypt them for you when you give your password.

Also an online wallet could store the encrypted keys for you. You don't have to worry about the service being attacked, the private keys would be worthless without the passwords. (assuming strong passwords).

Hope this helps.

[Pieter Wuille]

Right, of course. I just generalized things a bit.

If you're talking about private keys, the distiction remains: either you want to export/import what is in an already encrypted wallet (useful for backup), or you want to do encryption separately. The intent here seems to be the second case, which is fine. It just means you'll need to both the wallet passphrase and the key password ready if you want to import.

Also, considering the used version byte, could you follow this thread? I'd say encrypted privkeys form a new data class.

[samr7]

If you're talking about private keys, the distiction remains: either you want to export/import what is in an already encrypted wallet (useful for backup), or you want to do encryption separately. The intent here seems to be the second case, which is fine. It just means you'll need to both the wallet passphrase and the key password ready if you want to import.

Absolutely!  The goal is to handle the keying independently and not depend on the master key of a specific encrypted wallet.  So, if it were used for exporting, it wouldn't be as convenient as "backupwallet," and at least one export password would be required.  But it could be implemented to be more convenient than dumpwallet + GPG.

Also, considering the used version byte, could you follow this thread? I'd say encrypted privkeys form a new data class.

Thanks!  I posted a note to the list and referenced that thread.

[Gavin Andresen]

Two different encryption schemes and/or passwords seems like a bad idea to me, both from a code maintenance/security point of view and from a usability point-of-view.

Can you expand on "private keys in base-58 export format are great for swapping around" -- what's the use case?  Who are you swapping with, and how?

[kjj]

We are at the point where outside utilities are starting to need more access to the wallet.  See pywallet, for an example of a very useful tool that I wish I didn't have to shut down my client to use.

One option would be to have the client open the wallet database without a total lock, so that other things could use it at the same time.  In that case, using per-key encryption inside the wallet would be a good thing for sure.

But most of the things that would be enabled by allowing concurrent wallet access could also be done through RPC, if we can just make the right RPC commands.  Oh, and we'll probably need at least a little bit of granularity in the RPC security system.

At any rate, these encrypted single keys would always be useful as a transfer format for moving keys between servers, archiving onto paper or CDs, offline generation, etc.  Whether they are useful as an alternate storage format inside the wallet will depend on whether we go with RPC or unlocking the database.

[error]

I'm convinced at this point that the on-disk wallet format needs to be completely scrapped and redesigned from scratch. Unfortunately, I'm not likely to have the spare time to devote to working on this.

[kinlo]

If special attention should go to entering the private key by keyboard, making it short and so on, shouldn't the format foresee multiple checksums to detect typing errors instead of the standard hash check provided by EncodeBase58Check?

If you would split the long private key in - let's say -  6 blocks, a checksum per block instead of one on the whole string as EncodeBase58Check does right now, gui's that allow entering the key in parts  would be capable of hilighting the specific part in red that contains a typing error, instead of invalidating the whole input.

[samr7]

Two different encryption schemes and/or passwords seems like a bad idea to me, both from a code maintenance/security point of view and from a usability point-of-view.

Can you expand on "private keys in base-58 export format are great for swapping around" -- what's the use case?  Who are you swapping with, and how?

Swapping around means storing a private key outside of a wallet.dat, either to be imported into another wallet.dat or another bitcoin client implementation.  It's an interchange format, not a specific wallet implementation.

The format proposed here is an extension that allows an exported private key to be password-protected.  Naturally, if it is to be interchangeable with another bitcoin wallet or another implementation, it shouldn't/can't be protected using the same password or master key as the wallet from which it came (if that wallet is encrypted).  The initial use case is to allow someone to use vanitygen to generate an address, and securely store the private key until it is later imported into a client.

Anyway, I think this proposal is orthogonal to the encryption of wallet.dat.

If you would rather this format follow the same password-derivation and encryption scheme as the master keys of the bitcoin wallet encryption system, that's certainly possible.  They're already quite similar, and until pixelglow came out and recommended PBKDF2, they both used EVP_BytesToKey().  I don't think the use cases between the wallet master key and a password-protected export format are quite the same though.