hardening brain-wallets with a useful blind proof of work

[TheButterZone]

https://www.grc.com/haystack.htm

[flatfly]

People who haven't worked on password cracking [...] Today the tools are significantly better and have been refined through the disclosure of hundreds of millions of unencrypted passwords and the same kind of statistical tools that power speech recognition and automatic human language transaction. This statistical intelligence gets backed up by the brute force of GPU and FPGA clusters that can try hundreds of million or even billions of attempts per second.

Do you know is there some convenient package, or existing cracking tool that works in reverse - you give it your password, and it tells you how long it would've take it to find it using its heuristics, common words, l33tification, number and symbol combination rules?

That might be a good demonstration for would be brain-walleters.  The other problem is even thats misleading because its not specific to them if you took someones online posts, handles, street address, publicly listed stats from social media sites a lot of the apparent entropy is going to evaporate also.  Need to augment the cracker with that info first.

Adam

There's a number of those, and none of them will give you a perfect estimate, but a pretty good one is zxcvbn:

demo and information:
 https://dl.dropboxusercontent.com/u/209/zxcvbn/test/index.html

[virtualmaster]

Hi Adam.
Interesting ideas about brain-wallets.
Some other thoughts and viewpoints about them.

Availability and ASIC resistance of the pass-phrase stretching.
Scrypt is very scalable and has a good ASIC resistance but is not so available especially as web implementation.
So if I would implement scrypt as password stretching before the key-pairs are generated would be a good hardening.
However if my website goes down some users which have memorized only the pass-phrase and have put coins on addresses generated with scrypt would have difficulties to generate it again.
Hardening with PBKDF2 wouldn't be at all ASIC resistant but has a high availability. He knows he created 10 000 rounds PBKDF2 then if the site is not available he can search a simple PBKDF2 rounder on the web and do it the take any brain-wallet which can create the key-pairs.
But what about bcrypt ? I think it is the best compromise. Bcrypt stretching has a good ASIC resistance but a better availability then scrypt.
With creating the pas-phrase rounds on a server I don't think it is a good idea. Even if the connection is secure may be the server isn't.
Better to wait 1 min if creating the key-pairs on a smartphone then wait only 10 s but the pass-phrase being stored.

.............
How to pay with a brain-wallet a lawyer if you are innocently arrested by an oppressive regime, paying step by step(not all the content of your brain-wallet) ?
It must be generated a key-pair chain.
But how to do it without a computer ?
MIND HASHING is the solution.
A new(stil not working) concept what I was thinking about.

MindHash(passphrase+1) ->GeneratedPassphrase1
MindHash(passphrase+2) ->GeneratedPassphrase2
...
MindHash(passphrase+n) ->GeneratedPassphrasen

On each meeting the innocent prisoner could pay a certain amount of bitcoin, namecoin or whatever to his lawyer. We suppose that his lawyer knows how to use brain-wallets.

The problem is only that such a function still doesn't exist. (with the fulfillment of requirement that from 1 or more GeneratedPassphrases you cannot find out another GeneratedPassphrase)
Is it possible to create such a hashing function what you could calculate in your mind and is not breakable with a computer ? Eventually some highly available objects could be used.
Let us think about.
Starting points could be:
- some mnemonic systems
- something like Solitaire from Cryptonomicon,   , but here you need cards
- something like RC4, where you need pieces of paper

Let us give a name for solving this problem:
The innocent prisoner and his lawyer's - problem

[adam3us]

a limitation with key stretching is it incurs computational load on the client, which maybe a smart-phone or single desktop class machine.  eg 16384 scrypt iterations are suggested in BIP 038, chosen to be fast enough to tolerate in javascript.

So it would be desirable to have a secure server offloadable KDF, which means a kind of blindable deterministic proof-of-work.  

http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02948.html

Rivest et al in their time-lock puzzle paper is that it is easy to create work without doing the work during setup [...] avoid the javascript overhead issue that forces users to choose a weak iteration level.

eg create a 32-bit random salt, replace scrypt(i=16384, salt, pass) with scrypt(i=1,salt, pass) to be brute forced based on deleted salt.  Immediate 2^32 = 4billion iteration salt without any significant setup cost.

