Bitcoin Forum

The risk with brain-wallets (eg BIP 038 with no EC multiply, or even with EC multiply if the manufacturer is not that trustworthy) where the ECSA private key is computed from password is that the passwords can be ground and if successful the funds can be stolen.  So clearly its desirable to use key-stretching for brain-wallets and  this is already done with Scrypt or PBKDF2.  However 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.  I described one such proof-of-work in this post (relating to blind-hashcash a different but in hind-sight related topic, where you in addition need a transferable publicly auditable proof of work):

An RSA based blindable (secure) work offload function:

So if we call that can be use as a blind deterministic password-based proof of work: we could set message = password, or H(password), blind by random factor g^b, and have the server compute blind-pbkdf( password ) for us with some large w that we cant afford to do on our smart-phone or laptop because itd be too slow.

The above work function is basically a blinded version of Rivest et al's time-lock puzzle (the time-lock puzzle desires non-parallelizabiiity as the idea is to intentionally encrypt something for the future, where you cant speed it up by using multiple cores.) 

The fact that it is non-parallelizable is actually a disadvantage for a blind KDF, it means the speed up is limited to the fastest single-core offload server.   Another simple parallelizable time-lock is proposed in the time-lock paper which is simply to symmetrically encrypt and discard say 40 of the key-bits (this is also the model used by Juels & Brainard for their client-puzzles proof of work which is somewhat hashcash-like but has no public auditability).  However that is not blindable as its not an algebraic form.

But it is easy to make an intentionally parallelizable instance by say 128 server cores (16x 8 core servers, or an even more impressive core count GPU server farm), use a smaller e value to take eg 10 minutes on a 1Ghz GPU core (whatever your transaction delay tolerance is), then stretch the password using eg PBKDF2 and 1 iterations, null salt, into 128-values worth of pseudo-random output call those m1..m128.  ie (m1||..||m128)=PBDF2(1,"",password).  Now create 128 cryptographically random (non-deterministic RNG) challenges b1...b128, the ECDSA key is x=m1^e+...+m128^e mod n, which is fast to compute when you know d (before deleting p, q, and d).  Each offload message is r_i = g^b_i*m1 mod n, and the respective unblind u_i=y^b_i mod n.  and the key is k = s1/u1+...+s128/u128 mod n.

