wallet destruction

[gmaxwell]

What is your birthdate?
What city were you born in?
What is your email address?

Hash those three values and that is your salt.

That isn't "salt" by anyone's definition,  it's additional structured very low entropy passphrase material— which might do enough to keep the horrible insecurity of the system from casually being discovered (much in the same way as the debian breakage of openssl still leaving the PID as a source of randomness preventing that flaw from being discovered for years) but it wouldn't actually make the system acceptably secure.

[1713967609]

1713967609

[1713967609]

1713967609

[DeathAndTaxes]

gmaxwell 5 common dictionary words chosen randomly have at least 40 bits of entropy if the dictionary has at least 2000 words (2000^5 > 2^40).

"People on this forum have frequently bragged about their oh so secure schemes, which actually provide fairly little entropy. "

Ok but that doesn't mean you CAN'T have sufficient entropy.

On salt
Simply ask user determinstic questions (such as dob, place of birth, father middle name, etc).  Salt isn't a secret our goal here is simply to prevent accidental collision, and high speed lookups by pre-computational attack.

On users

Even the most intelligent users will sometimes make boneheaded moves, so even if you're confident that you're better than the typical user— you still should strongly prefer software that isn't gratuitously vulnerable to operator error. Any developer who isn't assuming that their users will make mistake, will choose passwords with less entropy then they think they have, will leak partial passwords to shoulder surfers, etc. just hasn't studied the problem space hard enough.

Then don't let the user choose.  Have the wallet pick 5 random words from a dictionary of 2000+.  User can press [generate new] until they find a set of words they can memorize.  If taken randomly then entropy is ensured.

The 30 minutes assumption is insane too

Notice I said HIGH SECURITY wallet.  You are trading generation time for strength.  For most users 30 minutes isn't necessary.  Even 30 sec generation time would provide massive hardening against a multi-terrahash brute force attack.  

I am not saying this is the ONLY way to achieve a secure wallet.  I just hate these blanket statements like deterministic wallets aren't safe or you MUST have  backup.  It simply isn't true.

It is possible to make a wallet which is secure, deterministic, easy to memorize, and doesn't require backups.  

[DeathAndTaxes]

What is your birthdate?
What city were you born in?
What is your email address?

Hash those three values and that is your salt.

That isn't "salt" by anyone's definition,  it's additional structured very low entropy passphrase material— which might do enough to keep the horrible insecurity of the system from casually being discovered (much in the same way as the debian breakage of openssl still leaving the PID as a source of randomness preventing that flaw from being discovered for years) but it wouldn't actually make the system acceptably secure.

Birthdates and places of birth aren't randomly distributed?  Really?  Low entropy?
Salt isn't a secret.  It should be assumed the attacker has the salt value.   

Lets look at just birthdate:  365 days are year almost perfectly distributed is > 8bits of entropy.  Birth year has much less entropy due to clustering effect but even if we assume 99% of birth years are clustered around a 20 year range that nets us at least 4 bits of entropy.  So birthdate alone has ~12 bits of entropy (likely more).

[gmaxwell]

maxwell 5 common dictionary words chosen randomly have at least 40 bits of entropy if the dictionary has at least 2000 words (2000^5 > 2^40).

If they are chosen randomly. Which almost always they won't be if you allow the user to do it.

40 bit searches aren't that hard either— I did a bigger search that 40 bits to find the signature at the bottom of this post.  You can argue that your strengthening makes that impossible but the security of strengthening is pretty squishy.  

our goal here is simply to prevent accidental collision,

Preventing accidental collision just hides the actual insecurity of the system. If there was any risk of accidental collision then the risk of compromise by a savvy attacker with a good probability model is much greater.

Then don't let the user choose.  Have the wallet pick 5 random words from a dictionary of 2000+.  User can press [generate new] until they find a set of words they can memorize.  If taken randomly then entropy is ensured.

If you don't let the user choose, you have what I suggested in my original post except without enough entropy.  The scheme electrum  uses only 12 words taken from a dictionary that uses words which are distinct and easily memorable and provides 128 bits of entropy.

If you offer the [generate new] you lose at least log2(average clicks) of entropy from the clicking, but probably more because users will just click until they hit a password with usually low markov entropy, e.g. they'll self-select insecure sequences because those ones are more memorable and it's exactly that process the attacker will model.

If the dictionary is well chosen you can have acceptable machine generated seeds which users can reasonably memorize without compromising on entropy.

I am not saying this is the ONLY way to achieve a secure wallet. I just hate these blanket statements like deterministic wallets aren't safe or you MUST have  backup.  It simply isn't true.
It is possible to make a wallet which is secure, deterministic, easy to memorize, and doesn't require backups.