Here's another related idea, not for brain-wallets but for password encrypted random key wallets.  So above I described the symmetric time-lock approach (by deleting some of the salt to instantly create a brute force target).  

As a requirement what you would actually like is to be able to type your password, stretch it a little bit (to be not too slow on your not-that-fast single CPU system which could be an offline netbook wallet), send it to miners, have them do the bulk of the KDF work, and then either end up with an invalid transaction signature (if your password was mistyped) or a valid signature which they publish.

You would have to pay the miner something for this work eg 60c for 2^46 SHA256 iterations at whatever the bitcoin mining difficulty/reward cost is.  (Its perhaps better with GPU friendly Scrypt to not compete for bitcoin security as GPU capacity is mostly unrelated to bitcoin (ASIC) capacity.)

At first I was thinking this would be very hard to arrange, but if you make the address of form H2( H( salt, public-key ) ) and then delete the salt, then the miner can try to find the salt without having to trust the miner.  Until the salt is found the signature is of unkown validity because it is unclear whether or not it matches the public key or is a random forgery.  Once salt is known the signature is cheaply validatable by anyone.

The user tries to type their password (or an attacker with a copy of their disk tries to grind their password).  So they convert the password into a key and decrypt the encrypted wallet private key.  However we remove any checksums so all private keys are equally plausible.  The only way to verify the private key is to compute the public key and see if it is correct, however now this is an expensive operation to offload to an untrusted fast machine, or miners generally for a fee.

If the user guesses their password wrongly the miner will still collect a smaller fee (20c) for presenting a 45-bit collision with the address, whereas the full fee (40c) is available for a full match with the address.  (This is necessary because there may exist 45-bit collisions on the real address and the others cant tell without redoing the full 46-bit address search).  Note the work is at most 2^46 for the full match because it is a known solution, but could take longer for the 45-bit collision if there is no full match because the password is wrong.

The miner may have to do a committed transaction (if he is not mining his own blocks to put the transaction into) with the salt because otherwise the reward could be stolen.  Collecting the KDF fee is a bit insecure otherwise.

https://bitcointalk.org/index.php?topic=206303.15

In this way you get a stronger KDF than you have hardware for by paying a small KDF fee, with the benefit your password encrypted wallet becomes very expensive to grind.  (Bearing in mind that if someone has your hard drive, all keys are "brain-wallets").

Or you could offload the KDF work from an offline wallet (which maybe a cheap slow old netbook) to a beefy less well secured network connected GPU desktop.

Bitcoin script doesnt have scrypt as a primitive (could be a useful function to add), so the proof has to involve hashes.

You could probably do all of this with existing P2SH without any new features (except for the committed transaction).

Not completely elegant but somewhat interesting and maybe leads to some other ideas.

(To pay the KDF fees the user needs an unprotected or simple (different) password protected wallet with a smaller balance).  

Does not seem to be compatible with deterministic wallets at least as stated above.

Adam

[adam3us]

related idea, not for brain-wallets but for password encrypted random key wallets.  [...]
type your password [... decrypt your private key, make a signature and...] send it to miners, have them do the bulk of the KDF work, and then either end up with an invalid transaction signature (if your password was mistyped) or a valid signature which they publish.

[...] if you make the address of form H2( H( salt, public-key ) ) and then delete the salt, then the miner can try to find the salt without having to trust the miner.  [...] Once salt is known the signature is cheaply validatable by anyone.
[...]
The miner may have to do a committed transaction (if he is not mining his own blocks to put the transaction into) with the salt because otherwise the reward could be stolen.  Collecting the KDF fee is a bit insecure otherwise.

Here's a way to repair the security of the process of the miner claiming the fee for doing the KDF work.

Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as R = H2( (y=H(salt)), Q ),  S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).

User deletes y, Q and A and k-bits of salt.

User publishes extended address E and receives funds on it.  

