BIP 38 Discussion Thread - Passphrase-Protected Private Key Format

[casascius]

I am starting a discussion thread on the technical merits and cryptographic soundness of my recent proposal for passphrase-protected private keys.

https://en.bitcoin.it/wiki/BIP_0038

The core features are:
* Encrypted keys are fifty-eight Base58Check-encoded characters starting with "6P"
* Encryption uses AES-256.  Key derivation uses scrypt.  Parameters are fixed at 16384,8,8; unused space in key format allows future specification changes.
* Typo detection is a 32-bit hash of the resulting bitcoin address and requires the full derivation and decryption process in order to be checked, so it does not provide any speedup to crackers.  These 32 bits are also used as salt.
* An elliptic curve multiplication step is selectable, allowing a scheme where Alice can select a passphrase and Bob can generate and fund bitcoin addresses that only Alice can decrypt; the specification describes what Alice must give to Bob to let that happen without divulging her passphrase, and defines a Base58Check-encoded format for it.
* Both compressed and uncompressed public key formats are selectable.

Fully functional proof-of-concept code has been published at https://github.com/casascius/Bitcoin-Address-Utility

I recently ran a contest where I created an encrypted paper wallet with a 5-letter password, loaded it with 10 BTC and published the encrypted private key, asking people to crack at it.  It took two days, the eventual winner threw 20 machines at it, and won only after I had leaked enough information about the password to reduce the search set to under 6 million possible passwords.  His estimate on how long it would have taken him to search the entire (reduced) search set was 45 to 60 hours.

My hope is that my proposal will be viewed as secure enough for implementation everywhere as a standard, anywhere someone is asked to provide a private key for any reason.  This includes any private key sweep or import functions in the Satoshi client.  In a user interface workflow, if a password-protected private key is entered, this should be auto-detected and the user would be asked: "Enter Password".  In an RPC context, the password would be another argument to calls.

[wtfvanity]

I think I checked in UI elements to allow batch entry, but haven't written the code to actually parse them.

This is in reply to your other thread, but single input works, the multiple does not. Regardless of what I enter, it does just say unrecognized. Looking at your code, button for multiple just allows multiline and changes textbox1. The button1 sends the text off to an interpreter that doesn't recognize more than one address at a time.

Something else I noticed, if I add an address only, it says private key, unknown. Is there anyway to tell it what the private key is if I enter it backwards like that?

[J-Norm]

Could this be modified so that the amount of CPU per guess could be configured? For example if you had to hash something 100 times instead of once to get the key instead of 1 time it would take 6000 hours to crack instead of 60. But if you know the password it will still only take a few moments to decode.

Not sure about the exact internals of your protocol but something like that would be nice and really annoy the brute force attackers.

[wtfvanity]

Could this be modified so that the amount of CPU per guess could be configured? For example if you had to hash something 100 times instead of once to get the key instead of 1 time it would take 6000 hours to crack instead of 60. But if you know the password it will still only take a few moments to decode.

Not sure about the exact internals of your protocol but something like that would be nice and really annoy the brute force attackers.

As he has it right now, it takes about a second to decode on my machine if you know the password. This would make it so that this could run on a phone in javascript at this difficulty when the password is known. Same machine would take half a year to crack 5 character single case. Make that upper lower and you're 12 years. Obviously, he had twenty machines and was not using the un-compiled code. For waht he is proposing the current hashing length is sufficient. If I'm calculating all of this right make it alpha numeric upper lower and that same thing takes 29 years on my single computer.

[J-Norm]

I agree that the current difficulty is sufficient. I thought the difficulty being configurable would be a nice feature, but you can always just use a longer password.

Code:

dd if=/dev/random bs=1M count=1 | sha256sum

^^ Damn good password.

[wtfvanity]

I agree that the current difficulty is sufficient. I thought the difficulty being configurable would be a nice feature, but you can always just use a longer password.

Code:

dd if=/dev/random bs=1M count=1 | sha256sum

