Topic: hardening brain-wallets with a useful blind proof of work - page 2. (Read 16836 times)

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

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

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.

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

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.

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.

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.

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.

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.

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.

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

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.

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/[email protected]/msg02948.html


Adam

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