SHA-2* family maybe broken in several years.

[drawingthesun]

According to http://valerieaurora.org/hash.html, weaknesses in SHA-2* have already been discovered. I know nothing about how these really work and know nothing about the weaknesses. However do we have a plan to migrate to another POW in a event the hashing algorithm is broken?

Or is the plan to pretend that SHA-2* will stand for all time unlike any crypto ever, and watch Bitcoin be destroyed?

[solex]

Depends upon whether you trust Satoshi's judgement. According to that site the SHA-2 family went "orange" before Bitcoin went live. Satoshi would have been aware of the 2007 paper mentioned which is the only thing vaguely justifying an orange alert.

I am not an expert, but from what I have read about SHA-2 it is very robust and would require a Fields Medal winning breakthrough in mathematics to scratch it.

[drawingthesun]

SHA-256 is very strong.  It's not like the incremental step from MD5 to SHA1.  It can last several decades unless there's some massive breakthrough attack.

If SHA-256 became completely broken, I think we could come to some agreement about what the honest block chain was before the trouble started, lock that in and continue from there with a new hash function.

If the hash breakdown came gradually, we could transition to a new hash in an orderly way.  The software would be programmed to start using a new hash after a certain block number.  Everyone would have to upgrade by that time.  The software could save the new hash of all the old blocks to make sure a different block with the same old hash can't be used.

This is good to know, I just hope the devs have a new hash in mind if we have to switch quickly.

[drawingthesun]

Depends upon whether you trust Satoshi's judgement. According to that site the SHA-2 family went "orange" before Bitcoin went live. Satoshi would have been aware of the 2007 paper mentioned which is the only thing vaguely justifying an orange alert.

I am not an expert, but from what I have read about SHA-2 it is very robust and would require a Fields Medal winning breakthrough in mathematics to scratch it.

Yeah I see what you mean. I just hope a backup is ready to commit into the source if a weakness is discovered.

[kjj]

Just FYI, there are many, many threads on this topic.

In the event of a really catastrophic break in SHA2, which is pretty much unimaginable, we can switch to SHA3, or whatever.  It doesn't really matter which one, and things change, so there isn't much point picking it now.

Why do I say it would be unimaginable?  Because if we used MD5 instead of SHA2, we'd be fine, even though MD5 is "broken".  None of the weaknesses in MD5 (or any other relatively modern cryptographic hashes) apply in the bitcoin world.  First, everything is always double hashed.  Second, everything has other constraints.

[piotr_n]

There is a huge difference between "weakness" and "broken".
In general: weakness does not mean shit - at least in this specific case.
Even if it is weak - very very weak, you still need to calc it, which still takes you some time that is bigger than 0, which is the only point that matters.

[yayayo]

Just FYI, there are many, many threads on this topic.

In the event of a really catastrophic break in SHA2, which is pretty much unimaginable, we can switch to SHA3, or whatever.  It doesn't really matter which one, and things change, so there isn't much point picking it now.

Why do I say it would be unimaginable?  Because if we used MD5 instead of SHA2, we'd be fine, even though MD5 is "broken".  None of the weaknesses in MD5 (or any other relatively modern cryptographic hashes) apply in the bitcoin world.  First, everything is always double hashed.  Second, everything has other constraints.

Well, this may be true - for now. However the more valuable Bitcoin gets the higher the motivation to hack parts of the software.


ya.ya.yo!

[kjj]

Just FYI, there are many, many threads on this topic.

In the event of a really catastrophic break in SHA2, which is pretty much unimaginable, we can switch to SHA3, or whatever.  It doesn't really matter which one, and things change, so there isn't much point picking it now.

Why do I say it would be unimaginable?  Because if we used MD5 instead of SHA2, we'd be fine, even though MD5 is "broken".  None of the weaknesses in MD5 (or any other relatively modern cryptographic hashes) apply in the bitcoin world.  First, everything is always double hashed.  Second, everything has other constraints.

Well, this may be true - for now. However the more valuable Bitcoin gets the higher the motivation to hack parts of the software.

I strongly recommend that you go read up on hash breaks to see why the two things I listed are more important than value.

But while we are talking about value, cryptographic hashes already protect a large fraction of global electronic commerce.  This is pretty much bitcoin's target market, so bitcoin is unlikely to become much more valuable than that.

