Proposal (+ Proof of Concept Software): AES-Encrypted Bitcoin Private Keys

[casascius]

Recently I proposed a private key format for Bitcoin private keys that require a password in order to be used.  Today I have amended my proposal to incorporate AES-based passphrase encryption, and have updated my Casascius Bitcoin Address Utility to function as a proof-of concept.  This proof-of-concept can print passphrase-encrypted paper wallets, as well as decrypt the encrypted private keys.

The proposal: https://en.bitcoin.it/wiki/User:Casascius/Base58Check-encoded_objects_proposal
The proof of concept with source: https://casascius.com/bitaddress.zip

Quick facts about the proposal:

* The keys start with "6p", and look like (for example): 6poiKAg7ZAGGLGfTMcwaqHixuEU3txKjFsDpxfxrmBrY6bAPwLjcfp
* AES256 is used.  SHA256(passphrase) is the key.  To keep the key short, no initialization vector is used, although chaining is retained.
* The spec includes a bit flag for specifying whether the public key should be compressed.
* The spec includes a 14-bit checksum on the passphrase, so most passphrase typos can be detected and rejected.

I wanted to solicit comments on the proposal, as I am considering advancing it toward a BIP.
 
 

[dogisland]

I implement AES encryption as part of the Strongcoin PDF paper wallet.

If memory serves the main issues were compatibility between openssl and other librairies, i.e. I had a few issues getting back and forward compatability between the two. I think the version of open SSL that you use can affect the type of encryption you get.

https://www.strongcoin.com/en/blog/decrypting_private_keys_generated_with_strongcoin

So it might be worth showing how you got the results for the examples you've given (i.e. the commands or tools you used) and trying a few other tools to see if you get the same results.

It's a great idea and we would have standardise paper wallets which would be great.

[jim618]

Hi Casascius,

Rather than using SHA256(password) why not use scrypt as your KDF ?

If you have a look at the proposed/ a MultiBit alpha exists specification for bitcoinj encrypted private keys you can see that scrypt is chosen as the KDF because of its resistance to silicon implementations:

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

I believe scrypt + AES is also used in Armory.
 
You mention that an IV is not used but the first block of AES needs to be initialised with *something*. I suggest you explicitly specify 16 bytes of 0x00 to pin down the spec.

If you do use scrypt as a KDF, specify the exact parameters to be used so that there is no ambiguity (e.g. see the defaults in the google doc.)

[Pieter Wuille]

You mention that an IV is not used but the first block of AES needs to be initialised with *something*. I suggest you explicitly specify 16 bytes of 0x00 to pin down the spec.

I think you're talking about AES in CBC mode, which indeed needs an initialization vector. AES the block cipher itself doesn't, and may be what casascius meant.

Regarding the key derivation: just using SHA256(passphrase) will expose the addresses in the blockchain to a relatively easy brute-force attack (bound by just an EC multiplication, a SHA256 round and a RIPEMD160 round).

[TangibleCryptography]

One thing I would recommend is using something ANYTYHING other than SHA-256 for KDF.   AES-256 SHA-256 is already fast algorithm IT WAS NEVER INTENDED FOR key derivative duties.   However fast as it is, it likely would still be "good enough" ... except for this called mining.  There is already a huge financial incentive for faster and better miners both in algorithms (openCL optimizations, FPGA bitstream optimizations) and in hardware and thus we have seen a huge amount of optimization.  Using SHA-256 allows an attacker to leverage all that "investment" at a very low cost.   Even using SHA-512 would be preferable.

This brings me to my second point.  The actual private key is arbitrary which means encryption isn't the best option.

Why go:
passphrase -> KDF -> key
key & encrypted private key -> decrypted private key

why not just go
passphrase -> KDF (PBKDF2, Scrypt, Bcrypt) -> private key

[jim618]

This brings me to my second point.  The actual private key is arbitrary which means encryption isn't the best option.

Why go:
passphrase -> KDF -> key
key & encrypted private key -> decrypted private key

why not just go
passphrase -> KDF (PBKDF2, Scrypt, Bcrypt) -> private key

The user might have an existing private key that they want to encrypt, rather than create a brand new one.

[TangibleCryptography]

True I hadn't considered that.

The "attacker optimized" KDF is the larger issue.

[gmaxwell]

I wanted to solicit comments on the proposal, as I am considering advancing it toward a BIP.

Please don't submit a BIP for an encryption scheme which is unsalted and uses a weak KDF on user supplied passwords. Especially don't do this with a fast error detection value.

Far less importantly, If there is an error detection value at all, it really should be large enough that errors are very unlikely to make it through— "everything works" and "only the right values work" are both reasonable from a UI perspective (though the latter is much better).  "Unlikely, but likely enough that people will still hit it" is very confusing in practice.

Use of the resulting public address as the salt kills two birds with one stone, since it lets you keep track of which is which before decrypting them, so perhaps you should consider that?

[casascius]

