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?
Add a comment
|
3 Answers
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.
answered Oct 6, 2011 at 12:59
-
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 Commented Oct 6, 2011 at 13:13
-
1The 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.) Commented Oct 6, 2011 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. Commented Oct 6, 2011 at 13:33
-
2It 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.) Commented Oct 6, 2011 at 13:37
-
1To 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. Commented Oct 7, 2011 at 1:27
All in theory: Moore's Law will compromise all proof of work algorithms as newer mining equipment becomes affordable to fewer and fewer miners. Eventually one miner will have 51% control and it doesn't need to be quantum.
However quantum would be a definitive answer to your question because Moore's Law is steadily approaching its limit for conventional CPU chips.
A functional 10000 qubit quantum computer can run Shor’s and Grover's algorithm: Applying different approaches with Shor’s and Grover's to associate private and public keys could break ECDSA 256.
The first 10000 qubit quantum computer could assert 51% control over any blockchain it targets.
If Bitcoin is still around like it is, a fork would happen to bb84, but before someone would almost certainly attack the blockchain at will if they could.
Quantum computers in 2019 by top qubit count:
- Google's Bristlecone: 72-qubit gate-based
- IBM's 50-qubit
- Intel: 49-qubit-Test-Chip
How long will it take to get to 10000 qubits? No one knows exactly.
-
Shor’s algorithm is for factoring. It has nothing to do with SHA256 Commented May 27, 2019 at 1:27
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.
-
2"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. Commented Oct 6, 2011 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? Commented Oct 6, 2011 at 15:28
-
2One 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. Commented Oct 6, 2011 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, Commented Oct 6, 2011 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). Commented Oct 6, 2011 at 20:12