[phzi]

Okay, that page is kinda interesting, but their classification of SHA-2 as "Serious weakness discovered" is rediculous.  I would say that in the worst case SHA-2 is in the "Minor weakness discovered" catagory.  Even then, look at the 2007 note they use for why SHA-2 was marked as weak: "In 2007, the NIST launched the SHA-3 competition because "Although there is no specific reason to believe that a practical attack on any of the SHA-2 family of hash functions is imminent, a successful collision attack on an algorithm in the SHA-2 family could have catastrophic effects for digital signatures." One year later the first strength reduction was published."

The strength reduction is barely significant from a computational point of view.  You can still compare the complexity of the attack to the number of protons in the universe...  And no full-round collision has been found years 6 years later. 

A bit of background on what is means to break a hashing algorithm:

A secure hash algorithm depends on its ability to produce a unique hash for any specific set of data.  A collision occurs where the same hash value is computed from for two different sets of data. Collisions do not represent breaks in an algorithm, but may possibly expose a weakness.  When collisions are known, an attacker may be able to, for example, alter data without changing the resultant hash.  A strong hash function is one that is resistant to such computational attacks. A weak hash function is one where a computational approach to producing collisions is believed to be possible. A broken hash function is one where there is a known way to reliably compute collisions.

Other academic weaknesses are common in hashing algorithms.  These weaknesses often propose methods of slightly shortening an all-out bruteforce attack on the alrogithm.  Current, meet-in-the-middle preimage attacks exist against SHA-2 - these show that the first x number of steps can be preimaged, and reduce the work required to compute a hash.  The best attack so far reduces SHA-256 to 42 steps (about 66% of the total 64 steps), but requires significant memory and disk resources to achieve this minimal reduction. (attacks reference: http://eprint.iacr.org/2009/477.pdf http://eprint.iacr.org/2009/479.pdf) IMO, so far, no publication about SHA-2 has shown anything that would cause real worry about the algorithm's security for bitcoin's purposes.

None of this really matters to bitcoin's use of SHA-256 for Proof of Work.  Unless SHA-2 is completely broken with a way to reliably generate data with a given hash, any further weaknesses are unlikely to affect it's usefulness for PoW.  Future vulerabilities may make SHA-2 based hashing algorithms a poor choise for password hashing and data signing, but are unlikely to break it in a way that damages its effectiveness as bitcoin uses the algorithm.

If the day comes where we see an effective attack against SHA-256 that affects bitcoin, the community will likely fork the blockchain and switch to another hash algorithm.  Any damange to the blockchain can just be reverted by resuming the chain from a previous checkpoint with a new hashing algorithm.  [If that needs to happen, however, all ASIC devices would become useless...]

[drawingthesun]

Okay, that page is kinda interesting, but their classification of SHA-2 as "Serious weakness discovered" is rediculous.  I would say that in the worst case SHA-2 is in the "Minor weakness discovered" catagory.  Even then, look at the 2007 note they use for why SHA-2 was marked as weak: "In 2007, the NIST launched the SHA-3 competition because "Although there is no specific reason to believe that a practical attack on any of the SHA-2 family of hash functions is imminent, a successful collision attack on an algorithm in the SHA-2 family could have catastrophic effects for digital signatures." One year later the first strength reduction was published."

The strength reduction is barely significant from a computational point of view.  You can still compare the complexity of the attack to the number of protons in the universe...  And no full-round collision has been found years 6 years later. 

A bit of background on what is means to break a hashing algorithm:

A secure hash algorithm depends on its ability to produce a unique hash for any specific set of data.  A collision occurs where the same hash value is computed from for two different sets of data. Collisions do not represent breaks in an algorithm, but may possibly expose a weakness.  When collisions are known, an attacker may be able to, for example, alter data without changing the resultant hash.  A strong hash function is one that is resistant to such computational attacks. A weak hash function is one where a computational approach to producing collisions is believed to be possible. A broken hash function is one where there is a known way to reliably compute collisions.

Other academic weaknesses are common in hashing algorithms.  These weaknesses often propose methods of slightly shortening an all-out bruteforce attack on the alrogithm.  Current, meet-in-the-middle preimage attacks exist against SHA-2 - these show that the first x number of steps can be preimaged, and reduce the work required to compute a hash.  The best attack so far reduces SHA-256 to 42 steps (about 66% of the total 64 steps), but requires significant memory and disk resources to achieve this minimal reduction. (attacks reference: http://eprint.iacr.org/2009/477.pdf http://eprint.iacr.org/2009/479.pdf) IMO, so far, no publication about SHA-2 has shown anything that would cause real worry about the algorithm's security for bitcoin's purposes.

None of this really matters to bitcoin's use of SHA-256 for Proof of Work.  Unless SHA-2 is completely broken with a way to reliably generate data with a given hash, any further weaknesses are unlikely to affect it's usefulness for PoW.  Future vulerabilities may make SHA-2 based hashing algorithms a poor choise for password hashing and data signing, but are unlikely to break it in a way that damages its effectiveness as bitcoin uses the algorithm.

If the day comes where we see an effective attack against SHA-256 that affects bitcoin, the community will likely fork the blockchain and switch to another hash algorithm.  Any damange to the blockchain can just be reverted by resuming the chain from a previous checkpoint with a new hashing algorithm.  [If that needs to happen, however, all ASIC devices would become useless...]

Thanks for your reply, in fact in cleared a lot of things up for me.

However just a note about your last paragraph:

If the day comes where we see an effective attack against SHA-256 that affects bitcoin, the community will likely fork the blockchain and switch to another hash algorithm.  Any damange to the blockchain can just be reverted by resuming the chain from a previous checkpoint with a new hashing algorithm.  [If that needs to happen, however, all ASIC devices would become useless...]

This is a problem because of large alternative crypto-coin GPU farms, if we have to eventually switch to another hashing algorithm for proof of work we run the risk of all the GPU miners launching a 51% attack on Bitcoin and taking the chance to finally destroy it. In Bitcoins moment of weakness it could be tarnished to the point that all confidence is lost forever.

[DeathAndTaxes]

The site has a lot of factual errors.  SHA-2 has not been weakened.  Reduced round version of SHA-2 have been weakened, which at this point means absolutely nothing unless Bitcoin used a modified reduced round version of SHA-2.

At the current time only SHA-2 not SHA-3 is approved by NIST for use on classified (SECRET & TOP SECRET) systems.  At this point there is no known attack vector against SHA-2 which is why the algorithm chosen for SHA-3 is radically different.  Today SHA-3 is merely an insurance policy.

[DeathAndTaxes]

Other academic weaknesses are common in hashing algorithms.  These weaknesses often propose methods of slightly shortening an all-out bruteforce attack on the alrogithm.  Current, meet-in-the-middle preimage attacks exist against SHA-2 - these show that the first x number of steps can be preimaged, and reduce the work required to compute a hash.  The best attack so far reduces SHA-256 to 42 steps (about 66% of the total 64 steps), but requires significant memory and disk resources to achieve this minimal reduction. (attacks reference: http://eprint.iacr.org/2009/477.pdf http://eprint.iacr.org/2009/479.pdf) IMO, so far, no publication about SHA-2 has shown anything that would cause real worry about the algorithm's security for bitcoin's purposes.

None of this really matters to bitcoin's use of SHA-256 for Proof of Work.  Unless SHA-2 is completely broken with a way to reliably generate data with a given hash, any further weaknesses are unlikely to affect it's usefulness for PoW.  Future vulerabilities may make SHA-2 based hashing algorithms a poor choise for password hashing and data signing, but are unlikely to break it in a way that damages its effectiveness as bitcoin uses the algorithm.

This is technically incorrect.

The 256 bit version of SHA-2 uses 64 rounds of operations.

The "weakness" cited above only applies to a non-exist "version" of SHA-2 which uses 42 rounds.  It takes 2^251 operations to achieve a pre-image collision as opposed to 2^256 by brute force.

Two things are important to note
1) This only applies IF SHA-2 uses 42 rounds (which it doesn't it uses 64 rounds for 256 bit version and 80 rounds for 512 bit version)
2) Even so it requires 2^251 operations (vs 2^256) which makes it 32x as efficient as brute force attack.
3) Merely counting to 2^266 requires many billions times more energy than is available in the lifespan of our star.  This attack vector at best reduces the energy requirements to many tens of millions times more energy than is available in the lifespan of our star.

I agree with you the site mislabels SHA-2 however it isn't even a "minor weakness" at this point it is more like "an academical curiosity which doesn't apply to the real SHA-2 and even if it did would require more energy than what is available to the human race to complete an attack" category. 

[kjj]

I agree with you the site mislabels SHA-2 however it isn't even a "minor weakness" at this point it is more like "an academical curiosity which doesn't apply to the real SHA-2 and even if it did would require more energy than what is available to the human race to complete an attack" category.

The chart is correct, it just doesn't apply to us.

Read the preamble.  He is concerned with compare-by-hash, as it applies to identifiers for arbitrary data.  In that world, there is a proven track record of academic weaknesses turning into practical exploits within the lifetimes of systems using those hashes.  The example he gives is bittorrent, which uses nothing but the hash to identify stuff.  For contrast, he specifically mentions rsync, which uses hashes to check whether files with identical sizes (and other metadata) are actually the same.

In one case, bittorrent, the system is vulnerable to the easiest attacks, and will need to be changed before those attacks become actually possible.  In the other case, rsync, the system is only vulnerable to much harder attacks, and can remain useful for years after the first class of systems has become exploitable.

Bitcoin is very much like the second class of systems.  We have constraints on the input: An attacker can't merely take an existing block and attach another megabyte of carefully prepared crap to it, he only has 80 bytes to work with, and there isn't much he can do to most of them.

So yes, if you are making systems that provide absolutely no security beyond the hash, his chart is exactly right and you should really be thinking about SHA3.  If you are making a brand new system, should at least consider what that chart has to say, but you don't need to follow it blindly.  In the base of bitcoin, despite published academic "weaknesses", SHA2 was still the right choice, and will remain so for many years (decades, likely).

FYI, at least two other threads link to that site: June of 2011 and July of 2012.

[DeathAndTaxes]

The chart is correct, it just doesn't apply to us.  ... He is concerned with compare-by-hash, as it applies to identifiers for arbitrary data.

I get that but the chart is STILL incorrect.  There is no known weakness of SHA-2.  Period.  There is a known weakness against an algorithm (not used by anyone anywhere for any purpose) which is similar to SHA-2 except it uses 42 rounds instead of 64.  Had SHA-2 used 42 rounds it would indeed be weakened but it does not.  Even given infinite energy and time the weakness can no be used to produce a preimage of a SHA-2.  

The only method of preimage of an SHA-2 hash is pure brute force requiring 2^256 operations.
The only merhod of collision of a SHA-2 hash is pure brute force requiring 2^128 operations.

As these are the maximum possible based on the hash length it by definition not "weakened".  The amount of operations required to attack an SHA-2 hash are exactly the same as they day the algorithm was created and exactly the same as any other 256 bit hash that has no known weaknesses.

So yes, if you are making systems that provide absolutely no security beyond the hash, his chart is exactly right and you should really be thinking about SHA3.

No you shouldn't as there is no weakness of SHA-2 at this time and SHA-3 has insufficient real world crypto-analysis.  This is why NIST currently prohibits (as in it is criminal charge) for using SHA-3 in classified systems.  The only authorized cryptographic hash for use in classified systems is SHA-2.  Eventually SHA-3 will be allowed and possibly sometime in the future if/when SHA-2 develops a known weakness SHA-2 will be deprecated but that day isn't today and it might not be for decades (if ever).

The chart is absolutely incorrect and such a simple mistake indicates a lack of entry level knowledge by the author.  Please provide a cite from a reputable cryptography advising anyone for any production system for any purpose to dump SHA-2 in favor of the significantly less vetted SHA-3 TODAY.

Lastly I would point out that while the "winner" of SHA-3 has been decided this doesn't mean the final SHA-3 algorithm will be bit for bit identical to the candiate algorithm which won.  NIST has not published the SHA-3 specification and based on internal reviews it is possible NIST will make tweaks to the algorithm before releasing the finalized spec.  Anyone claiming to implement SHA-3 is more accurately implementing the " Keccak" algorithm or "SHA-3 draft".  Implementing so called "SHA-3" today runs the risk that your implementation will NOT be the standard and thus in the future when there is SHA-3 hardware acceleration it will NOT apply to your similar yet incompatible implementation.


TL/DR: the chart is wrong for all usages in all scenarios.

[kjj]

The chart is correct, it just doesn't apply to us.

I get that but the chart is STILL incorrect.  There is no known weakness of SHA-2.  Period.  There is a known weakness against an algorithm (not used by anyone anywhere for any purpose) which is similar to SHA-2 except it uses 42 rounds instead of 64.

That is the criteria for getting marked "weak".  When it progresses to an actual weakness against a full-round version, they call it "broken".

This is the standard progression of academic cryptanalysis.  Ponder MD5.

[DeathAndTaxes]

The chart is correct, it just doesn't apply to us.

I get that but the chart is STILL incorrect.  There is no known weakness of SHA-2.  Period.  There is a known weakness against an algorithm (not used by anyone anywhere for any purpose) which is similar to SHA-2 except it uses 42 rounds instead of 64.

That is the criteria for getting marked "weak".  When it progresses to an actual weakness against a full-round version, they call it "broken".

This is the standard progression of academic cryptanalysis.  Ponder MD5.

No it isn't not in any official capacity.  Maybe this user (and you) have recoined the term "weak" to mean any derivitive function has greater than brute force efficiency but no standards body uses that alternative definition.  Please link to a single cite by any reputable cryptographer or recognized body which defines SHA-2 as cryptographically weak/weakened.

I am well aware of the history of MD5.   SHA-1 is a better example.  It is considered cryptographically weak because there is a theoretical attack possible on the full algorithm , it is theoretically possible to produce a SHA-1 collision with "only" 2^61 operations, vs the 2^80 required for a brute force search.  Still it is important to point out that at this point no SHA-1 collision (in any system, under any conditions) has ever been found/reported.  However that vulnerability was sufficient in 2004 for NIST (and other standards bodies) to deprecate SHA-1 in favor of SHA-2 and other algorithms. If Bitcoin used SHA-1 it likely would be safe in the short term (as 2^61 operations is still a staggering amount of computing power) but since SHA-1 is genuinely weakened it would be prudent for developers to consider a transition plan to SHA-2 or some other secure algorithm.

[prophetx]

if sha-2 had to be replaced with something else, would that make any ASICs operating at that point in time obsolete?  hashing power would plummet?

[DeathAndTaxes]

if sha-2 had to be replaced with something else, would that make any ASICs operating at that point in time obsolete?  hashing power would plummet?

It depends.  If the POW algorithm is replaced, they would become instant paperweights.   However if SHA-1 is any indication it is very likely that any cryptographic weakness will take years to develop.  It will be interesting to see how that plays out as there likely will be alarmist who want to change instantly no matter the cost.  This could actually reduce security as it would overnight obsolete a massive amount of hashing power.  On the other hands large ASIC owners will likely want to drag out any transition possibly longer than would be safe.

A more likely scenario is that SHA-2 becomes cryptographically weak but that weakness has no relevance in mining.  Remember though that SHA-2 is used in the creation of addresses and a preimage vulnerability here could allow theft of funds.  If SHA-2 is weakened it would be prudent to design new address types which doesn't use SHA-2.  The timeline could be measured in months if not years but users a plan forward would be to allow users to transfer funds from existing "version1" addresses to some new more secure "version 2" addresses.

[smscotten]

Follow the sources/citations/footnotes. Rather quickly you get to something which says that SHA-256 has been examined for weaknesses. Historically being examined for weaknesses is on the road to someone finding a weakness, therefore it's on it's way to being broken and OMFG it's already useless.

It's a combination of bad logic, the telephone game problem, and shoddy researching.

http://valerieaurora.org/hash.html refers to http://www.larc.usp.br/~pbarreto/hflounge.html where SHA-256 has the dreaded magnifying glass icon next to it. note the key:

"Finally, the symbol (Magnifying glass) means the function design or a reduced version thereof has been analyzed by third parties, pushing the limits of known cryptanalysis techniques without indicating a weakness in the full design." (emphasis mine)

[Luckybit]

According to http://valerieaurora.org/hash.html, weaknesses in SHA-2* have already been discovered. I know nothing about how these really work and know nothing about the weaknesses. However do we have a plan to migrate to another POW in a event the hashing algorithm is broken?

Or is the plan to pretend that SHA-2* will stand for all time unlike any crypto ever, and watch Bitcoin be destroyed?

SHA256 is safe. In fact it's one of the safest most conservative choices Satoshi could have made. Ask anyone who knows anything about this and you'll get a similar answer.