Please, stop conflating 'deterministic' with shit-in-your-memory. They are not the same. A wallet which was based on a cryptographic PRNG with two megabytes of starting state would absolutely be deterministic but could never be memorized.  (also— please don't yell, it's not polite)

If you add the qualification, "while in the hands of a large collection of actual users", which of course is the goal of anyone writing software worth discussing here,  then it absolutely is true, at least if you're going to insist that purely random electrum seeds aren't easy to memorize.

(I think the memorability of electrum seeds is debatable. The kind of user who might have a fighting chance of using a pure password scheme securely will have no trouble memorizing an electrum seed. Joe-blow not so much. The difference here is that in a password only scheme joe-blow— who happens to work at mtgox— would get owned, lose 100,000 of other people's bitcoins and send our reputation into the trash,  while in the electrum/armory like scheme he'd take the require 30 seconds to make a backup and everything would stay secure)

[casascius]

What is your birthdate?
What city were you born in?
What is your email address?

Hash those three values and that is your salt.

That isn't "salt" by anyone's definition,  it's additional structured very low entropy passphrase material— which might do enough to keep the horrible insecurity of the system from casually being discovered (much in the same way as the debian breakage of openssl still leaving the PID as a source of randomness preventing that flaw from being discovered for years) but it wouldn't actually make the system acceptably secure.

I think this was brought up not to dispute the definition of salt, but to refute the claim that someone could attack all brainwallet users at once with the same effort, just so long as trivial steps were put in place to control for it.

[DeathAndTaxes]

40 bit searches aren't that hard either— I did a bigger search that 40 bits to find the signature at the bottom of this post.  You can argue that your strengthening makes that impossible but the security of strengthening is pretty squishy.  

You only did it because the algorithm was simplistic enough to try tens of millions of private keys per second.  Now what if you could only try a dozen per second?  Could you still do it in a year? a lifetime? and at what economic cost?  If the key stretching increases the cost of a search by a factor of a million or so you have gained 20 bits in key strength.  If it increases it by a factor of a billion you have gained 30 bits.

60 bits of entropy at 1 million keys per second is no more secure against brute force attack than 40 bits of entropy at 1 key per second.

Is it your contention that you could brute force a 40 bit passphrase w/ 30 bits of salt and a billion fold key hardening?

If it is then I think we can setup a pretty interesting wager.

(I think the memorability of electrum seeds is debatable. The kind of user who might have a fighting chance of using a pure password scheme securely will have no trouble memorizing an electrum seed. Joe-blow not so much. The difference here is that in a password only scheme joe-blow— who happens to work at mtgox— would get owned, lose 100,000 of other people's bitcoins and send our reputation into the trash,  while in the electrum/armory like scheme he'd take the require 30 seconds to make a backup and everything would stay secure)

Until his backup is compromised because he emailed it to himself or worse he loses/corrupts it and having placed all his faith in it.

[gmaxwell]

I'm responding mostly out of mathmatical interest and because I'd gone through the trouble of writing this post before I saw that you'd persisted in your yelling.

Birthdates and places of birth aren't randomly distributed?  Really?  Low entropy?

They aren't randomly distributed, people like to #@$@ on some dates more than others resulting in more births on some days than others.

The FCC ham radio callsign database is the only thing I have handy with a lot of birth dates in it.. With 723624 entries, it is a pretty good sample.

But the actual entropy is greater than I expected: 8.513275 bits,  8.510952 dropping the leap-day.

But this doesn't matter— say you get your 14.58 bits of DOB salt (the entropy from the FCC database for the full DOB), then an attacker going after only a million users simultaneously still enjoys a 40x speedup over a scalar attacker.

[casascius]

But this doesn't matter— say you get your 14.58 bits of DOB salt (the entropy from the FCC database for the full DOB), then an attacker going after only a million users simultaneously still enjoys a 40x speedup over a scalar attacker.

I think he proposed DOB, birthplace, and e-mail address (or substitute that is less likely to change throughout someone's life, such as father's name).  These numbers seem to assume only DOB.  The other two factors are rather significant in terms of the entropy they would add.

[gmaxwell]

Is it your contention that you could brute force a 40 bit passphrase w/ 30 bits of salt and a billion fold key hardening?

I might be able to, if your billion fold hardening was the addition operator or if you were calculating the 'billion fold' vs a memcpy, then I absolutely could (and of course the amount of 'salt' is irrelevant in such a statement). But that was never my contention.

My contention was instead that a system that attempted to work this way would be insecure _in practice_ due to human factors, and/or weaknesses in the strengthening system (which is not provably strong— e.g. it could actually by like my 'addition' example, and so it becomes an large additional assumption).

Until his backup is compromised because he emailed it to himself or worse he loses/corrupts it and having placed all his faith in it.

