I wonder if it ever becomes viable to try to brute-force the private key of such a valuable address, rather than devoting the brute force power to mining.
That's the entire point of asymmetric crypto, the amount of effort you would need to brute force 2^160 keys is staggering. Even if you made billions of ASIC processors and ran them until the end of time, you probably wouldn't find the funds you were looking for.
This is constantly suggested, and it's always useless. If you could attack keys like this the system would be broken.
It's important to note that asymmetric crypto behaves somewhat differently. RSA is a particularly notable example of this: a 160-bit RSA key is almost trivial to break, 512-bit keys are possible, and there are good reasons to think that large organizations with lots of cash and motivation are able to break individual 1024-bit keys when they want to.
The ECDSA keys used in Bitcoin are much stronger than RSA keys at the same size, and they seem quite safe, but don't make the mistake of looking at the time needed to brute force e.g. a 128-bit AES key and assume that applies to asymmetric algorithms too.
No. What the GP is quoting is "security bits" a measure explicitly designed to mitigate that difference. Bitcoin addresses have 160 bits of security, 128 bits if the public key is known. This is directly comparable to symmetric key sizes.
However, in cases where the private key is generated from a hash of a passphrase, like brainwallets, then it is far more feasible. There are people running bruteforcers constantly looking for private keys corresponding to brainwallet passphrases; that's their form of "mining".
To test it, if you make a brainwallet with a password of "password" and then send 0.01 BTC into your account, you'll see it vanish in a few minutes (or a few seconds).
Brainwallet inputs -> public keys are deterministic. It's true that the method of creating the key pair is as much of a password as the password, it's easy to select the most common methods (sha-256 hashes, bitaddress.org's method, etc.)
I cracked thousands of passwords for the https://keybase.io/warp competition (I lost by a few minutes... the answer to the top one is Je).
Once you have those public, private key pairs you can simply make an index of them and watch the blockchain for any of them to show up.
I've also noticed quite a few people who've posted threads on bitcointalk after having fallen victim to one of these brainwallet crackers. It really boggles the mind why someone would entrust significant amounts of money to an incredibly weak passphrase.
I don't think so. Brainwallets are generated as a hash. So if the input is secure, the output is secure. It's not possible to generate the input from the output. And frankly the connection between password -> private key and private key -> public key is very similar in brainwallets. To crack a brainwallet, given only the public key and sufficient bits in the password, is actually harder than directly attacking the private key.
Plus you have to balance "my own fuckup" risk against "someone attacked me" risk, right. Wallets depend on your backup habits, and you backup provider's security. Going through the fora, I'd say "oops. I lot my wallet.dat" is a much more serious threat to your bitcoins, on average, than someone got a hold of your password. Both of those, for most people (including me) are ... lacking. Brainwallets depend on my memory for passwords. A hardware brainwallet would guarantee you're 100% not exposed.
As for ECSDA attacks. It's true that the algorithm itself is near-unhackable. However, make one single transaction on a computer which chooses a non-random k value, and you're exposed. So the risks don't end just because
This is a 2007 study on web password habits. In it, they reveal the fact that fewer than 1% of passwords have bitstrength >= 90 bits: http://i.imgur.com/8vSrx2E.png
Achieving 128 bits of protection with a user selectable and memorable password is statistically unlikely (to put it mildly).
The fact that a brainwallet password is memorable means a computer can bruteforce it in far fewer operations, too. I.e. the bitstrength is mostly meaningless. Just ask the guy who runs http://www.cloudcracker.com
A memorable user-selectable password is incredibly unlikely to be as strong as 128 random bits.
Brainwallets shouldn't be casually recommended without appropriate warnings, but they certainly can be secure.
Passphrases aren't limited by length, and your brainwallet can be derived from your memory and publicly available information, so you can construct very strong memorable passphrases, e.x. the 3rd sentence of the 8th chapter of your favorite book concatenated with a moderately strong but memorable password.
Key stretching with PBKDF or scrypt helps a lot as well. Do you care if it takes 1 minute to compute your keys from the passphrase? Probably not, and it will make cracking much more difficult.
You missed my point. You can't attack the cryptographic function or the keyspace, but you can attack the original passphrase that is hashed, via typical hash cracking methods (rainbow tables, bruteforcing, dictionary attacks, etc.). All you need to know is the hash function; most brainwallets use a single round of SHA256.
Given it got broken up into 4000BTC chunks after the box TX, we can assume they are on paper wallets, probably distributed up using secret sharing. That's standard in the Bitcoin world.
That's the cool thing about Bitcoin. You can create a wallet on a completely offline computer or even a virtual computer, save the address and the private key, and send the money to it.
You only need the internet connection to do something with the coins.
Edit: got curious and found an answer: http://bitcoin.stackexchange.com/questions/2847/how-long-wou...
If I understand correctly, it's still not viable even if you tried your brute-forced keys on all addresses in the network.