^^ Damn good password.

Hard to remember though. 5 alphanumeric shouldn't be too hard to remember without having to write it down or mistype a very long password.

[J-Norm]

I agree that the current difficulty is sufficient. I thought the difficulty being configurable would be a nice feature, but you can always just use a longer password.

Code:

dd if=/dev/random bs=1M count=1 | sha256sum

^^ Damn good password.

Hard to remember though. 5 alphanumeric shouldn't be too hard to remember without having to write it down or mistype a very long password.

Not only is it hard to remember, it has enough bits to be a private key itself. I was making a little joke, not very good at jokes. 

[wtfvanity]

I agree that the current difficulty is sufficient. I thought the difficulty being configurable would be a nice feature, but you can always just use a longer password.

Code:

dd if=/dev/random bs=1M count=1 | sha256sum

^^ Damn good password.

Hard to remember though. 5 alphanumeric shouldn't be too hard to remember without having to write it down or mistype a very long password.

Not only is it hard to remember, it has enough bits to be a private key itself. I was making a little joke, not very good at jokes. 

Over my head, sorry.    Get in a mind set discussion about certain things and the jokes start missing.

[Nyhm]

The ability to generate addresses without knowledge of (exposure to) the private keys is masterful. I've studied cryptography (and even digital cash) in grad school and have practiced applied cryptography professionally for some years, but I'd have to really get back into my studies to properly analyze your methods. If they're sound, then this is a wonderful capability for Bitcoin. The BIP itself is written very clearly and concisely.

I know this comment isn't very substantive to the discussion, but I wanted to thank you for your efforts. I already thought you were awesome for producing physical Bitcoin coins (combining two of my favorite things: coinage and cryptography), so now you're pretty much my new hero.

EDIT: Here's something more substantive: This would solve the Vanity Address Service conundrum. Scenario: Alice wants a Vanity Address, but does not have the CPU power to generate one. Alice sends Bob her intermediate_passphrase_string. Bob has lots of compute power and can generate addresses without any knowledge of the private keys. When Alice's desired vanity string is found, Bob can provide the address and encrypted key to Alice, who can decrypt the private key and use it without fear that Bob will exploit it later. Bob can even show proof that he has found a valid vanity address before releasing the encrypted private key back to Alice (e.g., to request payment for service).

I've seen something like this proposed for vanity addresses before, but I believe this BIP solves it rather well. Is this accurate?

UPDATE: ... and now I have yet another idea ...

[Red Emerald]

EDIT: Here's something more substantive: This would solve the Vanity Address Service conundrum. Scenario: Alice wants a Vanity Address, but does not have the CPU power to generate one. Alice sends Bob her intermediate_passphrase_string. Bob has lots of compute power and can generate addresses without any knowledge of the private keys. When Alice's desired vanity string is found, Bob can provide the address and encrypted key to Alice, who can decrypt the private key and use it without fear that Bob will exploit it later. Bob can even show proof that he has found a valid vanity address before releasing the encrypted private key back to Alice (e.g., to request payment for service).

I've seen something like this proposed for vanity addresses before, but I believe this BIP solves it rather well. Is this accurate?

I think this would work for vanity mining.  That problem does already has some solutions.  https://vanitypool.appspot.com/


How would proof be given?

[casascius]

EDIT: Here's something more substantive: This would solve the Vanity Address Service conundrum. Scenario: Alice wants a Vanity Address, but does not have the CPU power to generate one. Alice sends Bob her intermediate_passphrase_string. Bob has lots of compute power and can generate addresses without any knowledge of the private keys. When Alice's desired vanity string is found, Bob can provide the address and encrypted key to Alice, who can decrypt the private key and use it without fear that Bob will exploit it later. Bob can even show proof that he has found a valid vanity address before releasing the encrypted private key back to Alice (e.g., to request payment for service).

I've seen something like this proposed for vanity addresses before, but I believe this BIP solves it rather well. Is this accurate?

