New blog post: Hiding Bitcoins in Your Brain

[justusranvier]

Yeah but scrypt isn't a very good fit for an FPGA since it is memory-intensive...

That's true today based on current RAM prices. Will that still be true 10 or 20 years from now? What happens if somebody relies on that assumption to store their life savings?

The problem of protecting web site passwords and the problem of protecting financial assets do not share the same threat model.

[1714011519]

1714011519

[1714011519]

1714011519

[1714011519]

1714011519

[1714011519]

1714011519

[1714011519]

1714011519

[mpfrank]

This is the essence of what I intend to propose as a standard brainwallet replacement for sha256:

First, I propose scrypt as the key derivation algorithm.

Second, I propose the following standardized method for creating salt: a user should enter their own birthdate and their postal code that was current at the time their brainwallet was created.  The postal code should be stripped only to alphanumeric characters (no spaces or dashes).  These should be provided as salt to the scrypt algorithm in the form YYYY-MM-DD-x where x is the stripped postal code.  The purpose of these is that it's unlikely the user will forget these (even if they move) while still providing satisfactory entropy to substantially prevent parallel cracking of the entire brainwallet universe.  If all brainwallet generators and decrypters follow the same method for generating salt, users won't be burdened with having to remember how they created their salt, nor how they formatted their information.

Third, I propose the scrypt parameters 16384,8,8 as a starting point.  I propose that brainwallet creators offer a checkable option called "additional security" that will result in using sensible power-of-two multiples of these parameters instead (which multiples to use are the implementer's choice, but should be appropriate for the current state-of-the-art in potential cracking threats).  For example, 32768,8,8, 32768,16,8 are logical next steps when more difficulty is needed.

Brainwallet decrypters should consider the possibility that a user may have enabled "additional security".  After trying the default parameters, a decrypter should be prepared to bruteforce 8 to 16 of the most likely possible alternates, looking for something that results in a private key with funds.  This should happen if and when a user fails to decrypt a brainwallet having funds, or indicates that they have enabled "additional security".  The user does not have to remember specifically whether or not they enabled it - the worst case for a user is that they don't remember, and are forced to wait a while for the brute forcing process to either find their correct private key, which will succeed regardless of whether they enabled it, or fail, if they have entered the wrong passphrase.

Thanks, that sounds like a good improvement.  Upgrading sites and software to support a new key-generation standard will take time...  In the meantime, I've edited my blog post to quote your and Gavin's suggestions regarding added (unique or quasi-unique per-user) salt data.

[mpfrank]

As far as randomness of passphrase, Electrum generates a pretty random phrase.  I don't see that those should be very crackable, and I don't beleve in the idea of including personal information in my passwords either, despite Gavin's recommendation.

Yeah, the Electrum phrases certainly appear to have substantial entropy, but on the other hand, they would also take substantial effort to memorize.  I think this is always going to be somewhat of a fundamental trade-off...  If it's harder to brute-force, it's also going to be harder to get it to reliably stick in your brain...  And if you can't recall it reliably, it kind of ruins the point of having a brain wallet in the first place.  

EDIT:  It might be feasible to remember a string of words with a large amount (e.g. 256 bits) of entropy by turning it into a short story.  I wrote a short Facebook note about this:  https://www.facebook.com/notes/michael-frank/memorizing-ultra-secure-passphrases-via-short-stories/10151445953063552

[Etlase2]

Why the focus on brain wallets? Deterministic wallets, imo, make much more sense. There would have to be a standardized system though, or people would have to remember which one they used to create it. But ask for some personal details to add lots of entropy against any unknown brute-force attacker, then ask for 3-5 names of people significant to your past but extremely difficult to guess or research (first kiss type questions), then ask for a 4-word passphrase from randomly selected words from a dictionary, or perhaps from a generated list, and then make them type it a dozen times. Hash it up and use it as a seed. Should get at least 100 bits against an unknown brute force attacker, and perhaps 80 or 90 against someone who knows you and is trying to get your money. That should be good enough for your average user for at least a decade.

[herzmeister]

a user should enter their own birthdate and their postal code that was current at the time their brainwallet was created.

Isn't birthdate and postal code alone insufficient because they merely add a well-known and limited set of of data to potential dictionary attacks, especially if this way of setting up brainwallets is somewhat standardized?

[Mike Hearn]

I don't intend on ever merging "derive key from human selected passphrase" code into bitcoinj, at least, because given the current state of the art I think it will inevitably lead to people losing their money.

But this does not apply to neat ways to memorize real keys. The human mind is capable of amazing feats when fed data in the correct form. If somebody came to me with a PGP words style transformation that

a) Was secure