Unfortunately the user does need to retain g, y & n (or publish them in a hard to censor location, and keep the hash c=H(g,y,n) as a public fingerprint, or embed that in their coin on the block chain, because if the user relied on the offload server to provide g,y,n the server could provide a g,n where g has a small sub-group, allowing the search-space of blinding factor to be greatly reduced.  The few remaining candidate password hashes could then be run through the KDF with the real n.

The user can even create a pre-signed message transferring ownership from key Q1=x1*G to new key Q2=x2*G, with bigger work parameters on x2, that it requests the server operator, or trusted party to release when the available compute farm sizes increase and compute becomes cheaper.  If locktime worked properly, you could even broadcast that transaction with a locktime 1 year into the future, and rely on the bitcoin network to automatically update your security margin over time.

So a user protecting a $10,000 brain-wallet bitcoin investment might say use $10 worth of GPU time (at amazon prices of $2.10 per 400core tesla GPU hour thats 100,000 fermi core seconds or 714 fermi card seconds.  According to the bitcoin wiki mining comparison an S2070 is 4 tesla cores, and does 750MH so say 187.5MH/tesla second is about 37-bits in entropy compared to PBKDF2 rounds.  If you have a 40-bit entropy password that takes you from at risk of being GPU brain-wallet mined ($80 worth of grinding) to implausibly uneconomical  border line not feasible with any resources for the mid-term.  Of course there are faster (AMD not Nvidia) and cheaper ways to grind than amazon.  Eg bitcoin mining pool payout probably charges a lot less.  Maybe it would be something for CPU & GPU miners to do as an alternative to vanity address mining or  primecoin/litecoin mining.


So in summary you in a javascript client, or puny cell processor can create an arbitrarily hard to undo KDF with no practical CPU cost at setup time.  You can offload it securely later to a server, and you are not relying on the server to be around - the information is public (on the blockchain) the "server" is replaceable and stateless, and could even be a bitcoin core feature (pay CPU/GPU miners and other users small fees to help you decrypt your brainwallet).  This is parallelizable so it should be easy to add 40-bits of key-stretching or more that would be really expensive even on a high end PC with top of the line graphics card, to do that from a smart phone.

Probably some more things that could be done eg combine with secret sharing so you can detect and eliminate defective work answers, or perhaps find a way to also have signed proof of work that somehow is easily verifiable without introducing a password verification crib.

Adam

Aside from the asymmetric blind proof of work, BIP 38 could be tweaked to avoid this issue.  (Though this approach is not securely sever offloadable).

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


Adam

Clarification: The "no EC multiply part" of  BIP 38 is not a brain wallet. In BIP 38 The stretched password is used for encrypting the private key. You need both the encrypted private key and the password to get to the private key... the encrypted private is not brain compatible.

Is there a BIP or standard for brain-wallets?  Would be interested to read...

Adam

No.

Practically everyone who knows about or cares about the BIP process loudly yells at people DO NOT USE BRAINWALLETS.  We've seen pretty concrete evidence that users are resistant to good advice in this space, and they are shocked when their favorite quotation is cracked and they lose their coins (But it was 60 characters long! I even added a special character! how is this possible?!),  the existing sites promoting this stuff won't use a KDF stronger than SHA256*1 because "users are stupid if they use weak passwords".


BIP∞: Brainwallets.

FOR GODS SAKE. DON'T DO IT.  YOU MAY THINK YOU ARE SMART ENOUGH. SO DID EVERYONE ELSE WHO GOT ROBBED. HUMANS ARE NOT A GOOD SOURCE OF ENTROPY.

YOU HAVE A SCHEME?  Pfft. THE SPACE OF ALL SCHEMES YOU'RE LIKELY TO HAVE PROBABLY ONLY HAS A FEW BITS OF ENTROPY. RANDOM PHRASE IN A BOOK? THERE ARE ONLY ABOUT 30 BITS OF SENTENCE SELECTION IN A LIBRARY.

OH NO. YOU ARE NOT LISTENING TO ME, ARE YOU?

OH CRAP. YOU THINK THAT "EIGHT CHARACTERS AND ONE FROM EACH CHARACTER CLASS" APPLIES HERE??  WEBSITE SECURITY MIGHT HAVE TO DEAL WITH 1000 ATTEMPTS PER SECOND, BUT SOME DUDE WITH A FPGA FARM IS PROBABLY PRECOMPUTING A BILLION BRAINWALLETS PER SECOND. JUST STOP.

NOOOOOOOOOOOO.

Well, now that you have no more Bitcoin I guess we don't have to worry about you using a brainwallet.

Cheers.


Of course, if by brainwallet you mean a key the user has memorized... it's not hard to memorize 128 bits mnemonic encoded. Though the risk of data loss is kinda sucky: People are really not all that used to data that cannot be recovered if lost.

It's not that difficult to memorize five random phrases, which will contain quite a bit of entropy(assuming the phrases are really selected reandomly) .

And whether it's secure to use really has to depend on how much money you will put in it, for pocket money it could be a viable alternative.

Except they stake-my-life-on-it will NOT be selected randomly if you allow any user to operate under that procedure. They will be selected "randomly" as in that same way that "DUCK SPATULA" is random: Not very.

If instead a cryptographically strong random number of, say, at least 128 bits is generated it can be directly converted into a secure mnemonic phrase with just 12 words (or fewer, if you want to deal with a bigger dictionary).  This is probably way smaller than your "five random phrases" but by being ruthlessly specific about HOW its generated and what "random" means, it's really just another way of representing a 128 bit key, and it's perfectly fine to memorize that.

If your construction involves the human picking the words or phrases, as it does 99 out of 100 times someone says "brainwallet" then the actual entropy is much lower. Humans are poor sources of randomness, and telling them to be "random" actually seems to make them worse at it. Powerful statistical models are quite good at predicting what humans will do, and while they won't break every single instance they can break a surprisingly large number.

People who haven't worked on password cracking have this quaint notion of running a little dictionary file through a program... and this would have been accurate in 1990 for someone cracking at your unix-crypt uni shell account.  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.

I'd rather not see cracking weak bitcoin brainwallets turn into a viable industry for people buying up no-longer-competative mining fpgas for pennies on the dollar.

No, the security it depends more on how much all attackers eveywhere in the world are spending on setting up ultrafast hardware for brainwallet cracking. This number is likely to become very big: "just pocket money" has a way of growing through lazyness and the sum of all pocket money is great in any case. This is especially the case because the attackers can attack everyone with the same effort it would take to attack one person.

Viable alternative to what? Done right it is just a cryptographically strong number, so it's not really an alternative in that case, it just "is" the other thing.

1) New bitcoin user decides to start off by purchasing a 4 or 5 figure sum of bitcoin (in USD terms).
2) User wants to be extra special careful, so they spend some time creating a brain wallet and move their funds there.
3) Weeks or months later, they start to worry about forgetting the key, so they import it into a desktop client.
4) They forget that a sizable fraction of their stash is held in a weak key since they never moved those funds to a new address.
5) Bitcoin appreciates an order of magnitude or two.
6) Brainwallet key is eventually cracked.