When user wants to spend funds (or an attacker who has the users hard drive), he types his password and computes K'=Scrypt(password), and computes a candidate private key x'=AES-Dec(K',X).  The candidate (non-extended) public key is Q'=x'*G.  The user cant tell if this is the right password (right private key x' nor right public key Q') the work to brute force k-bits of salt is much more CPU power than he has.

User publishes (R, S, ECDSA(x',tx)); anyone can compute Q' from the signature, and see that the signature is valid, but it takes work to discover if R is derivable from Q'.  Thats the work the miner does as follows: the miner tries to find salt in the defined (advertised) search space such that either H2(H(salt'),Q') == R (because the password is correct) or if the password is wrong the miner finds salt'*Q' == R mod 2^k (ie last k bits match).  If the password is right the miner does not publish salt, only publishes H(salt') and signs with salt as private key to R in order to claim the full reward (40c+20c).  If the password is wrong (miner did not find full match within search space) miner signs with salt' but as H2(H(salt'),Q') != R he can only claim 20c.

Unlike before it is not possible for other miners to take the solution and assign the fee to themselves so the KDF miner does not need to be a bitcoin miner (to include his own fee collection into a block), nor does he have to use committed transactions for security.

Adam

[oakpacific]

related idea, not for brain-wallets but for password encrypted random key wallets.  [...]
type your password [... decrypt your private key, make a signature and...] send it to miners, have them do the bulk of the KDF work, and then either end up with an invalid transaction signature (if your password was mistyped) or a valid signature which they publish.

[...] if you make the address of form H2( H( salt, public-key ) ) and then delete the salt, then the miner can try to find the salt without having to trust the miner.  [...] Once salt is known the signature is cheaply validatable by anyone.
[...]
The miner may have to do a committed transaction (if he is not mining his own blocks to put the transaction into) with the salt because otherwise the reward could be stolen.  Collecting the KDF fee is a bit insecure otherwise.

Here's a way to repair the security of the process of the miner claiming the fee for doing the KDF work.

Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as Q' = H2( (y=H(salt)), Q ),  S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).

User deletes y, Q and A and k-bits of salt.

User publishes extended address E and receives funds on it.   

When user wants to spend funds (or an attacker who has the users hard drive), he types his password and computes K'=Scrypt(password), and computes a candidate private key x'=AES-Dec(K',X).  The candidate (non-extended) public key is Q'=x'*G.  The user cant tell if this is the right password (right private key x' nor right public key Q') the work to brute force k-bits of salt is much more CPU power than he has.

User publishes (R, S, ECDSA(x',tx)); anyone can compute Q' from the signature, and see that the signature is valid, but it takes work to discover if R is derivable from Q'.  Thats the work the miner does as follows: the miner tries to find salt in the defined (advertised) search space such that either H2(H(salt'),Q') == R (because the password is correct) or if the password is wrong the miner finds salt'*Q' == R mod 2^k (ie last k bits match).  If the password is right the miner does not publish salt, only publishes H(salt') and signs with salt as private key to R in order to claim the full reward (40c+20c).  If the password is wrong (miner did not find full match within search space) miner signs with salt' but as H2(H(salt'),Q') != R he can only claim 20c.

Unlike before it is not possible for other miners to take the solution and assign the fee to themselves so the KDF miner does not need to be a bitcoin miner (to include his own fee collection into a block), nor does he have to use committed transactions for security.

Adam

"Q' = H2( (y=H(salt)), Q )" should be R = H2( (y=H(salt)), Q ), right?

[adam3us]

"Q' = H2( (y=H(salt)), Q )" should be R = H2( (y=H(salt)), Q ), right?

Yes I'll edit it in place.  (Dangers of late relabeling!)

Adam

[oakpacific]

AES is bad (baked by NSA).
Please use another cipher (say, Serpent, Threefish or ...)

AES is not baked by NSA, NIST selected AES as their standard, NSA only approved it as fit for top secret information encryption, and they went as far saying all candiates are sufficiently strong to do the job.

We can be complete conspiracy freaks here, but SHA-256 underwent the same process.

[adam3us]

Here's a way to repair the security of the process of the miner claiming the fee for doing the KDF work.

Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as R = H2( (y=H(salt)), Q ),  S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).

User deletes y, Q and A and k-bits of salt.

One downside of this pattern of not knowing if your password is correct at the high-level is that if you misttype your password, you lose 20c each time.  If you are using the process to offload a 32-bit KDF from your cheap/slow offline wallet computer to your own fast online computer its not a huge deal, just try again as there would be no fees.

