Topic: Self-descriptive strengthened keying: a standard for deriving keys from seeds (Read 6209 times)

Like someone said, electrum does it right.  Their passphrase generation
process uses computer generated entropy at a high enough level,
and also uses key-stretching to add 16 more bits of security for a total of 144.

I believe their implementation solves the issues.

No need to "roll your own" (always a bad idea in crypto). There is already a solution called Password Based Key Derivation Function (PBKDF2) which properly performs multiround hashing to increase the work required to hash a password.  However the larger problem is humans are simply horrible at selecting strong passwords.   Most passwords (even ones users believe are secure) have very little entropy.   When you have something secured by a single weak factor, it usually ends badly.

Brainwallets are a Great idea but the concerns are of course legitimate.
How many people are there in the world that might want to hide money, from Govt ( or an ex wife ) in their head.
The Market potential is huge.

Could Bitcoin have been made to utilise a slower Hash function like Bcrypt instead of Sha256
Could Bitcoin be altered to use something like Brcypt which would slow down brainwallet mining and presumably
make precompiled rainbow tables too inefficient.

A future cryptocurrency or Bitcoin update ought to cater for hardening Brainwallets against attacks.

What's wrong with (Sha256(Bcrypt(PassPhrase)))

With multi-signature transactions, there's no reason an output need be tied to just one user's brain wallet, yeah?

The only thing I don't like about rfc1751 is that short words are actually less memorable.  Not to mention a 2048 word dictionary is pretty small.  You can use a 65,536 word dictionary (16bit) if you include plurals and conjugations, which I think is fine -- even if the user forgets the exact conjugations, they will remember the base words, and will be able to recover their key with enough attempts.  8 words will get you a 128-bit key like this:

"inverse speaker ameliorate floated platypuses yearns conjugate nullified"

The user knows all the words in their key: and if they remember the acryonym "isaf pycn" it will help them recover all the words.   Theoretically, it would be possible to make this even easier if the app that was generating the key was willing to sacrifice a few bits of entropy for the purposes of finding sequences that have nice, memorable acronyms:  such as "mime type".  Then, even if the user can only remember 6 of the words, there's a limited amount of remaining entropy that they can cycle through with a program.

Of course, I still hate brainwallets: I don't like the idea of users taking their Bitcoins to their own grave when they get hit by a bus, but so many people are so passionate about it, it's tough to ignore.

Only 5 words is likely not viable.

12 words of a 1024 word list = 1024^12 = 2^120 (120 bits)
11 words of a 2048 word list = 2048^11 = 2^121 (121 bits)
10 words of a 4096 word list = 4096^10 = 2^120 (120 bits)
9 words of a 8196 word list = 8196^9 = 2^117 (117 bits)
8 words of a 32,768 word list = 32,768^8 = 2^120 (120 bits)
....
5 words of a 20,000,000 word list = 20,000,000 ^ 5 = 2^121 (121 bits)

The exponential is a powerful operator.  Dropping the word count greatly increases the size of the word list.

Yeah, I've been wondering the same!
How much bigger would that word list need to be?
And would it be as resilient to random guessing/bruteforce attacks?

Interesting thread. Nice to have all these great math minds on this topic.

Can I get your thoughts on doing SHA256(rfc1751)?

From a very brief glance at sipas demo looks like we want to ask people to remember 11 or 12 words. If that is the case can we make a standard with a bigger word list where people would only need to remember 5 words but still have 128 bits of entropy?

I suspect the popularity of brainwallets would go down if people knew how difficult they were to make secure. Perhaps somebody should set up a program that finds addresses based on weak passwords and then resends any such outputs back to the real owner. When the user sees transactions appear in the list they didn't create, hopefully their reaction will be to stop using brainwallets - before somebody else steals everything!

FYI, here are some statistics on password theft on Gmail, which represents a user population of around 400 million people.

Having one password for everything is fortunately not the majority case but still fairly common, the re-use rate being 10-15%. Many of these passwords are pretty reasonable - good mixes of letters, numbers and punctuation, lack of dictionary words, etc. Unfortunately having put the effort into creating a "good" password the natural human tendency is then to use it everywhere.

