Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

The Bitcoin network use SHA256 as a core component to it's design. I'm no expert on cryptography, but it seems to me it usually is only a matter of time before security vulnerabilities are discovered (MD5 for example as well as many others).

What are the chances similar vulnerabilities are discovered in SHA256 at some stage, and how damaging would it be to the Bitcoin network?

share|improve this question
    
You might want to try shooting this to the IT Security Stack Exchange. They are pretty good at delving into questions like this. –  bethlakshmi Jun 9 '11 at 13:46
    
md5 is not encryption, it is a hashing algorithm. –  Chris Aug 21 '11 at 13:46
add comment

migrated from programmers.stackexchange.com Aug 21 '11 at 14:15

This question came from our site for professional programmers interested in conceptual questions about software development.

6 Answers

The only known way to ascertain the security of a cryptographic algorithm is to leave it under close scrutiny of hundreds of cryptographers for several years, and see what comes out. So the right perspective here is historical.

MD5 was published in 1992; it was actually designed the year before (1991). In 1993, first weaknesses were spotted, then bigger weaknesses in 1996 (collisions on the compression function, found by Dobbertin). It took 8 years for these weaknesses to be turned into actual collisions by Wang, in 2004. Seven years later, in 2011, we can create MD5 collisions at will (and much more efficiently than with Wang's original method), but preimage and second-preimage resistances of MD5 are still as good as ever.

From this we can infer that when weaknesses are found in hash function, they do not appear overnight: we have quite some time to react. Also, the first MD5 weaknesses were discovered only one year after its publication, and that was in the early 1990s when the public research in cryptography involved much fewer people than nowadays.

Let's see what this gives for SHA-256: first published in 2001; ten years later (2011), we still have no clue whatsoever on the slightest hint of a weakness. This would be suggestive that SHA-256 is indeed robust, and collisions for SHA-256 are not just right around the corner. Also, I have not looked in full details at the Bitcoin protocol, but it seems that collisions are not a real danger for Bitcoin -- it rather relies on preimage resistance, for which not only SHA-256 is rock solid, but even MD5 would still be reliable.

However, it is dangerous to make statistics on a single measure. In 2007, it was estimated that there was a relatively high risk that the attacks on MD5 could be transported to SHA-1 and then SHA-256/512 -- this prompted NIST to organize the SHA-3 competition. It turned out that attacks on SHA-1 have somehow stopped progressing, and there is no attack on SHA-2. Whether this is because SHA-2 is really robust, or because all the cryptographers are busy trying to break the SHA-3 candidates, is not known (but my opinion is the former: SHA-2 is a secure hash algorithm).

share|improve this answer
add comment

Vulnerabilities can happen at different levels here.

1) A theoretical attack may be discovered that reduces the complexity necessary for a successful attack, but not low enough to be practical. I.e. from a technical POV the algorithm is considered broken, but it is still safe for any practical use.

2) An attack is discovered that reduces the complexity down to a level that can be practically performed by a large distributed attack within feasible time. The algorithm may still be useful for specific purposes (e.g. MD5 to identify download errors of a file), but it is a No Go for anything requiring long term security, like digital signatures.

3) The algorithm is completely broken, anyone can do it on his home PC. Forget it and anything that uses it as a central component. The download verification may still be OK, but not much beyond that.

There are some fundamental laws that should be considered here. First, you can't prove that an algorithm is secure, you can only prove it's unsecure by actually cracking it. Second, attacks always get better, they never get worse. I.e. researched knowledge of previous attacks won't be forgotten.

