Self-descriptive strengthened keying: a standard for deriving keys from seeds

[Pieter Wuille]

(this is a proposal based on a discussion with gmaxwell and etotheipi, and inspired by a proposed extension to the Casascius mini private key format)

1. Abstract

There is currently a lot of talk about deriving keys or wallets from a relatively short seed in a deterministic way ("brainwallets"). As your wallet's keys are exposed to the whole world, it is essential to make sure it is hard to mount a brute-force attack against potentially easy-to-guess seeds (in particular when the seeds are user-chosen passwords). This is a proposal for a standard for doing this derivation, which has some nice properties.

2. Introduction

Typically, key strengthening is used to increase the time necessary for trying a single seed. This does however require either fixing the number of iterations (which should increase over time as hardware gets faster), or forcing the user to remember the number of iterations. It also lacks a way to verify a seed was correct, as every seed results in a valid key.

An alternative is using a checksumming system. For example, requiring that SHA256("BLAH" + seed) starts with a given number of zero bits, and using SHA256(seed) as key. With N required zero bits, this also slows down testing of seeds by 2^N per valid seed. It does provide a way to verify a seed was correct, is very fast to do the actual derivation, but also introduces some variation in the seed generation.

Neither solution however addresses the fact that it requires the derivation count or checksum strength to be known in advance (either as part of the specification, or by making the user remember). However, by combining both strengthening and checksumming, we can have seeds that encode their own strength, without compromising security.

3. Proposed algorithm

This is the proposed derivation algorithm:

• Calculate H(H(H(...(seed)...))), with 257 iterations, and H = HMAC-SHA512.
• If the 257th iteration results in a hash that starts with 8 zero bits, the 256th iteration hash is the output (the key).
• If not, keep doing iterations
• If the 513th iteration results in a hash that starts with 9 zero bits, the 512th iteration hash is the output.
• If the 1025th iterations results in a hash that starts with 10 zero bits, the 1024th iteration hash is the output.
• ...

This results in a variable-strength keying that requires 2¹⁶, 2¹⁸, 2²⁰, ... iterations of H per valid seed (both for a legitimate user creating a new seed, and an attacker trying to attack them). However, an attacker who does not know which strength the user chose, cannot give up quickly after a limited number of iterations. In what follows, we will however assume an attacker does now, so the security of this scheme does not depend on that property.

What this does essentially, is split the generation difficulty equally over making it take 2^N steps to generate a key, and at the same time, making only 1 in 2^N seed valid. This has some nice properties:

• Generating a key of a given strength S, requires 2^16+2*S iterations on average
• An attacker that has an oracle which can iterate all valid seeds of a given strength in constant time, still needs as many elements as there are in the original seed space to test all valid keys.

Note that HMAC-SHA512 does take a salt as input. This salt can be an application-defined default (such as the fixed string "Bitcoin key derivation"), but the application can also prompt the user for some extra random but non-secret bits (such as an email address, a birthdate, ...). There have been threads above such a salt alone, if I recall correctly.

4. Improvements

The potential difficulties (number of iterations necessary to a generate a valid seed) offered by the scheme described above are relatively far apart: a factor 4. We can however tweak the algorithm a bit.

Instead of checking for a particular number of zero bits at the start of a hash, we can interpret the hash as a number, and compare it directly to some predefined constant. This is similar to how the proof-of-work check happens in Bitcoin itself. Assume we want the difficulties to start at 2¹⁶ still, but have them be a factor 2 instead of a factor 4 apart, we can use this algorithm:

• Calculate H(H(H(...(seed)...))), with 257 iterations, and H = HMAC-SHA512.
• If the 257th iteration results in a hash whose first 32 bits are below 0x101000, the 256th iteration hash is the output (the key).
• If not, keep doing iterations
• If the 363th iteration results in a hash whose first 32 bits are below 0xB60183, the 362th iteration hash is the output.
• If the 513th iteration results in a hash whose first 32 bits are below 0x80C1A2, the 512th iteration hash is the output.
• If the 726th iteration results in a hash whose first 32 bits are below 0x5B2143, the 725th iteration hash is the output.
• ...