But if you are offloading a 46-bit key stretch online you could do with either a check character on disk (which makes 57/58 passwords offline grindable, so removes 6-bits from the password strength, or only a 40-bit key stretch for the CPU cost of a 46-bit one). 

Or better augment the users password with a check character so that the user is expected to remember.  Remembering a check char doesnt seem so unreasonable if you are trying to remember a 50+ bit password you can probably remember a single char that was machine generated appended to the end.  Computed in such a way as to catch transposed characters, missed chars as well as typos with probability 57/58.

Then for 60c per transaction in additional fees you can bump the security of a 50-bit password to 96-bits, with the knowledge that grinding is uneconomical even though your password unstretched is within grinding range.  I bet most people's wallets (whether offline or online), once an attacker has their disk so they become brain-wallet like, could be economically ground currently for amounts of $10k and above say. 

Basically I claim, everyone effectively has the brain-wallet "you're either kidding yourself how good your password is, or your password is so good you'll forget it", once you factor in an attacker getting a copy of the (random private key) encrypted deterministic wallet.

Adam

[oakpacific]

Here's a way to repair the security of the process of the miner claiming the fee for doing the KDF work.

Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as R = H2( (y=H(salt)), Q ),  S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).

User deletes y, Q and A and k-bits of salt.

One downside of this pattern of not knowing if your password is correct at the high-level is that if you misttype your password, you lose 20c each time.  If you are using the process to offload a 32-bit KDF from your cheap/slow offline wallet computer to your own fast online computer its not a huge deal, just try again as there would be no fees.

But if you are offloading a 46-bit key stretch online you could do with either a check character on disk (which makes 57/58 passwords offline grindable, so removes 6-bits from the password strength, or only a 40-bit key stretch for the CPU cost of a 46-bit one). 

Or better augment the users password with a check character so that the user is expected to remember.  Remembering a check char doesnt seem so unreasonable if you are trying to remember a 50+ bit password you can probably remember a single char that was machine generated appended to the end.  Computed in such a way as to catch transposed characters, missed chars as well as typos with probability 57/58.

Then for 60c per transaction in additional fees you can bump the security of a 50-bit password to 96-bits, with the knowledge that grinding is uneconomical even though your password unstretched is within grinding range.  I bet most people's wallets (whether offline or online), once an attacker has their disk so they become brain-wallet like, could be economically ground currently for amounts of $10k and above say. 

Basically I claim, everyone effectively has the brain-wallet "you're either kidding yourself how good your password is, or your password is so good you'll forget it", once you factor in an attacker getting a copy of the (random private key) encrypted deterministic wallet.

Adam

It's not a downside, it's a feature, or someone who has your disk can go at it repetitively to decrypt your private key.

[adam3us]

Here's a way to repair the security of the process of the miner claiming the fee for doing the KDF work.

Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as R = H2( (y=H(salt)), Q ),  S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).

As stated that is a single use password because once a miner has published y=H(salt), Q is revealed and someone in possession of the encrypted private key X=AES(K,x) where K=Scrypt(password) can grind by trying x' values to check if x'G =? Q.

To have a multiple address, reusable password the user needs to use BIP 32 private address derivation and store encrypted random chain codes so that Q_i=(x+c_i)*G is used in place of Q in the above protocol.  ie Q'_i=H2(y=H(salt),Q_i) and to delete c_i after it is spent.

Adam

[Domrada]

I only have a surface knowledge of this subject so I was hoping one of you could enlighten me. Brain wallets seem to me like a perfectly secure approach if they are long enough. The way I understand it, a pass phrase is composed of a series of Tokens, be it words, letters, alphanumeric characters, or other symbols. The Neighborhood for each token refers to the number of possibilities for each Token. If the Token is chosen randomly from a dictionary, the Neighborhood is the size of the dictionary. If the Token is a bit, the Neighborhood is 2. I think gmaxwell's point is that if the tokens are not chosen at random, the size of the Neighborhood is drastically reduced. That is, it may be possible, through sophisticated methods, to determine a token with a few guesses, based on context, if the token is chosen by a human. I grant this point. Here is where my understanding falls short: it seems to me the predictability of each Token only reduces the size of the Neighborhood. The possibility space is equal to