Around 1 to 1.5 million email/password pairs per day (where the email matches an existing Google account) leak out of compromised websites. Given these two numbers you can see that on any given day around 100-200,000 users become vulnerable to account hacking. These numbers are lower bounds, based on observed attempts to run spam campaigns on Gmail - the true number of exposed passwords that don't get used is likely higher.

Facebook claim they see around 500-600,000 accounts per day being compromised. Given that Facebook is larger than Gmail this doesn't sound unreasonable.

Many users have systematic problems keeping their accounts secure and have been compromised more than once. Or rather, would have been, if we had not blocked the attempts. A small number of users fight the system - after being compromised and forced to select a new password, they try to change back to the previous stolen password. Many of that subset take the view that the inconvenience of memorizing a new password is higher than the cost of having their account be hacked.

Given my practical experience with these matters I'm not intending to support brain wallets any time soon in my own software, including system created passwords. On the other hand, letting you back up a wallet by writing down a root private key makes a lot of sense (this is just the most extreme form of system-provided password of course)

I believe a more useful area of research would be how to encrypt private keys under biometrically derived keys. Another use of CP-ABE (beyond p2p investment funds) is to do this, for instance, a biometric measurements authority can - given a photo of your iris - issue a key that encodes your biometrics. These can then unlock your wallet root key, which could be backed up in a public place (like a DHT).

It's perfectly possible to do a 'recovery' with a purely user provided string. This is one thing SDSK addresses.

For the record:  I'm still against brain-wallets.  But there is such intense, passionate interest in them by so many users, that it's difficult to ignore.  I absolutely insist users always have a printed backup, but some people are absolutely intent on taking their own bitcoins to their grave (literally, in some cases).  Even though I use a different alphabet for Armory wallet seeds, someone figured it out and wrote a tool for converting any passphrase into a wallet-recovery string.  I can't do anything about that, except offer my disapproval.

So while I disapprove of the practice, at least this proposal by Peter, sets up a system whereby the popular clients will not accept brain-seeds unless they have this 1/2^N property:  which means the user is forced to add a certain amount of entropy (by searching random suffix strings) to their otherwise-crappy passphrase.  I think this goes a long way towards mitigating the issues we don't like about brainwallets.  It might be just enough convenience that users will do it (add entropy), but not inconvenient enough that they are motivated to evade the mechanism (such as modifying client source code).

Electrum does it right: computer-generated high-entropy brainwallets.

RE: seeds with a lot of entropy:

Every time I look at the academic literature on passwords/passphrases, I get more depressed about the feasibility of either giving users a secure passphrase that they will remember or getting a secure passphrase from them. I fear there will be a lot of lost coins if "brain wallets" get popular.

E.g. this 2012 paper: http://dl.acm.org/citation.cfm?doid=2335356.2335366

Yes, much though I love Stefans work on webcoin I think doing KDFs or even ECDSA in a browser is something of a non starter performance wise. I saw how slow the iPhone app is at creating new keys and signing transactions the other day, it was fairly ridiculous.

The point of these scheme is basically forces the input to not be some insecure user generated string, or at least imposes a computational tradeoff in order to make a more arbitrary scheme valid.  In theory, the seeds used for this would be secure with just a single SHA256 (because they have lots and lots of real entropy).

Since we can't be absolutely sure of that, it would be nicer to use more computational expense in the strengthening. Unfortunately there is a fine line: People seem to be hell bent on using KDFs implemented in python and javascript which are a thousand times slower than native ones.  This means that "adequate" KDF from the cpu perspective is intolerable from a JS generating tool.

If the self-descriptive strengthened keying is not weak enough to be fast in these usecases then it just won't be adopted and people will continue to use sha256(password) Javascript web generators.

This can be partially mitigated by using an algorithm which is difficult to optimize.  bcrypt attempts to achieve this.   IMHO SHA-256 is  the worst possible choice.  The user is likely generating the private key on a personal computer ill suited for a high number of rounds.  Mining has created a great incentive in improving the hashing efficiency (MH/$ and MH/W) such that the multiple between a major hashing farm and the user is already huge.   The rise of ASIC hardware will increase the potential resources of an attacker by another order of magnitude.

