Bitcoin Forum

If i was a bad guy, and saw that it is almost impossible to steal bitcoin,
I would try to destroy other people's bitcoin

by erasing wallets or uninstalling or whatever.

There will be some people that will not make backups of their wallets.

question is :
are those encrypted wallets too big to be written into a block chain ?
Someone attacked would know approximately when he created his wallet
or would have some other reference
to restore that wallet.

Customized tool would scoop wallets in chosen period of time,
and try user provided password on those wallets...
since sending will require 2 passwords soon, coins would not be stolen,
but wallets could be restored

and maybe wallets could be written into namecoins block chain,
since there is merged mining, to let namecoin return the favor...

Or is it possible to store in block chain only some kind of "seed" of a wallet
to reduce storage size ?

Copy the wallet.dat to yourself, steal coins available and then erase original wallet.dat from target machine for lulz. Or copy the wallet.dat file, wait when lamer recieves more coins in the wallet and then steal the coins. Some users will send more coins to compromised wallet even after the coins are stolen :D

Just use a deterministic wallet.  If you have the passphrase you can rebuild the wallet.  Period.

What could be better than that.  Anything stored in block chain "seed" or not would obviously need to be encrypted thus you still need a passphrase.

Not sure what storing an encrypted wallet in the blockchain would gain you over simply using a wallet where your passphrase IS your wallet.

tell it to my grandma :)


It would allow people to act irresponsible (as usual), without being punished for it.

Most of the people is mentally stuck in 7th grade, basically kids with mustache or boobs...
they often do not have due attention

on install, encrypted one is created (with 2 factor authentication)
only one of those passwords will be used to recover the wallet from the blockchain
other password would enable spending

and this is protection from destruction, not from (both) passwords being sniffied

No one will lose a wallet without a backup twice.

And my hat is off to anyone that can find my long term storage wallet burned to several M*Disc DVDs and erase them all.

You should sit down and do the math — the value to you in destroy other people's bitcoin is very small unless you happen to own most of the bitcoin, far less value than stealing it.  In fact the attacker is best off living that potential victim alone, because his bitcoins will be worth more if people are not afraid to use bitcoin due to the attacks.


Attempts to destroy your bitcoin can also be foiled with a simple offline backup— a $2 usb key or two is cheap insurance. You're a fool if you don't have an offline backup because dataloss happens even when there are no attackers.

'Backing up' to the blockchain is a horrific idea. It would provide no security (what is the point of 'secret' data which is known to everyone) over just using the password alone— and using a password alone is itself a terrible idea because people are bad at producing strong passwords even when they are trying, it would burden the bitcoin network and prematurely degrade our decenteralization.

I am just saying that someone could lose it once

that would bring bad publicity, slower adoption...
uncomfortable and risky use turns people away

and if motivation is political or psychotic ?
simply to destroy or disrupt



I suggest writing it somewhere automatically,
block chain is a suggestion because it is always there, unlike USB stick

in near future 2 passwords will be required to send/steal coins
so if there is encrypted wallet online, it could be brute forced once,
but that would not be enough, if it requires confirmation via SMS or some other method to send coins

thief could find all wallets and look at balances, but not steal
if they require additional confirmation

I would a deterministic wallet is even EASIER to use than one that requires backups (automatic or not).


You still haven't explained why one is easier than the other:

ENCRYPTED WALLET
1. You create wallet.
2. You backup wallet
3. If wallet is lost you need to use passphrase AND redownload wallet (which may be difficult or confusing for user)

I would also point out if user's passphrase is weak having them in the block chain allows attacks remotely.  The user's machine doesn't need to be compromised an attack can simply brute force all backed up wallets hoping for a hit.

DETERMINISTIC WALLET
1. To create a wallet you ... enter a passphrase.
2. To access wallet you ... enter same passphrase.
3. To restore a corrupted/deleted/stolen wallet you ... enter same passphrase.

So I will ask again what exactly does backing up an encrypted wallet into block chain accomplish that a deterministic wallet doesn't?

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

Doesn't sound like the devs want to go that direction yet, though I have seen Gavin mention that it's the right direction to go.... eventually...

For now, you can simply wait for Armory (https://bitcointalk.org/index.php?topic=56424), 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!

You should take care to not describe a deterministic wallet as requiring no backup at all, ever.  I'm completely confident that the official client will _never_ implement a deterministic wallet that has no known-random component. Moreover, you should not use any client which implements such a thing because its developers obviously have a poor grasp on security.

Instead, what you would have is a deterministic wallet with a random component with at least 128 bits of real entropy. Perhaps it can convert it into a special list of words that you can memorize if you really want (e.g. electrum does this) plus whatever pass-phrase you use,  you'd backup this random data _once_.  Then you don't have to back it up anymore.  (it's, in fact, arguably better to actually leave the password out of the generation and only use it to decrypt the stored seed— so that its possible for you to change the password if you worry that someone might have seen you type it in)

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

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.

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

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.

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.

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.

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.

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.

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.  

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

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 (http://www.cs.utexas.edu/~shmat/shmat_ccs05pwd.pdf), 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)

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.

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

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

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.

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.

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

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