(size of Token Neighborhood) ^ (# of Tokens).

Since the exponent influences the space more than the base, it would seem to me that having enough Tokens is much more important than having a large Neighborhood. In theory, I could invent my own non-random phrase, composed of common english words with all lower case letters and good grammar, and as long as it is 128 words long, it should be at least as secure as your 128-bit randomly generated string. What am I missing? Thanks in advance...

[bloss]

Since the exponent influences the space more than the base, it would seem to me that having enough Tokens is much more important than having a large Neighborhood. In theory, I could invent my own non-random phrase, composed of common english words with all lower case letters and good grammar, and as long as it is 128 words long, it should be at least as secure as your 128-bit randomly generated string. What am I missing? Thanks in advance...

However, if the first x words of your non-random phrase exists in any book that happens to be in some rainbow table, then you have essentially converted that set of x tokens to 1 token.  I think this is why people advocate a completely random looking and high-entropy passphrase.

[kensilverman]

So I needed to think it through for myself:   In the original post on Brain Wallets "brain wallet providers do not use anything more than SHA1-256  because the user is stupid to have a  weak password."  Well, it is clear to me that the ability to crack a private key is directly proportional to not only the entropy but also the memory intensive recusriveness of the KDF.   and even before that, if you dont "trust" the wallet seed creator - you can use a prior  KDF just to create your entropy from the "weak" password to be sure.   So, for example, let's compare a strong ARGON or scrypt hash to SHA1-256 to create more entropy:

Apples to Apples:

Assume per N bits of entropy it takes one core with access to a reserve area of memory, 1 second to crack.    Now assume we are going to create a highly recursive KDF that cannot be broken down by parallel processes on the same check, but we'll allow a memory reserve area so large as to assume that all cores can have access to the same necessary memory at the same time - THAT actually is not likely in a memory intense KDF with so many cores, however, we will allow it for sake of argument:

So, assume an FPGA farm which generates in parallel, 1 billion entropy ==> seed checks per second.  The KDF in question takes some unit time T to compute:

Now, if the KDF is made to take 2T, then that same FPGA farm will take 2 seconds to check through the same entropy, thus we shave 1 bit off the entropy complexity necessary for a 1 second crack (becasue every bit of entropy doubles the entropy and therefore doubles the time to check - all else being equal).

So, a one second KDF changed to a 2 minute KDF per core,  allows one to shave off 7 bits of complexity.  Ok, that is not a lot, but is is something.  2 hours means 11 bits of complexity.  Nobody will wait 2 hours to generate a wallet to save just 11 bits of entropy.   For a 128 bit 12 word (bip39) wallet, that means shaving off only one or two words.

If however, you had a few GPUs in your own setup, --- well then so would everyone else,  so the game stays the same.  Cloud creation of key?  Then its a trust issue.  So , it seems then, there is no solution other than strong entropy.

Encryption of your high entropy 24 word key using ARGON2 or Scrypt-256 is another story.  You can encrypt with a reasonable password and nonce then save those keys online.  but why?  then yo have to write down the nonce adn the whole point of encryption is to have nothing to write down saving only a small weakish password in your head - so at least for now that seems not possible.  While they say aes-256 is not breakable - that assumes a strong nonce and key (more shit to write down).  If there is anything to write down then we are back in the same crap.  So???   Keep the hash algorithm secret?  More shit to write down or store or save somewhere.  Encrypt that?  strong nonce or key to write down.  Dam!

At the very best we can make it that the only way an attacked can succeed is a personal attack =- ie he KNOWS your addres has a lot of coins and he KNOWS your secret key is encrypted in YOUR email, not someone elses.

This gives rise to another method:  a large circle of potential email addresses, for which your encrypted key file is in only one of them.

So while a solution is possible,  and easy to guard against all but a personal attack,  it appears overall a strong entropy is still needed.   if Ive helped anyone think on this more: donations acptd here:  19baMnvNEo3aQwPo7kdmRNAAkr17bLGk3P