Given the user can wait for some significant but not unreasonably long period of time the use of something like bcrypt would seem to be preferable.   GPU acceleration of bcrypt is generally poor (although FPGA acceleration is not as adversely affected).  Scrypt attempts to hinder acceleration on both GPU and FPGAs.

TL/DR version.  The attacker will always have more hashing power than the user.  The goal is to keep the attackers throughput as low as possible (while still keeping the algorithm functional for end user).  This can be achieved by:

a) more rounds.  If the user only needs <1 private key per second then make it take a full second to generate.
b) salt.  prevents parallel and precomputation attacks.
c) algorithm optimization.   Use algorithm which is fast for user but not much faster (or optimally no faster) for the attacker.



Hypothetical numbers.  Using SHA-256 the user selects a strength which will take <1 second to generate.  That would be ~1 million iterations (assume implementation in code is roughly similar to throughput of CPU miners).

An attacker with a single GPU could attempt ~500 million to 1 billion passwords per second.
A major hashing farm (100 GH/s double bitcoin hashes) could attempt 200 billion passwords per second.
A 10TH/s (double bitcoin hashes) could attempt 10 trillion passwords per second.

Against that kind of brute force virtually all passphrase are going to fall.  The throughput of the attacker must be reduced.  We can use salt but if it is determined by user input it will have relatively low entropy.  We can use more rounds but the multiple of attackers throughput is so high that even having user wait 10 seconds per private key "only" keeps a major ASIC hashing farm at 1 trillion passwords per second.

An algorithm which prevents re-use of the massive optimization in bitcoin mining for attacking passphrase is essential.

While bcrypt can't protect painfully weak passwords the combination of deterministic salt derived from user responses and a passphrase requirement of at least 8 characters, and a large number of rounds can limit the attacker to an ineffective throughput (baring dedicated bcrypt processors) which makes brute force attacks infeasible or at least uneconomical.

Rainbow tables can be defeated if a derivitive of the salt is correctly introduced salt on each round.  It makes the output of the round dependent on round number.  

That being said I feel using a function specifically designed for multi-round hashing would be better (PBKDF2, bcrypt, scrypt).  It is far too easy to design a cryptographic systems which appear secure yet have hidden flaws.  Those kdf were specifically designed to hash passphrases over multiple rounds and prevent cryptographic attacks other than pure brute force.

As a client developer, I want to discourage "simple" seed generation.  A user can always go to the "Recover Paper Wallet" dialog, and plug in his own sequence of characters, which may be something like sha256("Bob"), assuming no one else would ever do the same thing.  You'd like to blame the user when his coins are stolen, but the application itself will get blamed for security issues, and the user is not likely to admit they used such a simple wallet key.  This is why I wanted to make it difficult for users to enter custom strings into the wallet-recovery dialog in Armory.

What this proposal does, is it allows me to pare down the space of valid keys to 1/2^N.  This is beneficial for not only key-strengthening, but forcing the user to add some entropy to their key.  If Armory will only accept keys that follow the pattern Peter described, then sha256("Bob") is not going to be accepted.   The user will be required to add N bits of real entropy to it to make it valid.   I'd almost be okay with a program that helps them do that.  Because while sha256("Bob") will be an easy key to break, sha256("Bob_g4982fX") is much better but still memorizable by a human.  So for users that want brain wallets, you're forcing them to accept extra entropy to their wallet key, while also slowing down someone who is trying to brute force it. 

This is a fundamental problem with any brainwallet algorithm. An attacker who has X times the computing power you have can try X possible passwords. If an attacker has a billion times the computing power you have, you need to make sure your passphrase isn't one of the first billion he would guess. This is, as far as I know, a fundamental limitation of a deterministic brainwallet algorithm that no known technique can avoid.

For starters, since it does not allow arbitrary seeds, it is hard (1 in 2^N/2) to come up with a password/passphrase to use as one. The intention is to still generate these seeds by a computer (just like Armory and Electrum do now), but use a dictionary to construct them, so they can easily be written down or remembered. As soon as the seed space is 2¹²⁸ large, attacking it becomes as hard as the ECDSA verification in Bitcoin itself.

Apart from that, there is the possibility to use a user-provided salt.