When computers can think like a human, only then will I be worried about losing my brainwallets. With all the human languages and symbols in existence, it's doubtful that all the hackers in the world working in consortium could break even one well crafted brainwallet. Though one not-so-well crafted wrench probably could.

Your brain is trained to memorize phrases, not random alphabet-number-symbol mix, it may indeed be the case that people can keep long series of english phrases in their memory longer than just some random strings, even if the length of the phrase series is much longer.


Brainwallet is mainly designed to solve the deniability problem, so that people who could seize you disks can not use it as a proof against you, so it's a viable alternative to make a paperwallet and bury it under a oak tree. But yes, maybe it's not an alternative for storing pocket money.

Who said anything about "random alphabet-number-symbol mix"? Alphabet-number-symbol mix is terrible cargo cult security and shouldn't be used. Go reread my posts. Good schemes for memorization use a mnemonic encoding that translates large integers to and from english text.

Though generally the properties that make phrases _easy_ to memorize are what actually produce the statistical properties that make them easy to predict (http://www.cs.utexas.edu/~shmat/shmat_ccs05pwd.pdf).  But predictability is resolved by using a lossless encoding process with known entropy rather than a human source.

(And memorization still has a rather severe forgetting problem. Like people overestimate their ability to be random, we also over estimate the integrity of our memory. The public has very little experience handling keys which cannot ever be recovered if lost.)

I actually have IRC logs about the creation of the phrase brainwallet and brainwallet.org.  It was created by someone who introduction to the subject matter was his own efforts to crack peoples insecure keys, and he was irritated that he only found a few coins. No kidding. Don't try to glorify history to people who watched it first hand.

It's possible to memorize keys without using an insecure generation scheme. Though if you think thats going to protect you from evidence of unlawful activity on your computer: (1) Perhaps you should engage in less unlawful activity. :)  (2) you're going to be rather disappointed when you realize how complete computer forensics is, hiding a key will probably be the least of your concerns. :)

Now since you were the one talking about the unreliability of common folks in generating dictionary passwords(like how can they not follow proper procedures), maybe you could also talk about how difficult it would be for people to use such mnemonic encodings?
Now don't speculate on my intentions as it's unproductive, to my best knowledge(and I suspect a lot of people) it was Jon Matonis who came up with the idea of brainwallet, and he made it clear in the Forbes article that deniability was his major concern. If you have some first-hand secret history, it would be way more helpful if you could please just share it.


Hmm...you do realize there are places in the world where doing completely legal things can get you arrested right?

 
Maybe, it would be interesting to see what FBI could do with Ross Ulbricht's bitcoins.

No, it was a person who goes by the name of "Joric", who also went and created the website. The discussion wasn't secret, it was all in #bitcoin on freenode in early 2011 IIRC.  The logs for the channel aren't public, but I can send them to you if you're curious.

Electrum users don't seem to mind.  Correctly written software should may it easy— and standards exist to help people make best practices sofware, I certainly don't expect people to go out and roll their own implementations. 

Or did you write your own copy of SHA256? :)

