Topic: A Proposal for Brainwallets (v2) (Read 3269 times)

I gave this some thought last night-

(somewhat reiterating on what I already stated)

A very secure Brain Wallet would employ both a passphrase and a numerical exponent.  The user would need to remember both the phrase and the exponent.  This way they can choose the level of security.  If the exponent is a variable, then the number of keys required to compute would be enormous(not to mention the number of keys the hacker would need to track).  This would offer fairly good security for a mnemonic security token.

You could easily modify the java code supplied above to perform this.



-bm

Let's choose our words carefully and differentiate between brain wallets and human chosen passphrases.
For example, Electrum can be used as a brain wallet but you cannot choose an arbitrary seed.

To me, the main problem with brain wallets is the $5 wrench, which is why I
advocate stealth quick-transfer mechanisms to other wallets.

btw Greg, if you're into JTR I'd be interested to know how quickly it would arrive at my example.

Lets say for demonstration purposes that we already know it's Shakespeare.  Even that alone would be a massive computation.

-bm

Certainly interesting but even in my example you are very far combinatorially from what you might call *easily computable*.  Remember first they have to guess the basic passphrase, then run through each and every numbering schema, and even manage to arrive at the % special character usage.  So lets say there are a few billion base passphrases that the cracker wants to cover, lets say a million numbering schema, another million special character schema, and lets say a thousand capitalization schema.

that would be:

BILLION X MILLION X MILLION X THOUSAND = very large number of private keys to compute

Back to OP, so if you increase the computation required for each one of these possibilities(as you suggest), you are miles away from crackability.  You might be able to enhance the security a bit by using a non-standard hashing algo(back to the commodification problem).  You could even have a custom definable hashing exponent, this would make the keys even more difficult to enumerate ie. you pick how many times the brain wallet system hashes your basic passphrase.

It is true that a fully randomized private key is the best security by far.  If you have a large Bitcoin balance a brain wallet is simply not recommended.

-bm

E.g. JTR rules mode is a publicly available example... though there are more powerful tools which are non-public.

An example of JTR rules on the single input word "hello world", with the minimal default rules— there are thousands of extra rules that can be enabled, and but even the default set produces a great many examples.


6hello World6
Olleh world0
World0 HELLO
Helling 8world
olleh worlD
helling dlroW
5hello dlroW
world. Olleh
HelloHello worlded
Hello0 world
5world 3hello
Dlrow Hello0
hello worlds
world7 Hello5
Hello3 World9
3hello 3world
hellohello World6
hello6 world5
Hello1 World4
Olleh world6
hello? world.
3hello world3
olleH Worlds
Hello3 7world
Hello9 world
5hello 8world
9hello world.
3hello World3
hellos dlroW
Hello9 world9
WorldWorld Hello8
olleH 3world
olleh world?
Hello5 world6
Olleh 8world
Helloed 6world
1hello World8
helloolleh world1
Hello7 worlD
Olleh World.
Hello6 1world
Hello4 World0
hellohello 1world
Hello5 wrld


Turning on some more rules:


Hello66666 Yworld
Hello07 world1111
HELLO9 world58
HelloR world1914
Hellov world15
dr.hello Qieks
Hello10 world1997
hello45 Wor1d
fqjju world1965
4hellos world1938
hellol world42
hello2012 world40
Hello222222 World14
Hello85 WORLD1
hellof World51
Hll WORLD7
Hello04 World66
Hello999999 2world
Worldy
Hello44444 world1923
Hello78 'world'
HelloC r[y'g
hello2009 World\
hello71 ld
%hello% Wor1d
Hello55 worlding
hello} World97

which cracking software are you referring to?

Is _already_ modeled by existing cracking software: They already try thousands of schemes like adding characters before and after the words in input phrases.

You are taking a bet that the cracker's parametrization of likely modifications won't include yours— but the community of attackers spends in total more than your _lifetime_ in time thinking about this problem every couple of years, and they have access to stolen password databases to test their theory against the behavior of great many people.  You might get lucky and choose a scheme they don't think of or that they consider too unlikely to search— or you might not, but as a user you are likely to do the likely thing, and not likely to know better.

