BIP 38 Discussion Thread - Passphrase-Protected Private Key Format

[Nyhm]

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.

Recommended reading: Practical Cryptography, Ferguson & Schneier

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.

Confirmation code allows generator (Bob) to prove he has produced an encrypted private key without revealing the private key. When the confirmation code is given to the owner (Alice), they both now have an address that can be funded, but neither can spend the funds. Alice needs the encrypted private key (to decrypt), or Bob needs the passphrase (to decrypt).

It's almost a zero-knowledge transaction, in that both parties know there is a private key, but neither knows what it is.

[casascius]

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

Satoshi has essentially described it as a cheap measure of protection against weaknesses found in SHA256.  If people start finding them, we're going to hear about weaknesses in SHA256(x) long before we'll ever hear about weaknesses in SHA256(SHA256(x)).  It gives us a generous measure of time to do something about any that are found.

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.

If you don't have access to the encrypted key because someone else generated it, this knowledge is useful.

For example, you bought a two-factor physical bitcoin and the encrypted key is inside.  You'd have to destroy the hologram to see the encrypted key.

Or you're doing an escrow arrangement, and the person with the encrypted key is the one who is supposed to get paid (so of course he isn't giving you the key to take your money back), and he's asking you to pay address X.  It's useful to know that address X depends on your passphrase and that you have some measure of control over the funds sent there, and isn't one he just pulled from his own wallet.

[thanke]

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

Recommended reading: Practical Cryptography, Ferguson & Schneier

I meant to say don't know why we use double hash here in BIP 0038. The use factorb=SHA256(SHA256(seedb))
is just a randomness expander from 24 bytes to 32 bytes. Collision or pre-image resistance is irrelevant here. Since seedb is supposed to be random and we are only expanding so few bytes, any statistically good randomness expander suffices (I could be even cryptographically weak, like linear recurrence equations). I don't want to suggest to replace it, just don't see why a double-hash is used.

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.

Confirmation code allows generator (Bob) to prove he has produced an encrypted private key without revealing the private key. When the confirmation code is given to the owner (Alice), they both now have an address that can be funded, but neither can spend the funds. Alice needs the encrypted private key (to decrypt), or Bob needs the passphrase (to decrypt).

It's almost a zero-knowledge transaction, in that both parties know there is a private key, but neither knows what it is.

I see the point now, thanks.

[thanke]

Satoshi has essentially described it as a cheap measure of protection against weaknesses found in SHA256.  If people start finding them, we're going to hear about weaknesses in SHA256(x) long before we'll ever hear about weaknesses in SHA256(SHA256(x)).  It gives us a generous measure of time to do something about any that are found.

If you have a preimage attack against H then you also have one against double-H. Collisions may be a different story, but don't really know of any part of bitcoin where collisions are relevant. Sure this has been discussed somewhere.

[EDIT]
If you have a second-preimage attack against H then you also have one against double-H.
If you have a collision for H then you also have one for double-H.

What becomes (apparently) more difficult with double-H is preimages of "target sets" rather than "target elements", i.e. finding x with H(x) in some given set S. Every round of H that you add may make the target set significantly smaller, possibly down to one element already for the second round. The reason for using doube-SHA256 for the mining target might be to smooth the difficulty adjustment in case a preimage attack for a large target set suddenly becomes available. Or, if such an attack becomes available to a single miner, to lower his advantage over all others.
[/EDIT]

[casascius]

I meant to say don't know why we use double hash here in BIP 0038. The use factorb=SHA256(SHA256(seedb))
is just a randomness expander from 24 bytes to 32 bytes. Collision or pre-image resistance is irrelevant here. Since seedb is supposed to be random and we are only expanding so few bytes, any statistically good randomness expander suffices (I could be even cryptographically weak, like linear recurrence equations). I don't want to suggest to replace it, just don't see why a double-hash is used.

That makes sense.  Asked that way, the answer is more that doubling SHA256 is done so consistently (often for the reason stated) throughout the Bitcoin codebase that there is no sense in not keeping it the same just for style's sake.

[thanke]

Shouldn't reusing the intermediate_code be forbidden?

If intermediate_code is reused then the party generating the encrypted keys can conspire with someone who gets to see a lot of privkeys (some big exchange) and wait for one of its customer to reveal some privkey from one of these generated encrypted keys. Sooner or later this will happen. Then the conspirers can take over the whole series of coins based on the same intermediate_code. An issuer of physical coins should protect himself from such accusations by not accepting the same intermediate_code twice.