Regarding the key derivation: just using SHA256(passphrase) will expose the addresses in the blockchain to a relatively easy brute-force attack (bound by just an EC multiplication, a SHA256 round and a RIPEMD160 round).

I don't think so: this is not meant as a brainwallet.  This does not specify how to create the Bitcoin private key being encrypted, which should be created with a good RNG.  For someone to be able to mount an attack, they would have to be in possession of the encrypted private key, and would only be able to attack what they possessed, not the blockchain at large.

[casascius]

One thing I would recommend is using something ANYTYHING other than SHA-256 for KDF.   AES-256 is already  fast cipher IT WAS NEVER INTENDED FOR key derivitive duties. 

AES is not being proposed for key derivation.  It is being proposed for encrypting the Bitcoin secret with a key derived from a passphrase.  I may simply amend the proposal and the example to use PBKDF2 HMAC SHA512.

[TangibleCryptography]

Sorry AES-256 was a typo.  "SHA-256 is already a fast algorithm ...."

[casascius]

Far less importantly, If there is an error detection value at all, it really should be large enough that errors are very unlikely to make it through— "everything works" and "only the right values work" are both reasonable from a UI perspective (though the latter is much better).  "Unlikely, but likely enough that people will still hit it" is very confusing in practice.

Perhaps a better choice is CRC-16 from the olden days.  As I understand it, it has the property that single errors or bursts of errors (e.g. typos) cannot, or are highly unlikely, to produce collisions.

Use of the resulting public address as the salt kills two birds with one stone, since it lets you keep track of which is which before decrypting them, so perhaps you should consider that?

The resulting public address isn't known until the payload is decrypted and so cannot be used as salt.  Anything used as salt simply has to be added to the payload, lengthening it.  A possible compromise that comes to mind is to add 32 random bits of salt to the message, which lengthens the message insignificantly, but still makes cracking of a large batch of stolen private keys with the same effort largely impossible.

[casascius]

You mention that an IV is not used but the first block of AES needs to be initialised with *something*. I suggest you explicitly specify 16 bytes of 0x00 to pin down the spec.

I think you're talking about AES in CBC mode, which indeed needs an initialization vector. AES the block cipher itself doesn't, and may be what casascius meant.

I am indeed referring to the block cipher itself.  With what I have proposed using XOR to chain the first block to the second, I think I have very possibly proposed the equivalent of using CBC with an initialization vector of all 0's.

[gmaxwell]

The resulting public address isn't known until the payload is decrypted and so cannot be used as salt.  Anything used as salt simply has to be added to the payload, lengthening it.  A possible compromise that comes to mind is to add 32 random bits of salt to the message, which lengthens the message insignificantly, but still makes cracking of a large batch of stolen private keys with the same effort largely impossible.

Yes, I'm well aware of it— but practical usage will want to include the address too— or you won't be able to tell which encrypted key is which and which you currently need without decrypting them.

"largely impossible", no— well, totally salted it's still unhappily possible especially with the CRC giving you a ~2^16 speedup and such a fast cracking friendly KDF. But, yes, it would largely remove batch and precomputation speedup.   Though a 32 bit random salt takes up more space than an address they you'd be sending anyways. Using the address also gives you absolute correctness confidence, but without giving any speedup at all (its soundly on the expensive side of the KDF).

[kjj]

This looks good to me.  Most of the objections that I had while reading it were dealt with later on.

The KDF is still an issue though.  Best practice would be to just use PBKDF2 and embed the salt for that in the output.  64 bits of salt doesn't fatally lengthen the encrypted key.

If using PBKDF2 with salt as the KDF, AES is overkill.  At that point, considering the random plaintext, XOR would be just as much security.  But AES is cheap in this context, so might as well.

[casascius]

Yes, I'm well aware of it— but practical usage will want to include the address too— or you won't be able to tell which encrypted key is which and which you currently need without decrypting them.

The practical usages I have in mind may very well include the address, but not necessarily encoded within the private key.  If I hand you a paper bitcoin bill protected by a password (which I also give you), the bill likely already has the bitcoin address on the left hand side.  Encoding it within the private key would be redundant.  I wouldn't want to require that these be encoded together, because there are practical applications to having them in separate QR codes (such as funding or checking balance without divulging the private key in any form, encrypted or otherwise).

"largely impossible", no— well, totally salted it's still unhappily possible especially with the CRC giving you a ~2^16 speedup and such a fast cracking friendly KDF. But, yes, it would largely remove batch and precomputation speedup.   Though a 32 bit random salt takes up more space than an address they you'd be sending anyways. Using the address also gives you absolute correctness confidence, but without giving any speedup at all (its soundly on the expensive side of the KDF).

By "largely impossible" I am referring to the fact that anyone who manages to steal a large number of private keys encrypted this way will still have to crack at the keys one-by-one.  I am unsure of how a 32-bit random salt takes up more space than a 160 bit address... 32<160 of course, so I must be misunderstanding something, though if what you're saying is if one must convey both the address and the salt, then the sum is indeed larger, then I agree.