You're right it's not a good idea to use plain text from literature(my original base text is Shakespeare).  Someone had their brainwallet cracked who used 'one small step for man one great leap for mankind'.  So yes you should use something that is personally memorable but not universally identifiable.  The technique I suggested though makes it virtually impossible to crack with any known NL processing technique, and fairly easy to remember.

Plain text Shakespeare is absolutely not a good idea.

-bm

There are attackers that are already precisely searching patterns like this.  Every sentence in every book in your local library (much less just the memorable ones) is only about 32 bits of entropy. Scheme selection is 8 bits. The prefix template of decimal digits (assuming uniform probability, which you probably won't get with a human selecting them) is at most 26 more bits.  This is not an impressively secure scheme, though you've just convinced yourself that it is.

This is why you should not be using anything like this, the human capacity for self deception is too great.

you're absolutely correct.

beefing up the hash function will make it considerably more difficult to enumerate passphrases and crack the brain wallet.  It is possible to make a mnemonic passphrase that is nearly impossible to crack in this scenario - just don't use simple and plain NL text.

ex. it's best to think up some method to include numbers in the passphrase, so take some memorable english text

"The common curse of mankind, - folly and ignorance" , and find some way to include numbers that is easy to remember

"1The 2common 3curse 4of 5mankind, - 6folly 7and 8ignorance"  and maybe an additional way to include special characters

"1The% 2common% 3curse% 4of% 5mankind%, - 6folly% 7and% 8ignorance%"

and you have a brainwallet with fairly good security.

-bm




-bm

Brain wallets are somewhat advanced topic but there are many user friendly wallets.  See Electrum.

Go easy on me because I haven't understood 95% of this thread  

But, I do know that if BitCoin and it's offspring are ever going to go
mainstream for the average Joe non-technical user ( me ) the wallet security issue
has to be resolved one way or another without requiring the owner to
engage in numerous incomprehensible steps to guarantee 'security' ..

I do know that a functional wallet must

1) Not reside on the owner's local computer ( hard drive crashes/keyloggers/viruses )
2) Be a 'hot' wallet for easy 'coin' transactions, both 'send' and 'receive'
3) Be suitable for 'cold' storeage
4) Feature one 'click' download and self install
5) Capable of handling multiple 'coins'
 
You folks are the experts and understand the ways various security features can be defeated ..
But .. The whole process needs to be orders of magnitude 'dumbed' down for mass utility ..
It's got to have the perceived utility and security? of the typical online brokerage account ..

In my limited ( less than 2 years ) exposure to cryptocurrency, the
NXT wallet is the closest to what i think is needed and I'm sure that
it has several security issue flaws ( though I have no idea what they may be )
that would make it a less than 'perfect' solution ..

Thanks for listening ..

Triff ..  

I agree it would be unethical to promote this method and I do not doubt
many have screwed themselves.  so if anyone is reading this I am
merely discussing the possibilities, not endorsing human chosen
randomness.

at the same time, it kind of seems like an insult to human creativity
to suggest we can't come up with unique phrases.  

something like "budwhacker beaver and Tim jones had a conversation with
captain despond about the lollipop mugshankery and the BOX of why everythinggg
vinyl 4017"

It can even rhyme if you want it to:

"frick-frack newfangled clamshack tishnyiak the fishman cried
my poor lady in red died bee-cause bell made me yell for
my poor grandma maybelle SLIDER mc-chachagagaya ooo 355"

While you can't measure it, seems hard to believe that either
of those phrases has less than 128 bits of entropy, especially
the latter because of its length.

Lol, that was silly.

The problem jonald is determining the level of entropy.  Also humans are very good at convincing themselves they are random when they aren't.  A common homework experiment of entropy is to ask 100 people to pick a random number between 1 and 10.  Usually 30%+ will pick "7" and significantly less than the expected 10% will pick either 1 or 10.   Picking 1 in the range 1 to 10 doesn't seem random to most people so at a subconcious level, most will reject it from even being a candidate.

