The attacker would not search for the private keys alone, he would calculate the private/public key and their corresponding address for all passwords up to a certain length (depending on his capacity), and store them in a table. Then he would scan incoming blocks for transactions that send coins to addresses that match his table. This allows him to harvest transaction outputs sending coins to addresses based on private keys that are generated on weak passwords. With one such table he can attack everyone using this scheme in parallel.
If the key generation is based on both a password and something that is globally unique (such as an email address) the attacker will have to either calculate really really big tables (unfeasible) or make a targeted attack against a single user (provided that he knows his email address), yielding much less profit.
How much of a length do you have in mind? The deterministic generators in existence now and that are proposed require passphrases with a minimum of 20-30 characters... this guy's table would have to have something like 10^37 entries, and he would need in excess of the world's capacity in hard drives to store it.
The post I referenced originally mentioned 5 characters, which makes a rainbow attack trivial:
Consider these two possible wallet decisions:
1) using a 5-character password to create a Deterministic Wallet using some tool.
2) create a truly random private key and copy/paste it into a text file in an encrypted true crypt drive, that is protected with a 5-character password, that you back up in several locations online and offline.
In addition, calculating ECDSA public/private keys is already a very slow operation, he would probably need in excess of his lifetime to produce just 10^20 keypairs and the GDP of a small country just to pay for the electricity, let alone 10^37. This attack is effective against the fool who chooses "john's bitcoins" as his passphrase, but not against someone who uses a program that refuses to cooperate with a poor passphrase.
Creating a keypair is not computationally hard and can be implemented effectively and cheaply in hardware.
For long passwords the attack can be turned around by making a table of all addresses in use and continously guessing at passwords.
Although I agree that the linked wiki article discusses it and recommends the user enter a "salt"... what practical difference would there be between the user entering a "salt" into a separate field, versus simply appending some extra characters to their passphrase? They will be concatenated anyway, so none from what I can tell. Salt in most other contexts is not something chosen by a user, rather it is something added by an application outside the user's control.
They aren't really concatenated, but seperate inputs to scrypt, which generates the seed used for deriving keys. The idea with the salt is that it is easy to remember, unique, and not a secret. In practical terms it allows for stronger security without having the user remember/keep-secret a longer password. In a UI I would always keep this as two seperate fields, as this makes it easier for the user to understand that there is a secret component and a unique component of his wallet.
With deterministic wallets we cannot rely on a central component generating the salt. We need the salt to be the same whenever we wish to recreate the wallet.
I still don't get it. One component needs to be secret (but not unique) and the other needs to be unique (not secret)?
The whole point of a passphrase is to be both unique and secret. If they're both, and they're long enough (entropy wise) that's all that's needed.
We want normal people to use Bitcoin. Asking the average Joe to memorize a complex 30 character password is error prone and will surely result in many lost wallets. The whole point of the salt and scrypt is that you can do with a shorter password that is easier to remember.
We make a rainbow attack unfeasible by using a unique salt that is easy to remember instead of a very long password.
We can make a direct brute force attack against a single wallet (where the salt is known) unfeasible by making each brute force attempt computationally hard. Scrypt achieves this both for software and hardware implementations. So basically we can reduce the password length by requireing the user's software to spend CPU during initialization.
If we make sure that brute forcing the private key from password is computationally as hard as brute forcing the private key from a public key we have something that is as safe as the Bitcoin system.
This completely makes sense in the context of using scrypt on, say, a website where there's a database, and per-user salt is stored separately from the user's brain. If scrypt is the algorithm of choice, and the algorithm wants a salt, and the user has to remember it, why not just define the first n characters of the passphrase (or the hash of it) and call it the "salt", rather than burden the user with caring about the difference. By demanding that the user understand "salt" to use a payment system, the size of the potential audience willing to use the payment system just gets quartered or worse.
The UI will be simple. "Enter your password" "Enter your email address". The CPU demanding calculation is only done when you wish to create/re-create your wallet.
