How much hashing power should one reasonably expect an attacker to have?

[Topazan]

I've still been thinking about brainwallets, and I wondered about this.

Basically, I'm thinking that I can use a relatively short memorable password of the correcthorsebatterystaple variety with a strong strengthening algorithm.  I know the tradition is to use recursive hashing, but I was thinking more like a random salt within a limited range.

Basically, I'd have an address, and my password.  In order to find the private key, I'd have to have an algorithm try, say, a million different salts until it finds a result that matches the private key.

What I want to know is whether or not a million is a good number.  I'd like to be able to access my coins from an average computer using cpu only in < 10 minutes while slowing down attackers as much as possible.

Would this work?  How many salts would I need?

[TangibleCryptography]

A random salt from a range with x values has the same computational requirements as a recursive hash with x rounds.

Even 100K is likely sufficient for your needs but modern CPU are much faster than you are thinking.  Throughput is in the millions of hashes per second.  If you are willing to wait minutes you could make the salt say a random 32 bit int.    Remember it will take you the same amount of time for every typo or misremembered passphrase too.

Still there really is no value of doing it this way over an recursive hash.  Given recursive hash functions like PBKDF2 are well researched and extensively used I would always go with that option over any type of "roll your own" cryptography.

[Topazan]

A random salt from a range with x values has the same computational requirements as a recursive hash with x rounds.

Even 100K is likely sufficient for your needs but modern CPU are much faster than you are thinking.  Throughput is in the millions of hashes per second.  If you are willing to wait minutes you could make the salt say a random 32 bit int.    Remember it will take you the same amount of time for every typo or misremembered passphrase too.

Still there really is no value of doing it this way over an recursive hash.  Given recursive hash functions like PBKDF2 are well researched and extensively used I would always go with that option over any type of "roll your own" cryptography.

Actually, wouldn't it have somewhat fewer computational requirements?

If x = 4, the recursive has has to go through 4 iterations.

However, the random cracker has a 1/4 chance of getting it the first time, 1/2 in the second or first one, and so on. 

Not that this is a good thing from a cryptographic point of view, but, you know.

Doesn't recursive hashing reduce entropy?  I assume difference is probably too small to matter, though.  I don't know, I guess I just like the idea of requiring some randomness to access the coins.  If I did it that way, I could have a lot of different addresses in my wallet all using the same key.  Of course, the same thing is possible just by adding more hashes for new addresses.

Thanks for the insight.

[TangibleCryptography]

cryptographically valid recursive hashes (like PBKDF2 or bcrypt) add the salt on each round which prevents the use of rainbow tables. 
SHA256(salt+SHA256(salt+SHA256(pass+salt)))

If you wanted to add some randomness I guess you could make the number of rounds random (or better the # of rounds is some static + random #).  If you really wanted it to take minutes you could define your address as PBKDF2 using 1 billion + 32 bit random number of rounds.  The need to also generate the public address and check it for a balance on each round would significantly slow the operation down.

[Topazan]

If I was going to do this, I would provide the correct address to the algorithm so it could be checked that way.  But yeah, you'd still need to generate the public address.

You've convinced me that recursive hashing is better, but one advantage of a random salt would be that new addresses could be generated quickly, without so much hashing.

Thanks again for the help.