It isn't impossible for a human to generate a passphrase with sufficient entropy however the three major problems remain:
a) Most will fail at the process, and when they fail they will have funds stolen so any method which encourages that is unethical.

b) It is very difficult to quantitatively state how much entropy your human chosen passphrase actually has.  So you pick a passphrase and your funds aren't stolen yet.  Is it because the passphrase is secure and it will never be stolen or is it just because a hacker hasn't gotten to it yet and they will steal it in the future.

c) The sheer number of inputs necessary to have a high confidence that there is sufficient entropy is high enough that a significant number of users will lose access to their funds.   Another way to look at it is if you need to memorize 25 words you chose to have the same security as 6 random words is there any benefit to advocating the former?


Then use diceware and random words (or some similar system). Using diceware and truly random selections (i.e. roll some dice), 10 simple words gets you >128 bits of entropy.  This is very similar to the concept that electrum uses for the seed words.  The seed is random    

You probably can be very secure using less random words combined with key stretching.  Key stretching is very effective when used with truly random values with lower (but still useful) levels of entropy.   For example 5 diceware words is only 64 bits of entropy*. If your key is the hash of the diceware words [ key=H(set of diceware words) and your attacker can make 1 trillion hashes per second well the 50% solution time is ~100 years.   Still that may be close too close to comfort and that work requirement can be increased by key stretching.  For something like a cold storage wallet you don't need sub millisecond access; so use a KDF timed to take a little over a second to complete.  Even in unoptimized javascript that should mean tens of thousands of iterations.  Lets say 10,000.  Now the attacker can't attempt 1 trillion passwords per second.  With the same hardware they can still complete 1 trillion hashes per second but each password attempt takes 10,000 hashes so their throughput has dropped to a mere 100 million passwords per second and correspondingly the 50% solution time has been increased to one million years.

It is important to understand that key stretching can't "fix" passwords with very poor entropy.  For example if your password is on a list of 1 million known compromised passwords then the attacker would find it in a fraction of a second (assuming it isn't precomputed).  Using key stretching is still ineffective as using this hypothetical machine above even with key hardening the attacker can attack 100 million hardened passwords per second.  So the solution time is increased by 10,000x however it is increased from microseconds to a fraction of a second.


If you wrote down a large list and then randomly selected from it then it would be random.  Of course by randomly selecting I don't mean the equivalent of "pick a number from 1 to 10" as we already know the results will not be random.  You could number the words on the list and then roll dice to pick the words.  Of course you would want a large library of words.  Larger library means less words selected for the same entropy.  You would also want to avoid words which may be confused for other words or are hard to remember.  You would also want to make sure your numbers system has a uniform distribution (each word has an equal chance of being picked). You would also need to safely store multiple copies of this system and it would be a good idea for it to be widely adopted.  This means it would be both peer reviewed and there is an increased chance you can find the word list in the future. Of course if you spent countless hours doing all that ... well you just reinvented diceware.  It has been around since 1996 and is rather robust.  Maybe someday I need to make a brainwallet site using diceware so people can stop losing coins.

http://world.std.com/~reinhold/diceware.html

* D&T warning.  You can only use a reduced entropy password if you are sure the level of key stretching.  For open source software you can inspect the code and preferably any system would make this clear and visible to the end user.  Opaque websites (i.e. your login for BCT) are a different story.  You have no idea how much key stretching (if any) the site is doing.  Thus you should always assume that no key stretching is being performed.  Although the topic is about brain wallets I don't want someone using 5 (or less) diceware words for their exchange account and when they get hacked saying D&T said it was secure.  Honestly since websites are so bad at security I would recommend using diceware as a master password for a tool like lastpass and generating a random 20 digit password for each website.

I do agree, its better to use computer generated randomness.

But, I'm still not convinced it can't be done.

If I wanted to use elements from my day yesterday -- say the name (which I can't even spell
correctly) of the lady at the Chinese take out place... or, a word from an episode title
that I watched with my wife... or the raw name of an AVI file that I burned, etc, or
the current time, ...maybe those methods are predictable but there is still entropy.