(more constants and mathematical model to obtain them can be found here; the numbers are found by a numerical approximation).

This results in difficulties very close to 2¹⁶, 2¹⁷, 2¹⁸, ...

Another potential improvement is using a different H function, such as something based on scrypt.

5. Implementation

An example implementation in Javascript can be found here. It does use a modified set of constants, which result in difficulties around 2¹⁰, 2¹¹, 2¹², ... instead, as difficulties around 2¹⁶ are already unusably slow (though possible) in Javascript.

[Mike Hearn]

I would definitely think about a function like scrypt here.

Despite this algorithm, I'm still missing / failing to understand what stops you calculating rainbow tables for common passwords given sufficient CPU time (it only has to be done once). Is the only defence against this telling users "choose a strong password or die"? What happens if technology improves and over time, functions that seemed strong become weaker (as happened with MD5/SHA for password hashing) - it results in money being stolen.

[Pieter Wuille]

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.

[JoelKatz]

Despite this algorithm, I'm still missing / failing to understand what stops you calculating rainbow tables for common passwords given sufficient CPU time (it only has to be done once). Is the only defence against this telling users "choose a strong password or die"? What happens if technology improves and over time, functions that seemed strong become weaker (as happened with MD5/SHA for password hashing) - it results in money being stolen.

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.

[etotheipi]

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. 

[DeathAndTaxes]

I would definitely think about a function like scrypt here.

Despite this algorithm, I'm still missing / failing to understand what stops you calculating rainbow tables for common passwords given sufficient CPU time (it only has to be done once). Is the only defence against this telling users "choose a strong password or die"? What happens if technology improves and over time, functions that seemed strong become weaker (as happened with MD5/SHA for password hashing) - it results in money being stolen.

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.

[DeathAndTaxes]

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.

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.

[gmaxwell]

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:

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.

[Mike Hearn]

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.

[Gavin Andresen]

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

Users tend to create passwords that are easy to guess, while system assigned passwords tend to be hard to remember. Passphrases, space-delimited sets of natural language words, have been suggested as both secure and usable for decades. In a 1,476-participant online study, we explored the usability of 3- and 4-word system-assigned passphrases in comparison to system-assigned passwords composed of 5 to 6 random characters, and 8-character system assigned pronounceable passwords. Contrary to expectations, system-assigned passphrases performed similarly to system-assigned passwords of similar entropy across the usability metrics we examined. Passphrases and passwords were forgotten at similar rates, led to similar levels of user difficulty and annoyance, and were both written down by a majority of participants. However, passphrases took significantly longer for participants to enter, and appear to require error-correction to counteract entry mistakes. Passphrase usability did not seem to increase when we shrunk the dictionary from which words were chosen, reduced the number of words in a passphrase, or allowed users to change the order of words

[JompinDox]

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

[etotheipi]

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

Users tend to create passwords that are easy to guess, while system assigned passwords tend to be hard to remember. Passphrases, space-delimited sets of natural language words, have been suggested as both secure and usable for decades. In a 1,476-participant online study, we explored the usability of 3- and 4-word system-assigned passphrases in comparison to system-assigned passwords composed of 5 to 6 random characters, and 8-character system assigned pronounceable passwords. Contrary to expectations, system-assigned passphrases performed similarly to system-assigned passwords of similar entropy across the usability metrics we examined. Passphrases and passwords were forgotten at similar rates, led to similar levels of user difficulty and annoyance, and were both written down by a majority of participants. However, passphrases took significantly longer for participants to enter, and appear to require error-correction to counteract entry mistakes. Passphrase usability did not seem to increase when we shrunk the dictionary from which words were chosen, reduced the number of words in a passphrase, or allowed users to change the order of words

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

[gmaxwell]

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

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

[Mike Hearn]

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

[pointbiz]

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?

[flatfly]

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?

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?

[DeathAndTaxes]

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?

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.

[etotheipi]

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?

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.

[chrisrico]

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.

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

[silversurfer1958]

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