For the chances, a discovery may be done tomorrow. Or in two years. Or in twenty years. SHA-1 is broken (http://en.wikipedia.org/wiki/SHA-1) and somewhere between 1 and 2, and SHA256 uses a similar basic structure. But yet no attacks are known against SHA256, AFAIK.

share|improve this answer
    
it should be noted that the phrase "SHA-1 is broken" has a very specific meaning in cryptography. it basically means that a collision attack has been discovered that is faster than a birthday attack. it does not mean that somebody could reverse a hash to get the original string. –  mulllhausen Feb 7 at 0:24
    
@mulllhausen Surely you mean to get a string which produces the same hash? As opposed to the "original" string. –  Jon Bentley Feb 14 at 1:07
add comment

It looks like the inner workings of Bitcoin is that it signs, using the ECDSA algorithm, the double applied (the first hash is hashed again) SHA256 hash of the transaction.

It is always just a matter of time before security vulnerabilities are found. But there tends to be more security vulnerabilities from a poor implementation of the best algorithm than from a good implementation of an acceptable algorithm.

Or, the worst of both worlds, a poor implementation of a poor algorithm. A SQL injection attack was used to get account details at the Mt. Gox Bitcoin exchange, where they were storing MD5 hashes of passwords in their database, including those of exchange administrators.

Which has absolutely nothing to do with the cryptographic security of SHA256, but was somewhat damaging to the Bitcoin network.

share|improve this answer
add comment

There are a couple things to understand.

The first is to understand the strength of a hashing algorithm. To replicate a hash, the level of difficulty is the full size of the hash key. Thus, if you already have an MD5 hash, and want to find a pattern that matches it, the difficult is a full 128 bits. But because of discovered problems, we might be able to do this with only 100 bits of difficulty. But, the max we can do is 60 bits of difficulty. So, cracking MD5 in the manner is still impossible with today's knowledge/hardware.

But there is a second concern for hash algorithms: that of creating two things that hash to a new value. It's a sort of meet-in-the-middle attack. It's half the number of bits of difficulty, so for a 128-bit algorithm, it's only 64-bits of difficulty. With known bugs in MD5, that difficulty becomes more like 50-bits, well within the ability of modern computers.

This meet-in-the-middle issue means that SHA-256 has only 128-bits of difficulty. What that means for Bitcoins is to create two transactions that hash to the same value.

Like MD5, we won't break it all at once. Instead, people will shave off a few bits of difficulty at a time, just like how they recently shaved off 2 bits of difficulty for AES. Thus, it'll go from 128-bits of difficulty, to 125, to 120, to 115, and so on.

With Moore's Law adding a bit of cracking power (60-bits today, 61-bits next year, 62-bits the year after), and SHA-256 losing a bit of meet-in-the-middle strength every year, that means we have about 30 years left before it becomes practical to forge Bitcoin transactions.

Bitcoin does do some things to make that harder, but probably in the next 30 years, somebody will figure out a way around those issues. Thus, I'd casually guess Bitcoins have a 30 year lifespan.

That's more than the currency for many mismanaged countries.

share|improve this answer
add comment

The time can maybe be guessed vaguely based on how long other widely used algorithms survived before being found flawed, but that of course doesn't actually mean you can make useful predictions.

An intelligent solution that a friend of mine explained for a large project was to simply use two hashing algorithms in parallel (I.e., each file had two hashes associated with it), then exchange one if it's broken. The chance of two algorithms being broken around the same time, and that the combination of the two is also breakable, is probably 10^lots^lots smaller than the chance that any given single algorithm will ever be broken, and as a bonus you have some time to take care of the transition to a new hash when one of them is broken.

share|improve this answer
    
As always, a bad implementation of this could mean breaking one hash achieves the goal, reducing the security. An example is password lock on android: forensics.spreitzenbarth.de/2012/02/28/… . I've also seen somewhere md5(sha1(x)) would reduce the complexity to the weakest function, but I don't know enough details to be able to claim or explain that. –  domen Sep 16 '13 at 12:39
    
@domen Clarified - They didn't nest algorithms, but rather created two hashes per file. –  l0b0 Sep 18 '13 at 8:28
    
I didn't have what you described in mind, just a generic comment. Note how this scheme is very good for file hashes, but for passwords it would make it easier to break. –  domen Sep 18 '13 at 8:59
add comment

MD5 is 128 bits hash value whereas SHA256 is 256 bits. So the possibility of a so called collision is lot smaller for SHA256 as compared to MD5.

Also MD5 is an old veteran had been around from the 90's i presume while SHA256 is about a decade old and it would need some awesome computing to get a collision. But in case it does happen then it would be a gradual one and i believe there would be some time (SHA-3 would be out by then) and they (BitCoin) could then migrate but then that is a mammoth task on its own and there are other people with the expertise to analyze that part (i don't fit in there at all)

Still a long time for such a compromise on SHA256 i think.

share|improve this answer
add comment

Your Answer

 
discard

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