and

b) Had real usability studies done on it showing long term recall was possible

then I would probably be enthusiastic about that. The musical note game that came up a while back was the kind of research I have in mind.

Until somebody proves it's possible for normal people to memorize 256-bit numbers, our time is better spent on finding ways for people to easily back up their deterministic wallets and feel confident while doing so.

[justusranvier]

Good minimal scrypt parameters ( as of today )
are : 1048576, 11, 11.
This trinity will give you good safety margin
 for couple of years )

This is why password strengthening algorithms are not sufficient for a brain wallet. They are designed to be "good enough" for a few years because they assume you can make the user change his password in the future when it's time to increase the number of rounds.

Brain wallets must potentially remain uncrackable for the rest of the user's life.

There is no substitute for passphrases of sufficient entropy. Telling users, especially unsophisticated users, that their funds are safe with anything less is negligent.

Sufficient entropy might not be 256 bits, maybe 168 would be enough, but whatever that number is there is no safe alternative to using it that's going to hold up over time.

[cbeast]

Good minimal scrypt parameters ( as of today )
are : 1048576, 11, 11.
This trinity will give you good safety margin
 for couple of years )

This is why password strengthening algorithms are not sufficient for a brain wallet. They are designed to be "good enough" for a few years because they assume you can make the user change his password in the future when it's time to increase the number of rounds.

Brain wallets must potentially remain uncrackable for the rest of the user's life.

There is no substitute for passphrases of sufficient entropy. Telling users, especially unsophisticated users, that their funds are safe with anything less is negligent.

Sufficient entropy might not be 256 bits, maybe 168 would be enough, but whatever that number is there is no safe alternative to using it that's going to hold up over time.

Agreed. Unsophisticated users should not use brain wallets at all. I do think that password strengthening algorithms are sufficient if they are used with multiple passes and are sophisticated.

[casascius]

I think onerous scrypt parameters are totally reasonable here.

Who cares if it takes 600+ seconds or more of 100% CPU on a highly tuned scrypt implementation to run?  That should allow for a lifetime of improvement without being too inconvenient.  Opening a brain wallet is akin to smashing a piggy bank.

[UncleBobs]

Good minimal scrypt parameters ( as of today )
are : 1048576, 11, 11.
This trinity will give you good safety margin
 for couple of years )

Sufficient entropy might not be 256 bits, maybe 168 would be enough, but whatever that number is there is no safe alternative to using it that's going to hold up over time.

Can someone please tell me:

a) how to calculate entropy - is there a simple formula for it?

b) what is the entropy of Electrum's 12 random words?  Estimated time to crack?

c) is entropy decreased by personal information such as email or government ID's ?

 

[justusranvier]

I'd never heard of PGP words until now, and although I like the idea, I don't see that they are more random than the 12 words Electrum spits out.

The words themselves are not random, they are chosen a way to transform a large random number into a form that can be expressed verbally with a minimal chance of ambiguity. That would make them easier to memorize.

[CIYAM]

I agree with the use of scrypt (which I use in my offline key generation) and many of the other good suggestions.

Creating a secure "brainwallet" is actually very difficult (as Gavin has pointed out).