Lot of good they're currently doing him (or likely to do him ever— considering the charges). I'd really rather not participate in a discussion where someone with charges like this (http://www.popehat.com/wp-content/uploads/2013/10/MarylandUlbrichtDocket.pdf) is held up as exemplar, as it's too easy to go off on a insane tangent.

But thats the thing about security it exists in the context of many other things. Bitcoins that can't be taken from you only achieve their full value to a spherical-convict who can't be put in a jail cell. It also has to be weighed against the very real risk that you run a fever and forget the key. For every person whos coins are attempted to be seized there will be 100 others who just forget their keys. ::shrugs::

Well if they fail to recover the private key eg because i) its 128-bit random, weakly protected with 40-bit password but stashed physically somewhere they dont know about, or ii) its 128-bit random encrypted with > 80-bit password and they have the encrypted key on the disk, or iii) its a brain wallet encrypted with > 80-bit password theyre going to fail via forensics and grinding.

That forces them to negotiate with him which wont make them happy, but the US (in)justice system is all about negotiation and little about fair-trial justice, so they should be used to that.  (>95% of cases never get to court, but settled via plea.)  Of course they'll be pissed that they cant get around a technical barrier sitting under their noses, but mathematics dont bend to will.

The other very interesting question is whether they know the address.  Is the address obvious?  Does it literally have $80m on one address?  Or is it more like split up into 1000 sized deterministic wallet addresses (addresses indistinguishable from random without the password).

Maybe they have evidence from the addresses they do have of transfers to or from other addresses...  That seems rather likely unless some clever and meticulously error free wallet-control was used.

If the address where the $80m is stashed, or some of them are identifiable, they are effectively tainted as belonging to DPR / Ulbricht.

When he's finally free in 15yrs or whatever DPR maybe richer than Bill Gates, but with a lot of tainted coins.  Satoshi's coins are also tainted (not in a negative way but due to the linking bug).

If there are some associates of DPR with control of some of the coins and they start to move, the taint problem could start to lead to some awkward fall out, and reinforce the need for committed-transactions, and change some opinions about taint not being a problem.

The public support on the war on some drugs is mixed at best, and there could be a streisand effect and silk road tainted coins might be collectors items selling above par. 

ps about taint I think its a bitcoin defect: what you really want is to identify the wallet, but not the coins.  In this way you can demand the wallet holder hand over the keys, but not screw up the 1000s of downstream holders of bits of long-circulated 10th hand change tainted by it.


And finally back to the OP topic: blind KDF (which I think is a fantastic new idea:) whether you believe in brain wallets or not (and trust me I do not, I am paranoid and I dont want to forget a password, or I may get hit by a truck) everyone effectively actually HAS a brain wallet whether they realize it or not.  Once some seizes your computer (legally or via physical theft), your 128-bit random coin encrypted with 40-bit entropy password IS a brain-wallet in the hands of the government or other criminal group that has it.  Or if you store it on an online computer that gets malware that steals wallets.

So even if your password is self-chosen (bad idea, as Greg says) or computer generated encoded in some mnemonic form, if its got a 40-bit offloadable stretch on it, you could more likely robustly remember the mnemonic form if its only 40-bits or 50-bits (its just as bad from your perspective to lose money from forgetting as from theft!)  Or 88-bit vs 128-bit mnemonic perhaps though the difference is lower.  If its a lot of money maybe you could use 50-bit stretch and pay $5k in offloaded grind to redeem it.

One thing you could do is create a paper wallet in a safe or bank vault and a pre-created paper bitcon cheque to your paper wallet address.  This way as soon as you realize your laptop is stolen in a burglary, travel theft, hold-up etc you click the panic button and broadcast the paper-cheque, sending your assets over an air-gap into a bank vault.  Of course the law enforcement/criminals are going to realize this and try to stop you getting near to a keyboard.  You could even have a dead man switch or friend that does this for you.  You are not trusting them much as they cant take your assets, only transfer them with your bitcoin-cheque to your better physically secured air-gapped paper wallet.  Even the encrypted cheque could be published an encrypted form to the block chain, so that the panic word can release the cheque and the cheque cant be seized.  Say one word publicly or that gets out, and the assets are moved.  You could even have multiple encrypted cheques paying to different addresses or chain the process.

Adam

