fantastic Finally someone figured it out for linux.  17.4 Mkey/s on 7870.

I was thinking there ought to be a code patch to make it work other than copying the old version amdocl .so (or the windows analog) because surely that library is not that bugged - people are playing games on it etc.  Must be some thing that goes wrong (results inconsistent gpu/cpu) that could be debugged and fixed. 

But this is close enough for now.

Adam

My claim is that brain-wallets are dangerous (private key which is the password) as your virtual "encrypted wallet" is effectively stored on the block chain so anyone can have a go at grinding your password.  GPUs are frighteningly fast at grinding passwords.  Even a 46-bit password can be ground for 50c of compute at bitcoin prices or analogous with litecoin/scrypt.

Its not that much better with an encrypted randomly generated private key (BIP 38), if you are worried that its realistic other people will get hold of your encrypted private key.  Once that happens you're in the same boat as brain-wallets against the people who have your encrypted key file/wallet.

Of course its better to encrypt than not.

But about increasing the security of your private key, choose a parallelizable key derivation and buy yourself a machine with a lot of GPU cores.  (eg Scrypt(iter=1,deleted salt,...) with a deleted 30-bit or 40-bit salt; it will be GPU expensive to decrypt.  This delete salt bits (not a new idea its due to Merkle 1976 and mentioned in Rivest et al's time-lock puzzle paper) its described here:

https://bitcointalk.org/index.php?topic=311000.msg3342217#msg3342217

Also see the top part of the thread, I proposed a couple of ways to securely outsource computing your KDF so that you can pay 50c and get 100 GPU miners to stretch your key for you, this one is interactive:

https://bitcointalk.org/index.php?topic=311000.msg3341985#msg3341985

or lots of ASIC miners in the second version which is non-interactive, its a stretched signature verification, and after its spent you need to delete the private key component c to prevent somone who later gets a copy of your private key grinding your password against the now public stretched signature:

https://bitcointalk.org/index.php?topic=311000.msg3402287#msg3402287

Adam

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

OK that makes better sense!  (I thought I must be missing something).

So with that clarification I wonder what the benefits if any are of public unlinkable derivation (public key and random encrypted chain code). 

- I think one thing is it could provide an infinite look-ahead - ie you dont need to look for keys of iteration i for some number of steps ahead, you could probably search all of them for the parent hierarchical base key, ie just decrypt E( Q, c' ) to find c' and verify to see if its one of yours vs random garbage.

- Another property is the sender after the fact doesnt know who he sent to if he doesnt log random c' values. 

- Also there's no stored chain code on the sender to be compromised (he can start from scratch fetching the base address from the shop site online and delete it with cookies, web logs etc at end of session)

Adam

ps It wasnt obvious reading BIP 32 and even looking now I dont see mention of the security requirements for handling chain codes.  If thats not frozen it might make sense to put a note saying that somewhere.  I could even take a stab at the edit - looks like its an editable page.

except you probably want c' to be random but derived as in BIP 32 like c"=random, c_i=MAC(c",Q,i) to avoid maliciously chosen c_i values as the recipient is eventually going to sign a tx using x+c_i as a private key; seemingly ECDSA is relatively immune to that (from looking at the question briefly) but in the general case for other signature schemes that is a potential opening.

Adam

So in BIP 32 https://en.bitcoin.it/wiki/BIP_0032 (simplifying) the base private key is x, base public key Q=xG, then public derivation (BIP calls this function CKD) is Qi = m*G+Q where m = MAC(c,Q,i) and c is the public "chain code" (they use MAC HMAC-SHA512).  The recipient can derive key x_i corresponding to Qi as x_i = m+x mod n (because m*G+x*G = (m+x)*G).

Now this is good for security but not so good for privacy as any public derived address is linkable as an analyst can just repeat the derivation function and check which key Q it is for.  In theory part of the reason to even use multiple receiving keys at all is to reduce linkability (unless there is an account benefit - one for each sender?)

(With private derivation (also specified in BIP 32) conversely here x_i = m'+x where m'=MAC(C,x,i), and Qi=x_i*G so there is no linking but that can only be computed knowing the private key x, so it is not publicly computable, and does not interoperate ie for using public derivation both sender and recipient have to use the public derivation method; and for private derivation the recipient has to generate and send the address to the sender, you cant mix public & private derivation as they are incompatible).

It seems to me you could make public derivation unlinkable eg by creating a random secret "chain code" and encrypting it for the recipient.  So c' = random, Qi = c'G+Q, E( Q, c' ).  Where E is public key encryption with Q public key, such as EC elgamal E(Q,c') = (A,B) where k=random, point C=[c',f(c')] where EC is defined by function f, A=C+kQ, B=kG.  Decryption is c'=[A-xB].x.  Now to receive transactions you need a full client and attempt to decrypt c" values and check if c"*Q=?Qi.

With out of band coordination the sender and recipient could reduce the amount of full decryption the recipient needs to do.  (Eg he can replace public key encryption function E by AES and a shared key)

Adam

With Benaloh it true that B can be smaller (than the order of the group of a secure EC DL instance) and actually it has to be smaller if you use decryption, because decryption takes time sqrt(B).  But I dont think mod B solves the inherent problem with less than, because as a generic thought experiment consider B=251 (or n=251 in an EC group of order n using EC discrete log instead of Benaloh), now you have an input 4, you can make the homorphic addition still work while defrauding the network:

E(4) = E(127)+E(127)+1

where 1 is the clear text fee (ie the recipent encrypts 1 and checks E(4) =? E(127)+E(127)+E(1)) which is true mod 251 because 127+127+1=255-251=4, and now you have created forged value of n=B=251 coins.

Did you see the range proof on this thread? 

https://bitcointalk.org/index.php?topic=305791.msg3294618#msg3294618

I optimized the application of the Schoenmakers range proof and comes to 1kB-2kB per value (proof size depends on the precision of the coin value, not on the size of n).

I avoided Benaloh because its less well used, not EC; and you still need the range proof I argue above, and being mod B anyway restricts your coin value precision to B, and the range proof will be no smaller in Benaloh than normal EC discrete log as a result.


Using the Pederson commitment as shown on the other thread allows validation of adding up without revealing the transaction details because there is also an undisclosed x (value private key), ie c1=g^v1*h^x1 and x1 is never disclosed, and yet addition can be checked.


Also about your idea there is a way to prove two discrete logs are equal that may allow what you want (havent checked how that works out with Benaloh).

Adam

I think it maybe simpler (and perhaps equivalent I didnt digest Sergio's post yet maybe we thought of the same thing) to say you only load the hotwallet with timelocked funds, so that they can be spent after the timelock, or undone with a cold wallet key before the timelock.

Now unfortunately bitcoin timelock is not a function but a property of a script, so you cant write "sig cold OR ( timelock > +6 AND sig hot ), but never the less you can do things like that indirectly.  (Also locktime doesnt even work properly in that at some point its implementation was changed so that is the users responsibility to send it after the locktime has passed, otherwise nodes discard it.)

It seems that the simplest way to implement the OR you can do is load the hot wallet with cold key signe, timelock > +6 AND sig hot (where hot is the hot wallets address).  Then the hot wallet private key can spend the timelocked coins to users addresses.

The exchange can post the tx after timelock, but the exchange can also give it to the user now to repost himself, and to show to other users, and create follow-on dependent transactions, eg to spend it before the time lock has passed (the user accepting before locktime has passed is in an analogous situation to 0-confirms - if the coin turns out to be as a result of  a hot-wallet hack, the coin will be undone).

How the coin is undone is the exchange monitors transactions, and if it sees something anomalous it releases a set of transactions sweeping all contested hot wallet spends to a cold address.  It can have the cold-signed sweep-to-cold transaction set pre-prepared even so there is no need to access the cold wallet under pressure.

Doing that does remove the immediate irredeemability from bitcoins though.  eg if the cold transaction is every hour, then the merchants selling online irredeemable virtual goods may lose their goods if an exchange theft results in their payment being undone.  Ie in the event of theft, the person who most likely loses is the merchant that was abused to cash out.  Sounds a bit like credit card situation.

Adam

Well firstly the number of combinations of 2 transposed hex chars from a 256-bit (64 hex nibbles) is c(64,2) = 2016.  Secondly you need to swap about half the digits c(64,32)>2^64 for reasonable security and that will be really hard to remember, or not randomly chosen enough.

And thirdly for paranoia you probably dont want to do that directly   Because there are algorithms for finding discrete log knowing some of the digits, at least for non-EC discrete log.  So I think it would be safer to make x' the private key x'=H(shuffle(x)) and you publish shuffle(x).

In Shrem's case omitting one digit thats even worse - I presume they were in base58, so 44 chars, but actually you can use 128-bit private keys if you use them as a seed, then only 22 base-58 chars.

Then if Shrem missed one char there are 22 chars to choose from and each can hold 58 values 22*58=1276 which is laughably grindable.

I do like the private key on a physical object though.  Good unless you check out in a plane crash where the ring may get lost.  You want durable material, but I guess the jewelers know about that.

If you swap chars in 22 base-58 (128-bit private key) representation its weaker still 231 combinations.

Adam

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

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

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

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

Thats true as they are independent progress free works then.  But they do need to be time-stamped, which means some coordination (broadcast?) and incentive structure to ensure later miners do not disregard or throw away earlier wins.

Were you thinking that the block needs to include the reward proofs as a means to time-stamp?

Adam

I agree these objectives are important.  I explored this a bit in the past and it seemed to me it could work to have multiple smaller rewards, and multiple parallel winners, where the coinbase for each new block mined referred to the set of previous parallel blocks that are non-conflicting with it.  (There's not actually any need to orphan something just because its different so long as you dont disagree with it and bitcoin doesnt do that, just adopting new mined blocks as the new starting point unless there is conflict).  Then some heuristics for how reward is paid out, how fees are shared out.  I was kind of gratified that it seemed plausible that it should work, as it appears difficult to change anything much about bitcoin without making it worse in some way.  However its clearly less bandwidth efficient and more complicated rules have to be used for reward and fees.

Also its relatively easy to reduce variance of hashcash (or other proof of work functions), by the generic approach of using multiple sub-puzzles, however the problem is bitcoin is structured as a first-past-the-post race to find a solution (or first-n past the post with the multiple parallel chain) for the block reward, and if you reduce the variance the faster miner will win disproportionately to its power (eg win 75% of time with 50% of power or that kind of effect) which is bad. (You can see it more clearly with the thought experiment what if the variance is 0, ie the proof of work is deterministic, then clearly the fastest node will win every time.

Adam

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

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

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

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

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

Adam