[casascius]

Shouldn't reusing the intermediate_code be forbidden?

If intermediate_code is reused then the party generating the encrypted keys can conspire with someone who gets to see a lot of privkeys (some big exchange) and wait for one of its customer to reveal some privkey from one of these generated encrypted keys. Sooner or later this will happen. Then the conspirers can take over the whole series of coins based on the same intermediate_code. An issuer of physical coins should protect himself from such accusations by not accepting the same intermediate_code twice.

Thanks for asking.  Let me break this down into an intermediate code's component parts.

An intermediate code consists of salt, and an EC point based on the passphrase plus that salt.

Whether or not someone should reuse the same passphrase is their prerogative and outside the scope of the spec, so I'll eliminate that for consideration.  Thus, the problem boils down to whether someone should reuse the same salt.

If never reusing salt were infinitely practical, then the answer would always be no.  In this application, in order to not reuse salt, one must generate a separate intermediate code for every key they want created.  That takes time.  And the creation of the addresses themselves would take similar time.  So, fair to say that it's inconvenient.

Salt prevents precomputation attacks.  The main purpose of salt is to add a random element to the key derivation process and to prevent somebody from being able to precompute a large table that would accelerate the cracking of any passwords that fell into the set of passwords covered by the table.  With unique salt per key, they have to attack keys one at a time instead of the whole world of keys at a time.

Using the same salt and passphrase broadens the exposure such that the entire batch of keys can be cracked with the same effort, rather than just one key at a time.  A random element is still added, but it's random per intermediate code, rather than random per individual key.

In this application, that's not a useful acceleration to an attacker, considering an entire batch of keys already likely has the same password and can be cracked as a batch anyway, whether or not the salt was unique per key.  Crack one, you've cracked them all.  There is no reason why an attacker would want to go to the enormous effort of creating precomputation tables just to attack multiple keys belonging to a single user whose keys probably already have the same password.  This would only be worthwhile if the table were a tool that could crack anybody's password when encountered; random salt per intermediate code puts an end to that.

My conclusion is there's no real benefit to burdening each user with a complicated process for what is probably an illusory measure of protection.

[thanke]

Shouldn't reusing the intermediate_code be forbidden?

If intermediate_code is reused then the party generating the encrypted keys can conspire with someone who gets to see a lot of privkeys (some big exchange) and wait for one of its customer to reveal some privkey from one of these generated encrypted keys. Sooner or later this will happen. Then the conspirers can take over the whole series of coins based on the same intermediate_code. An issuer of physical coins should protect himself from such accusations by not accepting the same intermediate_code twice.

Thanks for asking.  Let me break this down into an intermediate code's component parts.

An intermediate code consists of salt, and an EC point based on the passphrase plus that salt.

Whether or not someone should reuse the same passphrase is their prerogative and outside the scope of the spec, so I'll eliminate that for consideration.  Thus, the problem boils down to whether someone should reuse the same salt.

If never reusing salt were infinitely practical, then the answer would always be no.  In this application, in order to not reuse salt, one must generate a separate intermediate code for every key they want created.  That takes time.  And the creation of the addresses themselves would take similar time.  So, fair to say that it's inconvenient.

Salt prevents precomputation attacks.  The main purpose of salt is to add a random element to the key derivation process and to prevent somebody from being able to precompute a large table that would accelerate the cracking of any passwords that fell into the set of passwords covered by the table.  With unique salt per key, they have to attack keys one at a time instead of the whole world of keys at a time.

Using the same salt and passphrase broadens the exposure such that the entire batch of keys can be cracked with the same effort, rather than just one key at a time.  A random element is still added, but it's random per intermediate code, rather than random per individual key.

In this application, that's not a useful acceleration to an attacker, considering an entire batch of keys already likely has the same password and can be cracked as a batch anyway, whether or not the salt was unique per key.  Crack one, you've cracked them all.  There is no reason why an attacker would want to go to the enormous effort of creating precomputation tables just to attack multiple keys belonging to a single user whose keys probably already have the same password.  This would only be worthwhile if the table were a tool that could crack anybody's password when encountered; random salt per intermediate code puts an end to that.

My conclusion is there's no real benefit to burdening each user with a complicated process for what is probably an illusory measure of protection.