Yeah, but unfortunately it works not a ton better than the standard practice now: send a public key, keep the private key, and combine them with EC addition (my utility can do this as well).

The intermediate code is just as ugly as the public key, and the only advantage would be that the original requestor would keep around a passphrase instead of a private key.  That's not a hugely useful improvement because whether it's a phrase or a key, it's no longer needed once the vanity address is generated... the user won't have an interest in memorizing it or trying to engrave it in limited space.

Also AFAIK, vanity generation MUST use EC addition and not multiplication, otherwise it would run way too slow to be useful.  EC addition has a security flaw but it only affects a very specific use case and does not affect vanity generation.

[Nyhm]

Thank you for the clarifications. I knew there was some vanity generation technique, but I was not familiar with the process. I see that BIP38 is particularly designed for use cases when the user wants a passphrase-based key. (I'll go read more about the EC addition process. When I was studying crypto, we didn't get into EC so much as factorization-based algorithms, and I really want to solidify my understanding of the roots of Bitcoin.) Inspiring work - thank you.

[thanke]

What is the purpose of AES encryption in the second method (EC multiply mode)?
You could simply place seedb unencrypted in the encrypted private key instead of encryptedpart1 and 2.

[thanke]

EC addition has a security flaw but it only affects a very specific use case and does not affect vanity generation.

What is the security flaw?

[2_Thumbs_Up]

I am starting a discussion thread on the technical merits and cryptographic soundness of my recent proposal for passphrase-protected private keys.

https://en.bitcoin.it/wiki/BIP_0038

The core features are:
* Encrypted keys are fifty-eight Base58Check-encoded characters starting with "6P"
* Encryption uses AES-256.  Key derivation uses scrypt.  Parameters are fixed at 16384,8,8; unused space in key format allows future specification changes.
* Typo detection is a 32-bit hash of the resulting bitcoin address and requires the full derivation and decryption process in order to be checked, so it does not provide any speedup to crackers.  These 32 bits are also used as salt.
* An elliptic curve multiplication step is selectable, allowing a scheme where Alice can select a passphrase and Bob can generate and fund bitcoin addresses that only Alice can decrypt; the specification describes what Alice must give to Bob to let that happen without divulging her passphrase, and defines a Base58Check-encoded format for it.
* Both compressed and uncompressed public key formats are selectable.

Fully functional proof-of-concept code has been published at https://github.com/casascius/Bitcoin-Address-Utility

I recently ran a contest where I created an encrypted paper wallet with a 5-letter password, loaded it with 10 BTC and published the encrypted private key, asking people to crack at it.  It took two days, the eventual winner threw 20 machines at it, and won only after I had leaked enough information about the password to reduce the search set to under 6 million possible passwords.  His estimate on how long it would have taken him to search the entire (reduced) search set was 45 to 60 hours.

My hope is that my proposal will be viewed as secure enough for implementation everywhere as a standard, anywhere someone is asked to provide a private key for any reason.  This includes any private key sweep or import functions in the Satoshi client.  In a user interface workflow, if a password-protected private key is entered, this should be auto-detected and the user would be asked: "Enter Password".  In an RPC context, the password would be another argument to calls.

Say Bob creates an enrypted bitcoin adress. But rather than sending this to Alice he sends the data to Charlie. I assume there is a trivial way for Bob to proove to Charlie what the adress is, right? I'm asking cause I believe this could have big implications for various digital cash systems.

See:
https://bitcointalk.org/index.php?topic=129594.msg1388631#msg1388631

[casascius]

Say Bob creates an enrypted bitcoin adress. But rather than sending this to Alice he sends the data to Charlie. I assume there is a trivial way for Bob to proove to Charlie what the adress is, right? I'm asking cause I believe this could have big implications for various digital cash systems.

See:
https://bitcointalk.org/index.php?topic=129594.msg1388631#msg1388631