That said though, 32 bits of the address might well accomplish the same thing without the CRC... there is still a 1-in-2^32 chance any given typo may slip through, but I would submit that it's acceptable as a super-rare inconvenience.  If on a paper bill, it means I'm encoding 32 more bits across two QR codes than I would be with one QR code, to me that's an acceptable resource cost to preserve the ability to scan the bitcoin address by itself.

[gmaxwell]

The practical usages I have in mind may very well include the address, but not necessarily encoded within the private key.  If I hand you a paper bitcoin bill protected by a password (which I also give you), the bill likely already has the bitcoin address on the left hand side.  Encoding it within the private key would be redundant.  I wouldn't want to require that these be encoded together, because there are practical applications to having them in separate QR codes (such as funding or checking balance without divulging the private key in any form, encrypted or otherwise).

Right— but why not require that both be provided to decode the private key?

Address:
Passphrase:
Privatekey:

though if what you're saying is if one must convey both the address and the salt, then the sum is indeed larger, then I agree.

Right, Addr+privkey is smaller than addr+privkey+salt.

That said though, 32 bits of the address might well accomplish the same thing without the CRC... there is still a 1-in-2^32 chance any given typo may slip through, but I would submit that it's acceptable as a super-rare inconvenience.  If on a paper bill, it means I'm encoding 32 more bits across two QR codes than I would be with one QR code, to me that's an acceptable resource cost to preserve the ability to scan the bitcoin address by itself.

32 bits of address are still way better for error detection than 16 bits of CRC under most error models.

I'd still rather use the whole address, but this isn't sounding so bad.... now, using a good KDF instead?

[casascius]

Right— but why not require that both be provided to decode the private key?

Address:
Passphrase:
Privatekey:

Because it increases the complexity and the code length needlessly.  If the only benefit is that one-in-4-billion passphrase typos are no longer going to be erroneously accepted, I'd prefer the code length being 15 characters shorter instead.  If I'm making Bitcoin cash, I either have to force users to scan two QR codes instead of one, or redundantly add bulk to the second QR code for no practical benefit.  If I've got bits to spare, I'd rather spend them on more error correcting codewords for the QR code so it's more resilient to damage.

32 bits of address are still way better for error detection than 16 bits of CRC under most error models.

I'd still rather use the whole address, but this isn't sounding so bad.... now, using a good KDF instead?

Would you mind recommending your favorite KDF where code samples for most development platforms are easy to come by?  (Part of why I had originally selected SHA256 was to maximize the likelihood that developers would be able to implement the proposal, since if you're working with Bitcoin it's already there.)

[casascius]

Here is what I think I am going to do with this:

* Change the format so it's 57 characters starting with "6p", which is 38 base58-encoded bytes.
* 14 bits are needed to keep the "6p" prefix intact.  The remainder offers 1 bit for a "compress/no-compress" flag, 4 bytes for salt, and 32 bytes for key.  There is one extra bit.
* The 32 bits of salt will simply be the first 32 bits of SHA256(the expected bitcoin address in ASCII) to double as a typo check.
* The KDF will be scrypt with the following parameters: N=1024, r=8, p=1, and a derived key length of 64 bytes.
* The first 32 bytes returned by script will be used as IV for AES-CBC, the last 32 bytes the key.

The selection of the parameters of scrypt are meant to make the encryption approximate a CPU's cost of generating a bitcoin address, at least within an order of magnitude or three.  One bit is available for specifying different scrypt parameters - at whichever point this is isn't enough, I believe it ought to be done with a new prefix (e.g. 6P instead of 6p) so compatibility and strength is visible to the user.

gmaxwell, would you mind lending your expertise with respect to the nomination of the KDF, the chosen parameters, and the methology?  Also, assuming I'm on the right track, can you recommend what the "other" choice of parameters might ought to be when the extra bit is flipped?  Would you go weaker or stronger, and why?  Thanks in advance.

[kjj]

* The 32 bits of salt will simply be the first 32 bits of SHA256(the expected bitcoin address in ASCII) to double as a typo check.
* The KDF will be scrypt with the following parameters: N=1024, r=8, p=1, and a derived key length of 64 bytes.

The selection of the parameters of scrypt are meant to make the encryption approximate a CPU's cost of generating a bitcoin address, at least within an order of magnitude or three.  One bit is available for specifying different scrypt parameters - at whichever point this is isn't enough, I believe it ought to be done with a new prefix (e.g. 6P instead of 6p) so compatibility and strength is visible to the user.

The defaults for scrypt are N=2¹⁴, r=8, p=1.  (From the original presentation in 2009).  I wouldn't go any lower unless you are pretty sure that these need to be usable on devices with less than 16 MB RAM available.

In my opinion, the salt should be random and stored in the output.  If you base the salt on the output, then you need the encrypted key and the public key both to recover the private key.  This isn't an overwhelming requirement, but still seems silly.