The "memory key" idea I have created (http://ciyam.org/memory_key.html) is another way to help - but of course if you want to create something "impossible" to brute force you need to be "creative" and you need to "work at it" (it can take quite a while to come up with something good enough).

I am willing to "test" publicly what *I* can come up with but of course I don't think that the same approach would necessarily work for others.

The problem of creating "secure" passwords has become "the problem" of our time as the "brute force power' has become so strong that a "new approach" is very much needed (if we are ever going to be able to get the "mums and dads" little own "grandmas and grandpas" using it successfully).

[UncleBobs]

I'd never heard of PGP words until now, and although I like the idea, I don't see that they are more random than the 12 words Electrum spits out.

The words themselves are not random, they are chosen a way to transform a large random number into a form that can be expressed verbally with a minimal chance of ambiguity. That would make them easier to memorize.

Well, as I understand it, even a number generated by a RNG is not truly random.

Without digging into the Electrum source, does anyone know what process is used to generate its passphrases?

My best reference on difficulty at this point is this cartoon ( ! )

 https://xkcd.com/936/

which claims 4 words would take 550 years at 1000 guesses per second.

[dancupid]

The brain wallet I use was created by printing out a random paper wallet and using the private key from that plus a memorable pass phrase to create a new address/private key.
I then gave copies of this paper wallet to people I trust to keep in a safe place. This paper wallet address contains no bitcoins.

Should someone steal the paper wallet they would be unlikely to be able to reconstruct the brain wallet key (or even know it had anything to do with a brainwallet), and it also allows me to maintain safe semi-backups with people I trust (or even don't trust).

Though not a pure brain wallet as such, I will always know how to reconstruct the private key when necessary.

[justusranvier]

My best reference on difficulty at this point is this cartoon ( ! )

 https://xkcd.com/936/

which claims 4 words would take 550 years at 1000 guesses per second.

If the ratio of ~11 bits per word is correct you'd need 23 words to achieve 256 bits of entropy.

Basically it means we need to stop thinking in terms of passwords, and even passphrases, and instead think about pass-short stories.

[UncleBobs]

My best reference on difficulty at this point is this cartoon ( ! )

 https://xkcd.com/936/

which claims 4 words would take 550 years at 1000 guesses per second.

If the ratio of ~11 bits per word is correct you'd need 23 words to achieve 256 bits of entropy.

Basically it means we need to stop thinking in terms of passwords, and even passphrases, and instead think about pass-short stories.

Thanks.  OK, that does cause me some concern. 

[justusranvier]

Here's another method for converting large numbers into memorizable form:

http://en.wikipedia.org/wiki/Mnemonic_major_system

[Elwar]

I memorize each letter and number and associate it with something I can remember.

taking a few numbers from my private address: 8Sp57A

that subset I remember that when I was 8 years old I broke my arm, the 'S' I think about Superman, the 'p' stands for taking a piss, 57 for 57 Chevy that my dad rebuilt, the A is for Al's restaurant on Happy Days...

just a simple way of remembering it all no problem

[UncleBobs]

Thanks for the great links CIYAM and Ukigo 

Here are my tests so far:

- 12 words similar to Electrum:

dumb gattaca simp argonaut redact finger elephant duplex orinoco fan depilate roster Entropy: 463.98 bits

- Individual 4 words, like xkcd:

dumb gattaca simp argonaut Entropy: 138.37 bits
redact finger elephant duplex Entropy: 161.77 bits
orinoco fan depilate roster Entropy: 143.69 bits

- CIYAM situation/event password

R00L20A01E06Y01D07R04F11Z18  Entropy: 153.16 bits

[Rygon]

More power to everyone who is willing to have their ability to memorize potentially be a critical point of failure in retrieving their bitcoins. But what happens if you just forget it? I could never seriously recommend to anyone to store their savings in an account for more than a few months with only a memorized password, especially one that needs to be sufficiently long. Bank accounts, retirement accounts, etc, can still be recovered if you forget your password. Bitcoin is extremely secure, but also extremely unforgiving.