I dont think it matters so much the actual scenario the point is to find ways to improve bitcoin security (and security of data & auth keys generally).  As Ed Felten observed recently, no its not a good idea for judges to start thinking because they can issue subpoenas that internet physics and software architects somehow owes them data in a subpoenable form.  The reason is the design is the same whether you are protecting against theft, blackmail, extortion, corrupt insider, or subpoena - its all the same thing from a technology perspective.

https://freedom-to-tinker.com/blog/felten/silk-road-lavabit-and-the-limits-of-crypto/

Clearly whatever you think of the war on drugs, and personally I am against drug taking but also against governments in a free country removing individuals freedom to choose, DPR if the charges arent made up apparently tried to have someone assassinated which obviously is very uncool.

Anyway sometimes its fun to think about and articulate security problems in a james-bond-esque setting, over the equivalent but boring dining-cryptographers setting etc, but the techniques are the same if its a wealthy individual safe-guarding their money from extortion, or a normal level wealth protecting their bitcoin from theft physical or virtual.

Adam

Ha, it seems to me that cryptography was actually established to protect against evil villains, not your Grandma or roommate, who most likely don't even know how to view your files with hidden attributes. ;)


Now back to something more on topic, I wonder if it makes sense to imagine some key-stretching function f, which for different values of x, would take vastly different time to find y=f(x) or y=f(x,s) if we add a salt, like for x1 it would take 1 nanosecond to execute the calculation, but for x2 it would take 1 minute. The disparity in the time of computation must be so large that a small percentage of "tough" numbers will take up most of the computation time. With such a function at hand, and a statistical knowledge of the distribution of the "tough" numbers x_d, I can obtain an estimation of the time it takes to scan across a randomly selected range of numbers to find a "softie" number, which should contain a fair bit of entropy, the total scanning time/initial stretched key generation time should be long enough yet tolerable(like 1 day or so), while the stretched-key creation time with the initial key already known much shorter as the chosen x is a softie. Now for an attacker who has no information whatsoever about the seeding key being used, it will take him an infeasibly long time to brute-force to the number we use, due to those "tough" numbers on his way, as he has to start from zero and scan through a much larger range of numbers than us. I naively assume that if such a function can be created, it could provide us with a reasonable key initialisation time(hours or days), short key reconstruction time with seeding key known(seconds), and infeasibly long brute-forcing time, and relatively benign ket/salt entropy requirement.

Example: Let's say we have 2^64 elements to try, dividing into 2^32 sets, testing all 2^32 elements in one set will take approximately 1 day according to some statistics, with 99% of the time being taken up by testing against just 1% of the tough elements, so that instead of having a brute-forcing/normal enhanced key creation time of about 2^63, we could, hypotehtically make it much longer without increasing password complexity.

This can be done although it requires a bit of discipline, which not everyone has.

Maybe you could do it (inflated variance) but generally I think it doesnt help because the attacker can just grind them all in parallel (multi tasking if necessary) so the uneven work factor will be removed.  You could think of knowledge of which bucket the real key is in as the salt, ie if you make a random salt in PBKDF2 or Scrypt and delete it as I suggested somewhere in the above thread (not a new idea, Rivest et al proposed it in their time-lock puzzle paper) then you can have instant setup, but a lot of work to decrypt.  If you keep the salt then it can be very secure.

eg if you have a server with a password hash (or public key/address created with it), but the user has the salt stored and the salt is 128-bits, the server can verify when you get the password right, but the server (nor any hackers who break in and take the password hash db) have no hope what-so-ever to grind the password.  Actually I used that design in oneid.com end-2-end secure auth model in several places.  (I am a crypto consultant to them and a few other companies).

The limitation for general use is you can think well the salt is on your disk, what if you have a disk crash.  In which case the salt is so large you'd just as well call it a key and be done.

Adam

Thank you Adam for the advice.


The function itself is supposed to be public knowledge, but the locations of the tough numbers are not, theoretically anybody can find out but testing every element is an infeasible task, and there should be no easy workaround, much like the situation of prime numbers. But as Adam has pointed out, this scheme has its own problems.

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

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

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

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,  ;D ;D ;D, 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

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

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

"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

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.

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.

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

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

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.

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