I can also devise a "predictable" but still effective ordering method.
(the method can be predictable, but doesn't mean the results can be
predicted)
 
if go with 100 as a lower bound of words people commonly choose, and
if I choose 25 random things, now you're talking 100^25, that's 160 bits of entropy.

Also, where do you draw the line between human-chosen and random?
If I write down random words to form a candidate word list, is it still
random, or does it have to be completely off the top of my head
without the help of rudimentary tools such as pen and paper?

Generally, it is probably best not encourage this kind of thing,
as the risks outweigh the rewards.  I just wanted to make the point
that it is not impossible if one is careful and understands the dynamics
and the numbers.

My answer to forgetting passwords is steganography.   Hide the backup on your own machine
in an image, mp3, or series of carriers if you really want to be paranoid.

When it comes to difficulty of memorizing something, I think people
are forgetting that the human brain remembers what it considers
to be important.  If I place a high importance of remembering my
bitcoin password, (and if I rehearse it), then I'm sure i could
retain a very long password for a very long time.  

I think the average person can easily remember a 12 word passphrase
if they have a substantial amount of money in it.

You absolutely can. First: whats hackable to _you_ is not whats hackable to some guy with powerful statistical analysis and a fpga cracking farm who, with one unit of effort, simultaneously attacks all users. Secondly, what I was more expressing was an OR case,  that frequently you secrets are either crackable OR they are likely to be lost.  Both of those possible outcomes result in you losing your funds.

A challenge there is that it may be quite hard to get users to understand that your collection of personal information there isn't to send it off to some server or put it someplace public... in querying around I got the impression that lots of people would put random things in those fields, defeating the protection.  It would probably be better than what people are actually doing.

There is another weird consequence is that you lose denyablity when using such a scheme. E.g. if someone does obtain your secrets then your address is effectively a cryptographic commitment to that personal info, it's harder to say "those transactions weren't mine". Thats a little bit into the realm of movie plot threats, but at least some of the people working on encrypted wallets have insisted on "denyability" as a feature, and people have used it as selling point for "brainwallets" (and also as an argument against writing down the key, which is probably the most prudent think you should do— considering the forgetting risk).

Which is it? Are the secrets hackable, or are they unrecoverable? You can't have it both ways.

IMO, wallets that use memorized seeds should do something like this instead:
- Ask the user for some impossible-to-forget information such as their full name to use as salt.
- Generate random words to use as a passphrase. The number of words can be user-configurable, but 5 or 6 should be OK on fast computers.
- Depending on the number of words, apply enough key stretching to make attacks infeasible.

Then you only have to memorize ~6 words instead of a full ~12-word seed mnemonic, which is a lot easier. And there's still no risk of users choosing bad passphrases, since the wallet does it for them.

(The rough passphrase utility I made a while ago works a bit like this, though it doesn't generate passphrases.)

A lot of people have screwed themselves badly this way— you are not a unique and special snowflake, the ways and manipluation people will come up with when they are trying to be "random" is fairly predictable, and that the same properties which make keys easy to remember make them more predictable. Studies of have shown people picking _more_ predictable passwords when explicitly instructed to be unpredictable. Modern password cracking is a statistical study of psychology, powered by "big data" analysis on information culled from huge leaked plaintext password databases and sources like twitter and the forums.

Using a fancy technique may really only be adding a few extra bits of entropy, and worse it's very hard for you to reason about how much entropy you have and an attacker with more powerful statistical tools than your intuition may find your key with only moderate effort.  For this reason it is far better to use a random technique (e.g. dice or a computer CSPRNG) and just add a couple bits directly, then there is no ambiguity.

(Though this is all without regarding the very real risk of forgetting— almost no one is prepared to deal with cryptographic secrets which _cannot_ be recovered if lost, and most people drastically overestimate the strength of their memory)

Whenever a website turns up having a security breach and we find it was using unsalted passwords everyone cries out claiming that the operators are incompetent fools (perhaps even criminally so) and yet thats exactly what a human generated "brainwallet" is— an unsalted hashed password, but worse: they're publicly visible to everyone so someone doesn't even have to compromise a system before they start cracking.