hardening brain-wallets with a useful blind proof of work

[adam3us]

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:

public params:

n=pq (primes p & q deleted at setup)
g=shared generator
e=2^(2^w)-1 ie a big, big number w is work factor
y=g^e mod n (generated cheaply at setup, or computable one-off cost afterwards)

blind:

m=message
b=random blinding factor
r=g^b*m (broacast r to miners)

work:

s=r^e mod n (expensive because e is big and carm(n)=(p-1)(q-1)/2 is unknown)

unblind:

u=y^b (unblinding factor)
m^e = s/u (as s/y^b=r^e/g^{be}=g^{be}*m^e/g^{be})

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

[adam3us]

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.  

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

So I had a go at deciphering BIP 038 in summary what I think its doing is (ommitting lot and sequence and deterinistic IVs for simplicity):

user:

x1 = Scrypt( salt=random, pass )
P = x1*G

send (salt, P) to coin manufacturer ->

                                manufacturer:

                                x2 = random 24bytes
                                Q = x2*P
                                k = Scrypt( salt2=H(Q)||salt, pass=P )
                                e = AES_k( x2 )

                                manufacturer puts e inside coin.

                <- send coin, (salt, e, Q) to user

                                then optionally creates conf code:

                                B = x2*G
                                c = AES_k( B )

                <- send conf code c to user

verify code c:

(by recreating P, then k from Q & P, decrypt c to get B, check Q = x1*B)

x1 = Scrypt( salt, pass )
P = x1*G
k = Scrypt( salt2=H(Q)||salt, pass=P )

Which seems reasonable enough, however its unfortunate that you have to repeat the Scrypt work at setup.

One thing that occurs to me eg as mentioned by Rivest et al in their time-lock puzzle paper is that it is easy to create work, if you are ok with parallelizable symmetric constructions (like scrypt(i) or PBKDF2(i) with i iterations) without *doing* the work during setup.

It seems to me therefore that the above protocol could avoid the javascript overhead issue that forces users to choose a weak iteration level if they want to create the wallet in that way.

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.  (Or if you want to limit the parallelism say scrypt(i=65536, salt, pass) with a deleted 16-bit salt.  That should be parallelizable up to 65536 GPU cores (32x 7970 chips).

Symmetric time-lock puzzles can achieve decrypt asymmetry without repeating the work at setup...

(Rivest et al go on to avoid using that symmetric construct with an RSA related mechanism, because they are trying to lock information for an approximate future date, rather than protected by a specific amount of grinding work.)

Adam

[Jan]

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

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.

[adam3us]

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

[gmaxwell]

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

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.

[oakpacific]

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

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

[gmaxwell]

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

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.

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

[justusranvier]

"just pocket money" has a way of growing through lazyness and the sum of all pocket money is great in any case.

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.

[cbeast]

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.

[oakpacific]

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

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.

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.

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

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.

[gmaxwell]

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.

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

Brainwallet is mainly designed to solve the deniability problem,

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.

[oakpacific]

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.

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

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?

Brainwallet is mainly designed to solve the deniability problem,

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.

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.

... (1) Perhaps you should engage in less unlawful activity.

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

 

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

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

[gmaxwell]

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.

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.

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 should also talk about how difficult it would be for people to use such mnemonic encodings?

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?

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

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

[adam3us]

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

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

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

[adam3us]

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

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.

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

[oakpacific]

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

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.

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.

[dserrano5]

Can U memorize all properties of your super function in mind for years with the same ease as your password/number/whatever used for brain keys generation ?

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

[adam3us]

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.

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

[oakpacific]

Thank you Adam for the advice.

@oakpacific
U can invent super lovely functions for key
 stretching or for seeding password crazifying, but...

I think the dual point of gmaxwell's "BIP" was :
 a) If one will publish and standardize brainwallet's algo, then it will be open for attackers...
 b) If one will keep it secret and only for himself, then it can suffer from amnesia later...
 Can U memorize all properties of your super function in mind for years with the same ease as your password/number/whatever used for brain keys generation ?

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.

[adam3us]

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