You can't win this sub-argument.  People forget passwords all the time— what if you get sick or hit on the head and lose a few chunks of your memory?  And you could remember an electrum seed sequence and make your memory your only backup if you want, at lest if you're the kind of person who would have any hope of remembering a secure password otherwise.

The difference there being the failure mode: Assuming the user would do something poorly, it's more secure if he leaves his backups carelessly laying around than if he uses a low entropy password (like "e352e8bceb", "8W3G7Pds9712++", or "7XiBKeJe5ochSqVW") that someone could simply bruteforce.   Sloppy backups, or especially sloppy backups plus a weak password, is simply more secure than a weak password.

And what if he emails it to himself? He can still be protected by passphrase. How is that less secure then any seed information not existing at all?   Even if you assume that he might use a somewhat weaker pass-phrase due to the existence of the stored entropy an attacker would still have to compromise his email account. Do you really think the false-confidence-induced entropy loss is going to be more harm than have-to-also-find-and-crack-his-email is a gain?

[DeathAndTaxes]

They aren't randomly distributed, people like to #@$@ on some dates more than others resulting in more births on some days than others.

The FCC ham radio callsign database is the only thing I have handy with a lot of birth dates in it.. With 723624 entries, it is a pretty good sample.

But the actual entropy is greater than I expected: 8.513275 bits,  8.510952 dropping the leap-day.

Well you own data shows it is pretty much randomly distributed.  If birth dates were assigned by a psuedo-random number generator then it would have 8.515 bits of entropy and the FCC files show 8.513.  Pretty much random.

But this doesn't matter— say you get your 14.58 bits of DOB salt (the entropy from the FCC database for the full DOB), then an attacker going after only a million users simultaneously still enjoys a 40x speedup over a scalar attacker.

How?  Unless you contend that all those users also are born in the same city, have same father's last name, have same email address, and went to the same highschool, etc.   

You just showed that birthdate alone has 14.58 bits of entropy.  How much do you think the intersection of birthdate, place of birth, email address, father's middle name, and gender?

Do you think there are even 2 Bitcoin users w/ the exact same:
birthdate
AND
place of birth
AND
father's name
AND
email address ( how the fuck does that happen)
AND
gender

Even with a billion users you would be lucky to get more than a handful of matches.  The point of salt isn't to be a secret it is to prevent pre-computational attacks, prevent collisions, and to prevent multiplier on work.

Now drumroll... if you think the entropy of the salt is still too low you can supplement it by a wallet generated small random number with their dictionary words.  A 4 digit "pin" would provide another 13 bits and isn't difficult to remember.

So 5 random dictionary words from a dictionary of 2000 gives us ~55 bits of entropy.*   I think most users could remember 5 random words plus a 4 digit pin. 

Something like:
win leave divide might 3817  (I grabbed those randomly from Oxford basic English 3000 word list)

Memorize this and you will NEVER lose your wallet again.  You are saying the average user can't handle that?


With use of an algorithm like scrypt you can limit attack to maybe 250,000x the computational power of the average user (largest botnet).  If your key derivation function takes 3 minutes that mean an attacker w/ 250,000x as much computational power is limited to a mere ~1400 passphrases per second.  55 bits of entropy @ 1400 passphrases per second = >80,000 years for a 10% chance of breaking it via brute force.

So please don't tell me it IMPOSSIBLE. 



* 3000 words might still be easy enough subset for memorization although it would require some research.  If 3000 words is viable you are looking at 58 bits.  Maybe 6 words is possible.  6 words from 3000 word dictionary is ~70 bits.

[DeathAndTaxes]

Is it your contention that you could brute force a 40 bit passphrase w/ 30 bits of salt and a billion fold key hardening?

I might be able to, if your billion fold hardening was the addition operator or if you were calculating the 'billion fold' vs a memcpy, then I absolutely could (and of course the amount of 'salt' is irrelevant in such a statement). But that was never my contention.

My contention was instead that a system that attempted to work this way would be insecure _in practice_ due to human factors, and/or weaknesses in the strengthening system (which is not provably strong— e.g. it could actually by like my 'addition' example, and so it becomes an large additional assumption).

By that logic Bitcoin is insecure because SHA-256 might be insecure.  There has been significant research into algorithms like PBKDF2 so the idea that it would have to be based on something cryptographically flawed 

Human factors can be minimized by using a system which doesn't rely on user making good judgements:
* Key stretching using strong hashing function w/ per round salt.
* Wallet provided high entropy passphrase via dictionary
* Deterministic salt combined w/ "PIN"


"win leave divide might 3817" protected w/ 3 minutes generation using PBKDF2, strong hashing function, and per round salt.  You wouldn't brute force it.  Not in a year, not in your lifetime.


