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
Topic: hardening brain-wallets with a useful blind proof of work (Read 16836 times)
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.
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...
(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...
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).
Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as R = H2( (y=H(salt)), Q ), S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).
As stated that is a single use password because once a miner has published y=H(salt), Q is revealed and someone in possession of the encrypted private key X=AES(K,x) where K=Scrypt(password) can grind by trying x' values to check if x'G =? Q.
To have a multiple address, reusable password the user needs to use BIP 32 private address derivation and store encrypted random chain codes so that Qi=(x+ci)*G is used in place of Q in the above protocol. ie Q'i=H2(y=H(salt),Qi) and to delete ci after it is spent.
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.
Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as R = H2( (y=H(salt)), Q ), S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).
User deletes y, Q and A and k-bits of salt.
One downside of this pattern of not knowing if your password is correct at the high-level is that if you misttype your password, you lose 20c each time. If you are using the process to offload a 32-bit KDF from your cheap/slow offline wallet computer to your own fast online computer its not a huge deal, just try again as there would be no fees.
But if you are offloading a 46-bit key stretch online you could do with either a check character on disk (which makes 57/58 passwords offline grindable, so removes 6-bits from the password strength, or only a 40-bit key stretch for the CPU cost of a 46-bit one).
Or better augment the users password with a check character so that the user is expected to remember. Remembering a check char doesnt seem so unreasonable if you are trying to remember a 50+ bit password you can probably remember a single char that was machine generated appended to the end. Computed in such a way as to catch transposed characters, missed chars as well as typos with probability 57/58.
Then for 60c per transaction in additional fees you can bump the security of a 50-bit password to 96-bits, with the knowledge that grinding is uneconomical even though your password unstretched is within grinding range. I bet most people's wallets (whether offline or online), once an attacker has their disk so they become brain-wallet like, could be economically ground currently for amounts of $10k and above say.
Basically I claim, everyone effectively has the brain-wallet "you're either kidding yourself how good your password is, or your password is so good you'll forget it", once you factor in an attacker getting a copy of the (random private key) encrypted deterministic wallet.
Adam
It's not a downside, it's a feature, or someone who has your disk can go at it repetitively to decrypt your private key.
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.
Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as R = H2( (y=H(salt)), Q ), S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).
User deletes y, Q and A and k-bits of salt.
One downside of this pattern of not knowing if your password is correct at the high-level is that if you misttype your password, you lose 20c each time. If you are using the process to offload a 32-bit KDF from your cheap/slow offline wallet computer to your own fast online computer its not a huge deal, just try again as there would be no fees.
But if you are offloading a 46-bit key stretch online you could do with either a check character on disk (which makes 57/58 passwords offline grindable, so removes 6-bits from the password strength, or only a 40-bit key stretch for the CPU cost of a 46-bit one).
Or better augment the users password with a check character so that the user is expected to remember. Remembering a check char doesnt seem so unreasonable if you are trying to remember a 50+ bit password you can probably remember a single char that was machine generated appended to the end. Computed in such a way as to catch transposed characters, missed chars as well as typos with probability 57/58.
Then for 60c per transaction in additional fees you can bump the security of a 50-bit password to 96-bits, with the knowledge that grinding is uneconomical even though your password unstretched is within grinding range. I bet most people's wallets (whether offline or online), once an attacker has their disk so they become brain-wallet like, could be economically ground currently for amounts of $10k and above say.
Basically I claim, everyone effectively has the brain-wallet "you're either kidding yourself how good your password is, or your password is so good you'll forget it", once you factor in an attacker getting a copy of the (random private key) encrypted deterministic wallet.
Adam
AES is bad (baked by NSA).
Please use another cipher (say, Serpent, Threefish or ...)
Please use another cipher (say, Serpent, Threefish or ...)
AES is not baked by NSA, NIST selected AES as their standard, NSA only approved it as fit for top secret information encryption, and they went as far saying all candiates are sufficiently strong to do the job.
We can be complete conspiracy freaks here, but SHA-256 underwent the same process.
"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
related idea, not for brain-wallets but for password encrypted random key wallets. [...]
type your password [... decrypt your private key, make a signature and...] send it to miners, have them do the bulk of the KDF work, and then either end up with an invalid transaction signature (if your password was mistyped) or a valid signature which they publish.
[...] if you make the address of form H2( H( salt, public-key ) ) and then delete the salt, then the miner can try to find the salt without having to trust the miner. [...] Once salt is known the signature is cheaply validatable by anyone.
[...]
The miner may have to do a committed transaction (if he is not mining his own blocks to put the transaction into) with the salt because otherwise the reward could be stolen. Collecting the KDF fee is a bit insecure otherwise.
type your password [... decrypt your private key, make a signature and...] send it to miners, have them do the bulk of the KDF work, and then either end up with an invalid transaction signature (if your password was mistyped) or a valid signature which they publish.
[...] if you make the address of form H2( H( salt, public-key ) ) and then delete the salt, then the miner can try to find the salt without having to trust the miner. [...] Once salt is known the signature is cheaply validatable by anyone.
[...]
The miner may have to do a committed transaction (if he is not mining his own blocks to put the transaction into) with the salt because otherwise the reward could be stolen. Collecting the KDF fee is a bit insecure otherwise.
Here's a way to repair the security of the process of the miner claiming the fee for doing the KDF work.
Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as Q' = H2( (y=H(salt)), Q ), S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).
User deletes y, Q and A and k-bits of salt.
User publishes extended address E and receives funds on it.
When user wants to spend funds (or an attacker who has the users hard drive), he types his password and computes K'=Scrypt(password), and computes a candidate private key x'=AES-Dec(K',X). The candidate (non-extended) public key is Q'=x'*G. The user cant tell if this is the right password (right private key x' nor right public key Q') the work to brute force k-bits of salt is much more CPU power than he has.
User publishes (R, S, ECDSA(x',tx)); anyone can compute Q' from the signature, and see that the signature is valid, but it takes work to discover if R is derivable from Q'. Thats the work the miner does as follows: the miner tries to find salt in the defined (advertised) search space such that either H2(H(salt'),Q') == R (because the password is correct) or if the password is wrong the miner finds salt'*Q' == R mod 2^k (ie last k bits match). If the password is right the miner does not publish salt, only publishes H(salt') and signs with salt as private key to R in order to claim the full reward (40c+20c). If the password is wrong (miner did not find full match within search space) miner signs with salt' but as H2(H(salt'),Q') != R he can only claim 20c.
Unlike before it is not possible for other miners to take the solution and assign the fee to themselves so the KDF miner does not need to be a bitcoin miner (to include his own fee collection into a block), nor does he have to use committed transactions for security.
Adam
"Q' = H2( (y=H(salt)), Q )" should be R = H2( (y=H(salt)), Q ), right?
related idea, not for brain-wallets but for password encrypted random key wallets. [...]
type your password [... decrypt your private key, make a signature and...] send it to miners, have them do the bulk of the KDF work, and then either end up with an invalid transaction signature (if your password was mistyped) or a valid signature which they publish.
[...] if you make the address of form H2( H( salt, public-key ) ) and then delete the salt, then the miner can try to find the salt without having to trust the miner. [...] Once salt is known the signature is cheaply validatable by anyone.
[...]
The miner may have to do a committed transaction (if he is not mining his own blocks to put the transaction into) with the salt because otherwise the reward could be stolen. Collecting the KDF fee is a bit insecure otherwise.
type your password [... decrypt your private key, make a signature and...] send it to miners, have them do the bulk of the KDF work, and then either end up with an invalid transaction signature (if your password was mistyped) or a valid signature which they publish.
[...] if you make the address of form H2( H( salt, public-key ) ) and then delete the salt, then the miner can try to find the salt without having to trust the miner. [...] Once salt is known the signature is cheaply validatable by anyone.
[...]
The miner may have to do a committed transaction (if he is not mining his own blocks to put the transaction into) with the salt because otherwise the reward could be stolen. Collecting the KDF fee is a bit insecure otherwise.
Here's a way to repair the security of the process of the miner claiming the fee for doing the KDF work.
Q=xG (x is ECDSA private key, Q is ECDSA public key)
A=H2(Q) address is hash of public key
Extended public key (R,S) as R = H2( (y=H(salt)), Q ), S=salt*G
Extended address E=H2(R,S).
K=Scrypt(password), encrypted private key X=AESEnc(K,x).
User deletes y, Q and A and k-bits of salt.
User publishes extended address E and receives funds on it.
When user wants to spend funds (or an attacker who has the users hard drive), he types his password and computes K'=Scrypt(password), and computes a candidate private key x'=AES-Dec(K',X). The candidate (non-extended) public key is Q'=x'*G. The user cant tell if this is the right password (right private key x' nor right public key Q') the work to brute force k-bits of salt is much more CPU power than he has.
User publishes (R, S, ECDSA(x',tx)); anyone can compute Q' from the signature, and see that the signature is valid, but it takes work to discover if R is derivable from Q'. Thats the work the miner does as follows: the miner tries to find salt in the defined (advertised) search space such that either H2(H(salt'),Q') == R (because the password is correct) or if the password is wrong the miner finds salt'*Q' == R mod 2^k (ie last k bits match). If the password is right the miner does not publish salt, only publishes H(salt') and signs with salt as private key to R in order to claim the full reward (40c+20c). If the password is wrong (miner did not find full match within search space) miner signs with salt' but as H2(H(salt'),Q') != R he can only claim 20c.
Unlike before it is not possible for other miners to take the solution and assign the fee to themselves so the KDF miner does not need to be a bitcoin miner (to include his own fee collection into a block), nor does he have to use committed transactions for security.
Adam
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.
So it would be desirable to have a secure server offloadable KDF, which means a kind of blindable deterministic proof-of-work.
http://www.mail-archive.com/[email protected]/msg02948.html
Quote from: adam3us topic=bitcoin-dev
Rivest et al in their time-lock puzzle paper is that it is easy to create work without doing the work during setup [...] avoid the javascript overhead issue that forces users to choose a weak iteration level.
eg create a 32-bit random salt, replace scrypt(i=16384, salt, pass) with scrypt(i=1,salt, pass) to be brute forced based on deleted salt. Immediate 2^32 = 4billion iteration salt without any significant setup cost.
eg create a 32-bit random salt, replace scrypt(i=16384, salt, pass) with scrypt(i=1,salt, pass) to be brute forced based on deleted salt. Immediate 2^32 = 4billion iteration salt without any significant setup cost.
Here's another related idea, not for brain-wallets but for password encrypted random key wallets. So above I described the symmetric time-lock approach (by deleting some of the salt to instantly create a brute force target).
As a requirement what you would actually like is to be able to type your password, stretch it a little bit (to be not too slow on your not-that-fast single CPU system which could be an offline netbook wallet), send it to miners, have them do the bulk of the KDF work, and then either end up with an invalid transaction signature (if your password was mistyped) or a valid signature which they publish.
You would have to pay the miner something for this work eg 60c for 2^46 SHA256 iterations at whatever the bitcoin mining difficulty/reward cost is. (Its perhaps better with GPU friendly Scrypt to not compete for bitcoin security as GPU capacity is mostly unrelated to bitcoin (ASIC) capacity.)
At first I was thinking this would be very hard to arrange, but if you make the address of form H2( H( salt, public-key ) ) and then delete the salt, then the miner can try to find the salt without having to trust the miner. Until the salt is found the signature is of unkown validity because it is unclear whether or not it matches the public key or is a random forgery. Once salt is known the signature is cheaply validatable by anyone.
The user tries to type their password (or an attacker with a copy of their disk tries to grind their password). So they convert the password into a key and decrypt the encrypted wallet private key. However we remove any checksums so all private keys are equally plausible. The only way to verify the private key is to compute the public key and see if it is correct, however now this is an expensive operation to offload to an untrusted fast machine, or miners generally for a fee.
If the user guesses their password wrongly the miner will still collect a smaller fee (20c) for presenting a 45-bit collision with the address, whereas the full fee (40c) is available for a full match with the address. (This is necessary because there may exist 45-bit collisions on the real address and the others cant tell without redoing the full 46-bit address search). Note the work is at most 2^46 for the full match because it is a known solution, but could take longer for the 45-bit collision if there is no full match because the password is wrong.
The miner may have to do a committed transaction (if he is not mining his own blocks to put the transaction into) with the salt because otherwise the reward could be stolen. Collecting the KDF fee is a bit insecure otherwise.
https://bitcointalk.org/index.php?topic=206303.15
In this way you get a stronger KDF than you have hardware for by paying a small KDF fee, with the benefit your password encrypted wallet becomes very expensive to grind. (Bearing in mind that if someone has your hard drive, all keys are "brain-wallets").
Or you could offload the KDF work from an offline wallet (which maybe a cheap slow old netbook) to a beefy less well secured network connected GPU desktop.
Bitcoin script doesnt have scrypt as a primitive (could be a useful function to add), so the proof has to involve hashes.
You could probably do all of this with existing P2SH without any new features (except for the committed transaction).
Not completely elegant but somewhat interesting and maybe leads to some other ideas.
(To pay the KDF fees the user needs an unprotected or simple (different) password protected wallet with a smaller balance).
Does not seem to be compatible with deterministic wallets at least as stated above.
Adam
Hi Adam.
Interesting ideas about brain-wallets.
Some other thoughts and viewpoints about them.
Availability and ASIC resistance of the pass-phrase stretching.
Scrypt is very scalable and has a good ASIC resistance but is not so available especially as web implementation.
So if I would implement scrypt as password stretching before the key-pairs are generated would be a good hardening.
However if my website goes down some users which have memorized only the pass-phrase and have put coins on addresses generated with scrypt would have difficulties to generate it again.
Hardening with PBKDF2 wouldn't be at all ASIC resistant but has a high availability. He knows he created 10 000 rounds PBKDF2 then if the site is not available he can search a simple PBKDF2 rounder on the web and do it the take any brain-wallet which can create the key-pairs.
But what about bcrypt ? I think it is the best compromise. Bcrypt stretching has a good ASIC resistance but a better availability then scrypt.
With creating the pas-phrase rounds on a server I don't think it is a good idea. Even if the connection is secure may be the server isn't.
Better to wait 1 min if creating the key-pairs on a smartphone then wait only 10 s but the pass-phrase being stored.
.............
How to pay with a brain-wallet a lawyer if you are innocently arrested by an oppressive regime, paying step by step(not all the content of your brain-wallet) ?
It must be generated a key-pair chain.
But how to do it without a computer ?
MIND HASHING is the solution.
A new(stil not working) concept what I was thinking about.
MindHash(passphrase+1) ->GeneratedPassphrase1
MindHash(passphrase+2) ->GeneratedPassphrase2
...
MindHash(passphrase+n) ->GeneratedPassphrasen
On each meeting the innocent prisoner could pay a certain amount of bitcoin, namecoin or whatever to his lawyer. We suppose that his lawyer knows how to use brain-wallets.
The problem is only that such a function still doesn't exist. (with the fulfillment of requirement that from 1 or more GeneratedPassphrases you cannot find out another GeneratedPassphrase)
Is it possible to create such a hashing function what you could calculate in your mind and is not breakable with a computer ? Eventually some highly available objects could be used.
Let us think about.
Starting points could be:
- some mnemonic systems
- something like Solitaire from Cryptonomicon,
, but here you need cards
- something like RC4, where you need pieces of paper
Let us give a name for solving this problem:
The innocent prisoner and his lawyer's - problem
Interesting ideas about brain-wallets.
Some other thoughts and viewpoints about them.
Availability and ASIC resistance of the pass-phrase stretching.
Scrypt is very scalable and has a good ASIC resistance but is not so available especially as web implementation.
So if I would implement scrypt as password stretching before the key-pairs are generated would be a good hardening.
However if my website goes down some users which have memorized only the pass-phrase and have put coins on addresses generated with scrypt would have difficulties to generate it again.
Hardening with PBKDF2 wouldn't be at all ASIC resistant but has a high availability. He knows he created 10 000 rounds PBKDF2 then if the site is not available he can search a simple PBKDF2 rounder on the web and do it the take any brain-wallet which can create the key-pairs.
But what about bcrypt ? I think it is the best compromise. Bcrypt stretching has a good ASIC resistance but a better availability then scrypt.
With creating the pas-phrase rounds on a server I don't think it is a good idea. Even if the connection is secure may be the server isn't.
Better to wait 1 min if creating the key-pairs on a smartphone then wait only 10 s but the pass-phrase being stored.
.............
How to pay with a brain-wallet a lawyer if you are innocently arrested by an oppressive regime, paying step by step(not all the content of your brain-wallet) ?
It must be generated a key-pair chain.
But how to do it without a computer ?
MIND HASHING is the solution.
A new(stil not working) concept what I was thinking about.
MindHash(passphrase+1) ->GeneratedPassphrase1
MindHash(passphrase+2) ->GeneratedPassphrase2
...
MindHash(passphrase+n) ->GeneratedPassphrasen
On each meeting the innocent prisoner could pay a certain amount of bitcoin, namecoin or whatever to his lawyer. We suppose that his lawyer knows how to use brain-wallets.
The problem is only that such a function still doesn't exist. (with the fulfillment of requirement that from 1 or more GeneratedPassphrases you cannot find out another GeneratedPassphrase)
Is it possible to create such a hashing function what you could calculate in your mind and is not breakable with a computer ? Eventually some highly available objects could be used.
Let us think about.
Starting points could be:
- some mnemonic systems
- something like Solitaire from Cryptonomicon,
, but here you need cards- something like RC4, where you need pieces of paper
Let us give a name for solving this problem:
The innocent prisoner and his lawyer's - problem
People who haven't worked on password cracking [...] Today the tools are significantly better and have been refined through the disclosure of hundreds of millions of unencrypted passwords and the same kind of statistical tools that power speech recognition and automatic human language transaction. This statistical intelligence gets backed up by the brute force of GPU and FPGA clusters that can try hundreds of million or even billions of attempts per second.
Do you know is there some convenient package, or existing cracking tool that works in reverse - you give it your password, and it tells you how long it would've take it to find it using its heuristics, common words, l33tification, number and symbol combination rules?
That might be a good demonstration for would be brain-walleters. The other problem is even thats misleading because its not specific to them if you took someones online posts, handles, street address, publicly listed stats from social media sites a lot of the apparent entropy is going to evaporate also. Need to augment the cracker with that info first.
Adam
There's a number of those, and none of them will give you a perfect estimate, but a pretty good one is zxcvbn:
demo and information:
https://dl.dropboxusercontent.com/u/209/zxcvbn/test/index.html
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
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.
@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 ?
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.
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
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.
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).
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).
Quote from: gmaxwell
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.
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).
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).
Quote from: gmaxwell
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
Jump to: