Topic: BIP 38 Discussion Thread - Passphrase-Protected Private Key Format (Read 8767 times)

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 (or don't write) results from app sandboxe.

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

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

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.

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.

bitaddress.org can decode it, works offline.

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

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.

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.

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?

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.

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.

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.

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.

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.

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.

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.

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.

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]

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.


I see the point now, thanks.

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 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.

Recommended reading: Practical Cryptography, Ferguson & Schneier


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 don't know why we use double-hash.


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.

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.

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?

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

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

What is the security flaw?

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.

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.

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.

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


How would proof be given?

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 ...

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

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. 

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.

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.


^^ Damn good password.

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.

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.

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?

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.