Of course we seem to be going off track.  Your contention initially was that a high security deterministic wallet w/o backups was impossible, flawed, and naively weak.   Now it sound more like there are concerns w/ implementation.  I will take that as a minor victory and call it a night.

[gmaxwell]

Well you own data shows it is pretty much randomly distributed.  If birth dates were assigned by a psuedo-random number generator then it would have 8.515 bits of entropy and the FCC files show 8.513.  Pretty much random.

Yes, thats why I posted it. I was more entropy than I thought.

How?  Unless you contend that all those users also are born in the same city, have same father's last name, have same email address, and went to the same highschool, etc.  

You keep adding things.  In your first suggestion you said DOB plus email but maybe not email.    Fine, if you add enough stuff there you'll make the multiparty speedup ineffective.   This still does nothing against attacking individual users where all that data is completely known.

(Add too much and you also create vulnerabilities that they'll get the data wrong later.  E.g. If you ask for name I might give you 'greg maxwell' 'gmaxwell 'gregory maxwell' 'Gregory Maxwell' etc.  I recently had to go through some pain to get my access to a banking site fixed because I was unable to reproduce the answers they required for the special trapdoor questions— because all the options they had were inapplicable to me, I don't have a favorite sports team, or own a pet, etc.)

email address ( how the fuck does that happen)

Because a lot of users will get tired of the bullshit questions, or mistake them for personal-data-collection that might identify them to other people, and leave them blank or put a dot in them.

But:

Even with a billion users you would be lucky to get more than a handful of matches.  The point of salt isn't to be a secret it is to prevent pre-computational attacks, prevent collisions, and to prevent multiplier on work.

Right, so you're spending a lot of effort there on something which does nothing against a targeted attack.

Now drumroll... if you think the entropy of the salt is still too low you can supplement it by a wallet generated small random number with their dictionary words.  A 4 digit "pin" would provide another 13 bits and isn't difficult to remember.

So please don't tell me it IMPOSSIBLE.  

You have me there: Nothing is IMPOSSIBLE so long as you keep moving the target.    But if you're willing to go that far, why not go the whole way and take 128 bits of honest-to-god non-user-generated entropy and not need to have a silly argument of ever escalating measures and arm waving about my-strengthening-is-really-good-I-promise in order to convince people that it's secure,  while simultaneously armoring the system against the random idiots who is going to make their key "bitcoin bitcoin bitcoin bitcoin bitcoin 1234" and then make headlines when they get robbed.

memorization although it would require some research.

I have three different genuinely random 128 bit keys memorized with electrum style conversion to words. I'm not especially good at memorizing. ::shrugs::  "So please don't tell me it IMPOSSIBLE"  

Human factors can be minimized by using a system which doesn't rely on user making good judgements:
* Wallet provided high entropy passphrase via dictionary

You can stop at that one, it's what I suggested in my original message. If the basis of the wallet is known high entropy stuff with enough entropy to meet regular cryptographic standards (e.g. ~>=128 bits) then there is no need for further discussion.

Your contention initially was that a high security deterministic wallet w/o backups was impossible, flawed, and naively weak.  

Not exactly, my contention was the you kept describing 'deterministic' wallets as being based exclusively on a user provided pass-phrase. This kind of scheme is flawed and naively weak,— and moreover that it would be recognized as much by almost anyone who has spent much time thinking about or researching the subject— and I haven't moved an inch from that position.  Rather: You've moved from your position of pure user provided data to adding actual randomness, though not quite enough for me to actually declare your proposals secure, so sadly I can't join you in declaring victory.

If I created dispute simply by being unclear about my position, then I apologize.  I really wasn't trying to argue that there had to be a backup (though I think there should be)— and my original post explicitly mentioned the possibility of the user memorizing a decently sized machine generated random number after converting it to a friendly form.  My position was only that there needs to be enough actual entropy to get near 128 bits of security and that users will not provide even enough security to get by with strengthening (a fact you implicitly admit by suggesting the need of demographic "salt" to prevent collisions, but fail to acknowledge that the same weak passwords that lead to collisions are also a problem in targeted attacks where the salt doesn't help!).

[ThomasV]

I really hope the official client will also have the option of creating a deterministic wallet one day...

For now, you can simply wait for Armory, which should be officially released (alpha) next week.  It not only has deterministic wallets, but paper backup print option (see the screenshot on the thread).  Digital backups are great and all, but you never know if that USB key sitting in your safe will still work when you plug it in for the first time in a year... paper backups are forever!

It seems to me that deterministic wallets are somewhat fringe and every client is using a different, ad hoc algorithm.

How about using the same key generation algorithm that is already used in Electrum?
this would make your client compatible with it; a user could use the same seed in both clients