Topic: wallet destruction (Read 2447 times)

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

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


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


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:


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


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.


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"  


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.


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

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.

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.


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.

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


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?

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.

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.


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.

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.



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.

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.

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.  


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.


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.


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)

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

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.

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.  

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.

128 bits isn't an absolute requirement, it's a comfortable rule of thumb.  You can arrive at basically this number by making conservative estimates about the energy requirements of brute force (e.g. assuming an optimal classical computer, incrementing a counter, requires about 240 million tons of tnt energy equivalent to increment from 0 to 2^128-1, which is clearly secure against whatever threat model or algorithmic speedups you wish to suppose)

This, plus the fact that 128 bits of security is almost always very cheap to have has resulted in the conventional wisdom that cryptosystems with less security than that are snake oil.    You can probably drop a couple bits and wave claims of strengthening at it and pass the smell test, but not much more than that.

The whole bitcoin system was designed to provide at least 128 bits of security for this reason.


Because most attackers will not have the encrypted wallet. Your security is passphrase PLUS wallet, which is an enormously higher standard than just passphrase. Belt and suspenders.  And what I'm describing for deterministic wallets is effectively the same:  Something you have (the random seed) and something you know (the passphrase).

Moreover, you can't actually measure entropy. You can make guesses based on assumed source models,  but you don't really know it unless you generated it.  Rejecting passwords by some simplistic model actually reduces entropy.


Whoa whoa whoa.  Full stop.  Salt?  Where does this 'salt' come from?  If you make the 'salt' at least 128 bits and store it you have _exactly_ what I've described.  And that's a fine thing: so long as there is enough entropy from strongly random sources to make blind attacks infeasible then its all good.  But you still have to record that salt someplace.
(and if you're strengthening you also need to store the strengthening amount, unless you always strengthen to the least common denominator)

It's pretty hard to reason about strengthening, because you can't generally prove that there isn't a way to shortcut it. In fact, if you assume quantum computation you get a minimum speedup of sqrt(n) for any possible strengthening scheme.  Strengthening has practical value and should be used whenever weak passwords might be used, but it's not a replacement for real entropy.
 

You're assuming that the passphrase has 40 bits of entropy, this is a fundamental error.  Multiple studies have shown that its basically impossible to get high entropy passphrases from humans, even if you give them excellent advice.  People on this forum have frequently bragged about their oh so secure schemes, which actually provide fairly little entropy.   This isn't because they're bad or stupid, or because they deserved to get robbed— being random is something that humans are just not good at.

(The 30 minutes assumption is insane too— almost all users would choose a less secure alternative over waiting 30 minutes—  but whatever, taking off a factor of 100 isn't what breaks your argument)

Moreover, even if the user is bad and stupid and deserves to get robbed— when they _do_ get robbed the reputation of the whole system is called into question. Responsible security conscious developers build systems which remain secure even in the face of user stupidity— ones which only fail in the face of unstoppable heroic stupidity whos stupidity would be obvious to even the most unsophisticated observers.

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

I guess I may need to prove it by making a private key based on key hardened passphrase consisting of 5 dictionary words, provide the salt, and the public address and say if it is so easy to crack my Bitcoins are yours.

Um salt doesn't need to be complex and it doesn't need to be a secret.

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

Hash those three values and that is your salt.

For wallet recreation simply ask the user those questions again and rehash to re generate the salt.

Unless you think there are enough people who have same birthdate, place of birth, and email address that also happen to use the same passphrase.

On second thought I don't like email address question because it could change.  Just find 3 or 4 highly deterministic questions to generate the salt like father's name, place of birth, etc.

So you are memorizing the salt in addition to your passphrase?

You wrote in your post that you don't need a recovery plan for your deterministic wallet, because it's all in your head.  If you've added salt, it's not really in your head. You will need a backup.

You are aware that problem was solved roughly 3 decades ago.... SALT

The issue is not breaking the passphrase.  It's that a purely-deterministic wallet without extra entropy will lead to many users, using keys that are identical, and then they'll end up sharing wallets -- which obviously will lead to one person taking the other person's money.  Then you'll have determined people creating wallets based on a common passphrases, and it will be very successful, because they will get to attack ALL such users at once.  They can just keep trying common passphrases until they find one that generates a wallet with money, then keep going.

That would be an utter disaster for Bitcoin.  There must be extra entropy added to ensure that no two users end up with the same deterministic chain of addresses.

Where is your analysis that 128 bits of entropy is required?
Also why is deterministic wallet held to higher standard than an encrypted wallet?
Why doesn't the mainline client then reject any passphrase without 128 bits of entropy.

Since wallet generation is relatively rare event, key hardening function like PBKDF2 can be used with quadrillions of rounds on an Open CL capable machine.  The seed generation function could be very slow taking 2, 5, hell even 30+ minutes since the event is rare unlike a website login which is dealing w/ thousands or millions of logins per day and thus must limit PBKDF2 execution time to a fraction of a second.  A long execution time combined with salt would make a passphrase with even 30 bits of entropy impossible to brute force.

Example of high security deterministic wallet:
passphrase w/ 40 bits of entropy (for example 5 randomly chosen words from dictionary)
SHA-256 key hardening w/ 20 billion rounds.
sequential throughput of wallet generation machine 10 MH/s
hashing power of attacker 1 TH

Wallet generation time: ~30 minutes
Attacker throughput @ 1 TH: a mere 50 passphrases per second (due to need for 20 billions hashes per attempted passphrase)
50% time to break 40 bit entropy passphrase @ 50 pps: 697 years