That's not what I meant. Say I order a series of physical coins from you, all with the same intermediate_code. Then I redeem one of the privkeys at MtGox. After that I spent all other coins from the series. Then I can claim that it wasn't me who spent the others, but that instead you conspired with MtGox to do it. You, as the issuer of physical coins, want to prevent that my accusation is plausible.

[kjj]

The encoding is, in my opinion, an ugly hack.  Sadly, this is the logical end point of the cleverness that people have been using to contort the base58 package.

Please stop the madness.  If you want part of the text to be human readable, do it outside of base58.  If you want "6" to mean "incomplete" and "P" to mean "encrypted", please do those comparisons in ASCII.  Leave base58 to the binary parts that aren't important to people.

If necessary, extend the base58check system so that it can include non-encoded parts in the checked part.

[casascius]

I suppose that makes sense.  If your secret is x and mine is y and I come to learn xy (mod N), it's not out of the question that I could calculate x.  (Is that possible?  I think it is, if one can calculate the multiplicative inverse of y modulo N and then multiply xy by it)

That right there might be a reason to strongly recommend that intermediate codes should only be used once (owing not to the properties of the salt, but the reuse of an elliptic curve factor) and to convert the intermediate code generator so that it creates a batch of codes, one per line.

In such an arrangement, the user would be able to detect the reuse of intermediate codes with either the private keys or the confirmation codes, because both would expose identical ownersalt if they came from the same intermediate code.

I suppose that makes sense.  If your secret is x and mine is y and I come to learn xy (mod N), it's not out of the question that I could calculate x.  (Is that possible?  I think it is, if one can calculate the multiplicative inverse of y modulo N and then multiply xy by it)

That right there might be a reason to strongly recommend that intermediate codes should only be used once (owing not to the properties of the salt, but the reuse of an elliptic curve factor) and to convert the intermediate code generator so that it creates a batch of codes, one per line.

In such an arrangement, the user would be able to detect the reuse of intermediate codes with either the private keys or the confirmation codes, because both would expose identical ownersalt if they came from the same intermediate code.

[casascius]

The encoding is, in my opinion, an ugly hack.  Sadly, this is the logical end point of the cleverness that people have been using to contort the base58 package.

Please stop the madness.  If you want part of the text to be human readable, do it outside of base58.  If you want "6" to mean "incomplete" and "P" to mean "encrypted", please do those comparisons in ASCII.  Leave base58 to the binary parts that aren't important to people.

If necessary, extend the base58check system so that it can include non-encoded parts in the checked part.

If we extend the base58 check system, we should extend it to something that uses a different means of checksum more like Reed-Solomon coding, that allows for useful and reliable correction, not just detection, of errors... and then apply it to the whole Bitcoin ecosystem, along with some methodical thought as to what the human user should see.

I totally agree with the concern and eliminating the madness, I just don't think that fixing it for BIP 38 alone will really de-uglify it.

[casascius]

I suppose that makes sense.  If your secret is x and mine is y and I come to learn xy (mod N), it's not out of the question that I could calculate x.  (Is that possible?  I think it is, if one can calculate the multiplicative inverse of y modulo N and then multiply xy by it)

That right there might be a reason to strongly recommend that intermediate codes should only be used once (owing not to the properties of the salt, but the reuse of an elliptic curve factor) and to convert the intermediate code generator so that it creates a batch of codes, one per line.

In such an arrangement, the user would be able to detect the reuse of intermediate codes with either the private keys or the confirmation codes, because both would expose identical ownersalt if they came from the same intermediate code.

Just as a followup: I have been doing some thinking about this.

I think I have come to the conclusion that a brand new intermediate code per address is necessary if requesting 2-factor generation from somebody else, but that it's still OK for someone to use one intermediate code to quickly generate a large batch of addresses for themselves.

Exploiting the weakness I think we're discussing can only be carried out by someone who knows the intermediate code.  Having only an encrypted key and its corresponding plaintext private key, without the intermediate code or the ability to derive it again, one would not be able to decrypt any other encrypted private keys based on that same intermediate code, nor would they know either of the two factors that went into producing the plaintext private key.  They would not even be able to decrypt seedb/factorb because they can't derive the key to the AES encryption protecting it.

The intermediate code can't be reconstituted without the passphrase (or the scrypt derivation of it) - anything in a position to intercept enough information to recreate the intermediate code would effectively have access to the passphrase or the result of deriving it, an attack for which there will never be a defense.

