Then one day, some highly motivated attacker will come along and discover the other very interesting property: that the work needed to attack Bitcoin scales linearly with the work needed to use Bitcoin. As soon as a successful attack is announced publicly, faith in Bitcoin will be shaken to badly that nobody will ever want to use anything called "digital cash" for a long time.
So the real question you should be asking is, "Who would benefit from a Bitcoin failure, and could they amass that much computing power?"
It seems like the biggest risk would be with the wallet websites, which is an issue that is present in other payment methods.
The biggest problem IMO is that there is no way to refund or right the wrongs done by an attack. If someone in russia or china steals half of the bitcoins, there is nothing anyone can do to get them back. I suppose they would all be logged and everyone could band together to block those BitCoins as payments, but that's probably not going to happen. That would be interest to watch play out.
I think betterunix is not talking about a crypto flaw but a 51% attack; for ~$20M you can buy enough ASICs to basically take control of Bitcoin. (I'm not convinced that mathematical concepts like "polynomial time" should be applied without consideration for economics, but that's a whole different topic.)
"Supposedly they can easily change algorithms if SHA-256 is broken in the future."
You are not understanding the problem. Bitcoin is not a hash function, nor is Bitcoin a digital signature system. Bitcoin is a digital cash system, and so any discussion of Bitcoin's security must be based on the notion of security in a digital cash system.
There are two minimum security properties a digital cash system should have (informally): first, that the units of value cannot be counterfeited; second, that each unit of value can be spend by exactly one party at any given time. In both cases, it is commonly assumed that the attacker's work is bounded by some polynomial in the parameters of the system itself, so the system is secure if no polynomial time algorithm can break either property (but an exponential time algorithm might e.g. a brute-force approach). It is possible (and usually desirable) to prove that a system is secure using mathematical arguments, for example these systems:
(Sorry that these are paywalled, you can probably find them elsewhere)
Unfortunately for Bitcoin, while it seems to satisfy the first property (but no security proof is out there as far as I know), it fails the second property. Double spending in Bitcoin requires work that scales linearly with the parameters of the system (the "51% attack"), which is basically worthless as far as cryptography is concerned. The fact that Bitcoin uses a secure hash function and a secure signature system is irrelevant because the problem is with the protocol itself.
An easy way to illustrate the difference between using a secure cryptosystem and being a secure cryptosystem is the "surreptitious forwarding" problem. Suppose you receive a message from your boss that was signed with his secret key then encrypted with your public key which said, "You're fired!" Now what you might do is to re-encrypt the signed message with another person's key and send that to them; they would now believe that they were being fired. It is not the encryption system or the signature system that you attacked, it was the fact that composing signing with encryption in that manner does not prevent such forwarding (but there are ways to do that). Bitcoin has a similar problem.
> As soon as a successful attack is announced publicly, faith in Bitcoin will be shaken to badly that nobody will ever want to use anything called "digital cash" for a long time.
It's worth noting that a 51% attack would only allow double-spending, and it's not something that could be realistically hidden; it would be very obvious what was happening. In addition, the amount of computing power available to the bitcoin network is becoming significant enough that it would be hard to exceed, even with a botnet.
It's also worth pointing out that people still use Paypal, despite all the stories of frozen accounts and people never getting their money back. People also still use credit cards, despite not every instance of fraud resulting in the victims getting their money back.
"In addition, the amount of computing power available to the bitcoin network is becoming significant enough that it would be hard to exceed, even with a botnet."
I agree that people may very well use Bitcoin despite a successful attack (plenty of people still use Hushmail), although I think a lot of confidence would be lost. Bitcoin has a lot of hurdles to overcome as it is, and the detection or announcement of a successful attack would add yet another.
A 51% attack is a possibility, and might be currently possible with the largest botnets known to exist today, but it would be pushing it. In future it becomes even more difficult.
That is exactly the sort of argument the Germans made: that Enigma had known cryptographic flaws, but that they did not think anyone would actually expend the effort needed to attack it. You are saying that Bitcoin has a known flaw, but that nobody is going to amass the computing power needed to exploit that flaw. That is a bad way to approach security.
It is not just about botnets (CPU "mining" is pretty slow); what do you think stops someone from spending their money on enough ASICs to pull off the attack? It is not all that expensive, maybe tens of millions of dollars in chips. Even if it were hundreds of millions of dollars, if Bitcoin were as threatening to the financial system as some people seem to think it is, that would not be a lot to spend on attacking it.
It is also important to recognize that the existence of an obvious polynomial time attack does not in any way rule out the existence of faster attacks, it only establishes an upper bound on the attack effort. The reason proofs of security in modern cryptography involve a reduction to an (assumed) infeasible problem is that it rules out all practical attacks (in fact, all theoretically feasible attacks).
It would be nice if there were a way of solving the double-spending problem that would make all attacks infeasible. But since there isn't, we need to make do with the options we have: to place trust in either a pre-chosen authority, or a defined majority we assume to be trustworthy.
Not all the tools we have for maintaining security are as good as public key encryption or symmetric encryption. In the world of bricks and mortar, $10 million buys you a lot of criminal clout. Is a safe deposit box safe against a determined attacker with that budget? Are all employees immune to million dollar bribes?
The law attempts to redress imbalances by making it difficult to get away with circumventing security to perpetrate financial crimes. The problem is not so much stealing from a bank, but getting away with it after the fact. The same problem applies to bitcoin if you want to execute a 51% attack; double-spending is financial fraud, after all.
Buying up $10 million worth of ASICs is relatively straightforward, but doing so in a way that can't be traced back to you is substantially more difficult. As well as the problem of trying to run that amount of hardware in secret, without a paper-trail, you'll also have problems in trying to convert any profits you make from the scheme back into fiat currency.
If one merely wanted to demonstrate the attack without profitting from it, then one could double-spend a small amount between accounts you own, in the same way that one could demonstrate an attack on a safe by buying one and then drilling into it. But that doesn't change the fact that there's a big difference between circumventing security, and illegally profitting from it without consequences.
So the real question you should be asking is, "Who would benefit from a Bitcoin failure, and could they amass that much computing power?"