Topic: Brain wallet, can it be secure and is the entropy argument always valid? (Read 3029 times)

Why have you posted this? Is it a challenge? And why necro an ancient thread, in newbie land to boot?

Instead I'll add some useful information for newbies ...

DO NOT USE A BRAINWALLET - IT IS NOT A SAFE WAY TO STORE YOUR BITCOIN

Of course this oversimplifies, but unless you understand exactly how the concept of entropy applies to key selection (and brainwallets in particular), then you've only yourself to blame when somebody steals your coins.

And yeah, electrum may well be secure, but its not what's being talked about here.

Electrum uses a 128 bit random seed, that can be saved as a sequence of 12 English words.
The seed is generated by the computer, not by the user.
A 128 bits seed is very secure: in order to crack, one would require as many iterations as for a 256-bit ecdsa public key.

18YXnSUCPDVNEpPGDFRVrdVye63RpH2MA4 is another but both were used and emptied out in a short period of time.  Why would anyone *ever* use such an address?  Perhaps they realized their vulnerability and corrected the situation but this second one isn't just a quick in and out.

https://blockchain.info/address/1B3PHXB6g5YGLvzTkxrrPEdLbpvfEoC5Qi is an example of a brain wallet with a poor passphrase.

I like brainwallets, because eventually some idiots will use a stupidly simple key.

Coder create a script that grinds names and english words together + 0-9 then inserts keys into a bitcoind worker instance to be validated. You have another script to automatically empty the wallet to your cold storage addy / torwallet periodically.
Depending on the amount of idiots (lots) and bitcoin uptake it can be more profitable than mining.

I figure the same will be eventually true for privkey, but current efforts have yielded nothing.

I personally have not done this but I see a lot of people gearing up for it if brainwallets keep gaining popularity.

BTW:
The code only demonstrates the transaction generation and verification, not how to duplicate a Bitcoin address with a key-pair.
I have no idea how to do that.

Hi enmaku.

See my reply to my own Newbie post, subject: Offline generated transactions, how is a transaction signature verified?

That should address your concern.

The full public key is used to access the private key encrypted transaction hash (scriptSig), which is then verified against a locally computed transaction hash.
The address (hashed public key) is used only from the previous transaction (source coins) as a first test.
HOWEVER, both the public key and the signature are provided in the transaction, so that does not result in any security if two public keys hash to the same Bitcoin address.

So to spend the Bitcoins for such a "collision", you have to have a private key / public key pair (or set) for which the hash of the public key must be the same as another party's Bitcoin address.  Then you can create a transaction to take the coins.

If you would like a copy of the modified BTCurious "offlineTransaction" JavaScript code that demonstrates all this, let me know in a reply post or message.

Regards.

My understanding of the protocol is that any private key whose corresponding public key hashes to a given address may spend the coins at that address. There is a potential collision attack here since the address is only 160 bits while the keys themselves are somewhat longer - there are possibly many keys which correspond to a given address. If someone who knows the gritty details can tell me whether the complete pubkey is actually checked or just the address I'd appreciate it, but my understanding is that only the address is checked. Unfortunately it's computationally unfeasible to generate two keypairs with the same address for testing purposes

Thanks enmaku.

I do like that strategy too.  It is not a true brain wallet since there are the dogtags.  Their content could easily be encrypted and stored in the cloud if necessary.  Not too risky.  Having a JavaScript program stored in the cloud does not help guessing a passphrase, password and pin.
It is clever.

Thanks for the entropy analysis.  It is consistent with what I have found.  I will save your comments.

I don't understand the RIPEMD160 issue completely.  To spend Bitcoins, one has to be able to correctly produce a signature in the scriptSig of the transaction.
The scriptSig contains a private key hash of the transactions and the public key.
I don't fully understand how signature verification works yet.  You seem to be indicating that there is a weaker link in the process because of RIPEMD160.
To spend Bitcoins you need a private/public key pair where the public key hashes/maps to the address of an account "holding" Bitcoins.  Right?
This way, you can create a scriptSig that will pass verification (however that is done).  This is not as strong as the private key because of the hash.  I may have just answered my question.

Is there a good resource I can use to understand this?

Thanks.

Thanks Ukigo.

 I understand the security in not sharing a method for a "brain wallet".
I would be interested in knowing yours, but that would not be in your best interest.  It is difficult to advance my understanding this way, but I can't blame you.
I understand that for my own best safety, I should not share anything like this.  I can always keep my own private method.

The purpose of sharing this is to have a method that anyone/everyone can use with realistic security.  Though this makes the strategy public, if the method generates unique enough keys for each user, it does not compromise the security of the result, any more than making AES public compromises its security.  The goal is to increase the possible solution pool to an all but impossible size, even though the seeds are not necessarily very complicated.  This is what cryptography is really all about.

