Tell me more ×
Bitcoin Stack Exchange is a question and answer site for Bitcoin crypto-currency enthusiasts. It's 100% free, no registration required.
up vote 8 down vote favorite

MD5 used to be the hash algorithm. Everyone loved it, but now, not so much.

What will happen to bitcoin if flaws are found in SHA256 in the future?

share|improve this question

2 Answers

up vote 5 down vote accepted

I'm assuming you mean what will happen to Bitcoin if SHA256 is discovered to no longer be suitable for use as Bitcoin uses it. First, such a thing is likely to happen very gradually. We'll first see hints of weaknesses and attacks that currently take millions of years will shrink to thousands of years and then hundreds of years. So there will be plenty of time to arrange a change.

Note that Bitcoin addresses also use RIPEMD-160, which is likely weaker than SHA-256. However, the way they're used, weaknesses in RIPEMD-160 might not actually create problems for Bitcoin.

Basically, whatever changes needed to be made to the protocol would have to be worked out. Possibly any other changes deemed advantageous could be made at the same time, since protocol-breaking changes are rare. Some fields may need to be expanded.

A particular block would be picked, after which the new methods would start. Everyone would have to upgrade before then.

I think every effort would be made to keep the block header size the same so the mining algorithm didn't have to change. This may mean having to add an intermediate header. The intermediate header would contain the larger hashes of the previous block, transaction tree, and so on. The hash of the intermediate header would go in the block the miners try to mine, reducing its three hash fields to just one. (And allowing the nonce to be expanded to 64-bits! Yay!)

If addresses or transactions had to change, then after that chosen block, new-style transactions would be permitted. Coins not transferred to new-style accounts might become vulnerable to attack, in theory. Because Bitcoin transactions already have input and outputs that function in a logically independent way, there would be no problem with importing coins with an old-style address/signature and sending them to a new-style address.

share|improve this answer
Actually RIPEMD-160 makes the protocol weaker. It is true that due to implementation it is very hard to retrieve the hashed data, but collision attacks are made much easier. eprint.iacr.org/2004/199.pdf – Mascarpone Oct 6 '11 at 13:13
1  
The thing is, a collision attack on RIPEMD-160 won't do you any good. Finding some plaintext that hashes to the same RIPEMD-160 value as my public key won't let you claim my coins (or do any harm at all) because you would still need to find a private key that corresponds to that public key. (However, a collision attack on SHA-256 would be disastrous for Bitcoin. It would enable you to invalidate transactions.) – David Schwartz♦ Oct 6 '11 at 13:17
RIPEMD-160 could be the first block in an elaborate Bitcoin attack aimed at the network. What if a malicious attacker generates 2 key pairs with the same address? this could lead to double spending. It's a question worth to be analyzed. – Mascarpone Oct 6 '11 at 13:33
2  
It couldn't lead to double spending. It would just lead to two ways to spend the same coins. There is no known way an attack on RIPEMD-160 could lead to an attack on Bitcoin. (Which, of course, doesn't mean it's impossible, especially since it's unique and not well studied.) – David Schwartz♦ Oct 6 '11 at 13:37
1  
To be precise, you'd have to find a private key whose corresponding public key's SHA-256 hash itself hashes to the same RIPEMD-160 hash. While weaknesses in RIPEMD-160 could bear on this, the interaction with ECDSA and SHA256 would mean that you would need to show RIPEMD-160 to be very weak for this attack to work. For example, if Bitcoin used MD5 for this purpose instead of RIPEMD-160, it would be justifiably considered badly broken and in need of a fix ASAP, but no actual attack would be remotely close to practical. – David Schwartz♦ Oct 7 '11 at 1:27
show 2 more comments
up vote 0 down vote

Since SHA256 has been used for such a long time, it is reasonable secure from a cryptoanalysis attack.

It is still vulnerable from a brute force attack, even though it is still reasonably secure for at least the next X Years (where X > 10).

Anyhow this question was already posed and there are several candidates eligible for succession:

http://en.wikipedia.org/wiki/SHA-3

MD5 fell out of use because the computational capacity rose over the years, thus making cryptoanalysis easier and thus leading to the discovery of several flaws.

I would be more afraid of quantum calculators, which will make today hashing techniques useless.

share|improve this answer
1  
"Since X has been used for a such a long time, it is reasonably secure from a cryptanalysis attack." Ummm....are you at all familiar with the history of cryptography? Everything is considered secure until it isn't. – eMansipater Oct 6 '11 at 15:21
Can we say that, since SHA256 has been extensively analyzed, we can be reasonably secure that no trivial attack can greatly reduce the collision resistance? – Mascarpone Oct 6 '11 at 15:28
1  
One could argue that the probability of a trivial attack is reduced by the extensive analysis, but there are a lot of mathematical questions that were abruptly changed despite centuries of analysis. Without an answer to P v NP, a formal proof of difficulty, etc. this is all on relatively shaky ground. Most professional mathematicians will tell you that it's safer to bet on the eventual demise of a hash function than on its eternal success. – eMansipater Oct 6 '11 at 15:39
As a professional mathematician my humble opinion is that we can measure the security of an algorithm by its exposure, defining expousure as e = (users) * (days without a critical flaw). By this metric I say that we should be more worried about RIPEMD than SHA256. Taking the subject from a more broader pow, my first concern is quantum computing, that by dodging the turing axioms, could computationally crush Bitcoin, – Mascarpone Oct 6 '11 at 15:56
I wouldn't say SHA-256 is vulnerable to brute force. Hell 64bit hash isn't yet vulnerable to brute force. Total lobal computing power (in all forms) is roughly 6.4 million Petaflops. Say computing power increased by a factor of 1 billion overnight, and every computer worked 24/7/365 trying to break a single SHA-256 hash. Assumming global computing power grew at 30% annually rate it would take over 300 years to attempt even 1% of potential keys (still 99% chance of failure). – DeathAndTaxes Oct 6 '11 at 20:12
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.