So unless I am persuaded otherwise, I will definitely modify my intermediate code generator to offer to create intermediate codes in a batched sized per user's choice, but will leave intact the functionality of quickly creating a batch of passphrase-protected private keys based on a single intermediate code.  That generator's implementation creates a single intermediate code, generates a batch of keys with it, and then discards it without ever letting the user see it.

[thanke]

I think I have come to the conclusion that a brand new intermediate code per address is necessary if requesting 2-factor generation from somebody else, but that it's still OK for someone to use one intermediate code to quickly generate a large batch of addresses for themselves.

What exactly do you gain by re-using the intermediate code? I understand what you gain by re-using passphrase. But if you batch generate why not just iterate ownersalt?

[casascius]

I think I have come to the conclusion that a brand new intermediate code per address is necessary if requesting 2-factor generation from somebody else, but that it's still OK for someone to use one intermediate code to quickly generate a large batch of addresses for themselves.

What exactly do you gain by re-using the intermediate code? I understand what you gain by re-using passphrase. But if you batch generate why not just iterate ownersalt?

The computation time in having to re-do the scrypt with the different salt, which is significant by design.  If a javascript bitaddress.org generated a bunch of printable bills, it would be prohibitively slow to redo scrypt per bill.

[casascius]

Lately I have been working on an iPhone app to implement a BIP 38 tool for the end user.  This is to support a service where anyone with an iPhone can order two-factor paper wallets from somebody else, and then validate/decrypt them upon receipt, all while sharing their passphrase with nobody but their beloved phone.

The iPhone app does two things:

1 - You enter your passphrase, it generates intermediate code(s), and prepares them into a new e-mail in the Mail app to send them off.

2 - Once you have a passphrase-protected paper wallet, you merely scan the QR code and it decrypts it and shows the plaintext private key on screen.  This is useful for at least two things: 1) getting an unencrypted private key for use in places that don't understand encrypted private keys, and 2) quickly confirming that paper wallets printed for you by somebody else are really encumbered by your passphrase.

I have all of this working other than a few things:

1 - QR code scanning (shouldn't be too long since there's open source code for this)
2 - artwork and metadata so it's suitable for the App Store

I am using Xamarin / MonoTouch to build this, both for my preference to use C#, as well as I'm reusing classes from my Bitcoin Address Utility to do all the heavy lifting, and I'm using the C# version of BouncyCastle for crypto.  When it's ready to go, I plan to GPLv3 release the source code on github and publish it myself in the App Store.  This app doesn't mention Bitcoin and isn't useful for sending money, so I'm not anticipating any challenges getting it approved.

[Nyhm]

Exciting work, casascius/Mike. This will certainly drive other innovations, as well.

[Hawkix]

bitaddress.org can decode it, works offline.

[casascius]

I made one in C# that worked under Xamarin and believe I put it on github...I realize that's a barrier given that Xamarin is expensive payware.

It scans QR and decrypts.  Also generates intermediate codes from passphrase and lets you email them to someone.

[casascius]

Oh, so if you publish it, you have to pay fees to xamarin?

It should be possible (easy?) to have a java page adapted from bitcoinaddress.com embeded in a little app for iPhone, no?

If i take your source, I can sign it and use it on iPhone, or do I have to install something from xamarin before beeing abble to use it?

Something runing in terminal with only copy past bip0038 key or acquire QRcode and tipping passphrase should be nice, don't you think so? We should just be sure it cannot call iPhone's internet connection for security and erase results from app sandboxe.

Wondering now if entering private keys on iPhone is a so good idea from security point of view  

I think you have to pay for the Xamarin dev in order to compile for your own phone.  Last I played with it, the free version only compiles for the iOS emulator.

Javascript BIP38 is going to perform very poorly on a phone, if at all.  The Xamarin compiled version is slow but still plenty usable (3-10 seconds to do operations)

I believe if you're using an iPhone model for which there is no jailbreak yet, your attack surface is small.  My app makes no attempt to save your passphrase to the file system.  Just to be safe, keep it off the internet until your private key is totally redeemed.

[Valle]

BIP38 encryption/decryption takes about 40 seconds on Galaxy Nexus (bouncycastle implementation + multithreading). You can try it - https://play.google.com/store/apps/details?id=ru.valle.btc&hl=en