Any suggestions you would care to share would be greatly appreciated.

You're basically correct in your summary of the entropy argument. Assuming you're using a published method for generating your private key from your passphrase (sha256 is particularly popular) then the question boils down to "how hard is it to guess your passphrase."

Here's the basic math: A Bitcoin private key is 256 bits, but realistically we're not interested in finding your exact private key, merely finding some private key for which the RIPEMD160 hash of the public key matches your address - yes, it is possible for more than one private key to map to the same address... This means that in order for us to not lose any entropy, any passphrase or key we select should contain at least 160 bits of entropy itself. If we're talking about natural English text such as you'd find from a book or poem, each word only represents about 1.5 bits of entropy. log2(1.5^274) results in 160.280... bits of entropy so we'd need a whopping 274 words of natural English text to make a suitable passphrase.

Now on the other hand, if we choose the xkcd method and build our passphrase using completely random words from a set of the 4,096 most common words then each word represents a whopping 12 bits and our privkey can be constructed with 14 words since log2(4096^14)=168.

Still, if you have a memory like I do, 14 random words is still a bit much, so I've come up with another method. I had two identical sets of dog tags printed up. Each dog tag can hold something like 15 characters per line, but I only used about 10. Each line is numbered 0-9 (I used two tags) and each line contains 8 characters of random Base32 text. Base32 was chosen because it is case-insensitive and most dog tag embossers can only do uppercase letters. Each line of text represents log2(32^8)=40 bits of entropy, so any 4 lines combined creates exactly the 160 bits needed for a private key. I memorize a PIN and my dog tags do the rest. My memorized PIN is useless without the physical artifact that is always on my person (a backup copy of which is in a safe place) and the artifact is useless without the memorized PIN. Better still, multiple PINs means multiple accounts, so I don't have to re-memorize a huge amount of data. Sure, if someone stole my tags and knew how to use them it wouldn't be hard to generate all 10,000 possible private keys and sweep away all funds in every account, but I'm still safeguarded against everything but a physical theft perpetrated by someone who knows EXACTLY what they're after. If I need more security than that, I'll generate a one-time true-random paper wallet and store it in a fire safe or something.

So in conclusion, if you don't have an absolutely stellar memory you're going to need a paper backup - if you can memorize it, chances are it doesn't contain enough entropy.

BTW, shameless plug I know, but I did write a Bitcoin Address Tool for Android. It's 100% compatible with Casascius' Bitcoin Address Utility, generates QR codes for both the privkey and address, stores no data, is open source and when combined with airplane mode makes brain wallets on-the-go somewhat easier.  

I have been working with Bitcoin transactions for a little while.  I have modified the JavaScript for bitaddress.org for a brain wallet.
bitaddress.org provides a client side JavaScript page that can be easily run on an offline machine, either Windows or Linux, which is nice.
The code looks well written and was easy to modify.  The code will recognize a passphrase for a private key.  Doing this directly, I agree, is not very secure.  I added the ability to enter a password and a PIN.  The password is modified by bit reversing each character and then cyclically XOR-ing it with the passphrase (a very old and simple type of cipher).  This results in an unintelligible passphrase.  The PIN defines the number of times to apply the 256 hash to the XOR-ed result to produce the private key.  So the brain wallet gets bigger, having three things to remember, the long passphrase, the reasonable password and the 4 digit PIN, but these would not normally be related to each other and would make guessing at an easy to remember passphrase to try to steal Bitcoins pointless. Keeping the private key secure requires the same precautions as usual.  The public key Bitcoin address generated with the private key is all that is needed to start receiving Bitcoins.  The purpose being to use this as a savings account or hidden stash for Bitcoins; never used in a wallet.  The passphrase should contain personal information like birth dates, maiden names, etc. instead of just text from a book or poem.  The whole point of this is to be able to easily regenerate your private key.  The Javascript can be hidden anywhere out in the cloud.  It is not secret, it just needs to be available should the private key need to be regenerated (to spend the Bitcoins).

Any comments addressing the strength of such an approach would be greatly appreciated. 

I looked into the entropy argument, and while not understanding informational entropy completely, the measurement/computation of such entropy does not appear to be very straight forward except for relatively simple cases.  The bottom line appears to be the ability of someone to either guess your private key (for a truly random key, unlikely), or to guess at the input to the generation of your private key (this case) so they also can generate your private key.  These modifications make that guess significantly harder if not also impractical.

I don't know how to make the modified source code available on this forum at this time, but I am willing to share it.

The second part of this is BTCurious' offlineTransaction JavaScript code.  This generates an offline transaction (no wallet required).  I will post about this in a separate post. (I need 5 as a newbie)

The third part is submitting the transaction to the Bitcoin network.

Thanks for your comments.