If Bob were to disclose both the "intermediate code" and the encrypted private key he created to Charlie, then Charlie could determine that the two of them are associated, and could independently calculate the bitcoin address.  With the intermediate code, Charlie can "decrypt" the AES encryption on the key material generated by Bob, which is how he can get the bitcoin address, but he is still missing Alice's key material, which is only available with the original passphrase, so he can't get the private key actually needed to spend the funds.

A proposal that I'm drafting has exactly the same property you describe, possibly for much the same purpose you describe, but has more features, namely, Eddie the escrow agent being able to release the funds to Alice or Bob, while having no access to take them for himself.  The proposal also does not rely on Eddie for the funds to be released to Bob as would be the typical case if the transaction is successful.

Look at this (which could have fundamental unresolved issues being a draft in progress).

https://en.bitcoin.it/wiki/User:Casascius/Escrow_scheme_draft

[Stephen Gornick]

* Encrypted keys are fifty-eight Base58Check-encoded characters starting with "6P"

Would you mind updating this wiki article to reflect this?
 - http://en.bitcoin.it/wiki/List_of_address_prefixes

[thanke]

What is the purpose of AES encryption in the second method (EC multiply mode)?
You could simply place seedb unencrypted in the encrypted private key instead of encryptedpart1 and 2.

Bump.

Question is still being asked. If the party generating the addresses, knowing seedb, cannot compute the private keys then why is seedb ever encrypted? The address passpoint*factorb cannot be redeemed without knowing passphrase and ownersalt.

Is there another reason to encrypt seedb?

[casascius]

What is the purpose of AES encryption in the second method (EC multiply mode)?
You could simply place seedb unencrypted in the encrypted private key instead of encryptedpart1 and 2.

Bump.

Question is still being asked. If the party generating the addresses, knowing seedb, cannot compute the private keys then why is seedb ever encrypted? The address passpoint*factorb cannot be redeemed without knowing passphrase and ownersalt.

Is there another reason to encrypt seedb?

Because it can be, and little more.

The same reason we use SHA256(SHA256(whatever)) instead of SHA256(whatever).

Because, I figure why give an attacker 1 factor when we can give him 0 factors at pretty much no extra cost.  Also, the attacker could have some advantage if he has another encrypted private key and knows the corresponding unencrypted private key (but not the factors) for a different key pair based on the same intermediate code.  If such an attack exists, I don't know what it is, but I made that attack far more difficult by denying the attacker the freebie he would need to execute it.

Someone else had also pointed out something that I understood like this: if someone were to make an ASIC to crack these, his job just got that much harder.

[thanke]

What is the purpose of AES encryption in the second method (EC multiply mode)?
You could simply place seedb unencrypted in the encrypted private key instead of encryptedpart1 and 2.

Bump.

Question is still being asked. If the party generating the addresses, knowing seedb, cannot compute the private keys then why is seedb ever encrypted? The address passpoint*factorb cannot be redeemed without knowing passphrase and ownersalt.

Is there another reason to encrypt seedb?

Because it can be, and little more.

The same reason we use SHA256(SHA256(whatever)) instead of SHA256(whatever).

I don't know why we use double-hash.

Because, I figure why give an attacker 1 factor when we can give him 0 factors at pretty much no extra cost.  Also, the attacker could have some advantage if he has another encrypted private key and knows the corresponding unencrypted private key (but not the factors) for a different key pair based on the same intermediate code.  If such an attack exists, I don't know what it is, but I made that attack far more difficult by denying the attacker the freebie he would need to execute it.

The attack could be: You have two encrypted keys, decrypt one of them, partially spend it and keep the decrypted version around for later spending. Suppose they are both based on the same intermediate code and produced without the AES encryption part. If someone finds them (one decrypted, one encrypted), then that person can spend also the encrypted one. So I see your point for AES now, unless you forbid reusing intermediate codes.

Different question: what is the purpose of the confirmation code? If I can decrypt the encrypted key with my passphrase I can also be sure the address depends on the passphrase, and that it is only spendable with the passphrase. No need for a confirmation code it seems.