Topic: SHA-2* family maybe broken in several years. - page 2. (Read 7738 times)

I completely agree about the second way of theft. But let's imagine someone broke both SHA-256 and RIPEMD-160 and able to produce a set of pubkeys corresponding to a bitcoin address. Indeed, it is highly likely, that very many pubkeys correspond to a single bitcoin address, at least since it's a mapping from 512 bits to 160 bits. But doesn't that hacker/cryptography genius still need to get at least one private key corresponding to one of those pubkeys to actually steal those coins. And doesn't getting a privkey from a pubkey mean breaking ECDSA?

You are half right and my statement was incomplete.  A compromise of SHA-256 alone would not be sufficient.  You would need to break BOTH SHA-256 and RIPEMD-160 but not necessarily ECDSA to steal bitcoins because there are two potential attack vectors.  You can (in theory) steal coins by finding a preimage of the public key that produces the same hash or by finding the correct private key to sign the transaction.

Thus to steal coins you would "only" need to break EITHER both hashing function or ECDSA.

Theft by preimage.
Bitcoin validates transactions by ensuring the public key of the signature corresponds to the pubkeyhash defined in the output being spent.  Thus if the attacker can find a pubkey which hashes to the correct pubkeyhash then he can spend the victims coins without breaking ECDSA.

pubkeyhash = RIPEMD-160(SHA-256(SHA-256(pubkey))

So if there is an unspent output sent to pubkeyhash P one "only" needs to perform a preimage attack to find a different pubkey p that produces the same pubkeyhash P.  There are potentially trillions of pubkeys which produce the same pubkeyhash.  However the triple hashing using two different algorithms designed by different entities and using different internal structures makes the odds that they would simultaneously be both compromised significantly enough to make such an attack feasible very low.  Still just for academic correctness you would NOT need to compromise ECDSA in order to perform this attack.


Theft by breaking ECDA
This IMHO is the more "likely"* attack scenario and it requires the pubkey to be know (funds have been spent from this address thus the pubkey is recorded in the signature of the tx input).  Given the pubkey the attacker either through a classical attack due to a cryptographic flaw in ECDSA or through some future advancement in QC and Shor's algorithm uses the pubkey to find the privkey.  Not reusing addresses greatly complicates this attack vector as the pubkey remains an unknown to the attacker. 

* By more likely I mean you are more likely to die by a shark then by meteor strike, both are rare.

Correct me if I'm wrong, but how one can steal bitcoins?
There are two possible ways:
1) find a collision, i.e. find another private ECDSA key which corresponds to the same bitcoin address (private ECDSA key--> public ECDSA key -(SHA256)->-(RIPEMD160)->Bitcoin address )
2) reconstruct private ECDSA key from a bitcoin address

In either case it's not enough to break SHA256, it's also needed to break RIPEMD160 and ECDSA.

Er actually it is:

prefix&nonce&data

bit of a difference, specifically because in your order:
data+nonce indicates that each change of the nonce would force a complete recalculation

 whereas the nonce inserted in the middle  means that a pre-pre state can be stored consisting of a pre-hashed data segment,

small point .. but let's be accurate when discussing the inner workings.....

One thing I don't understand is why didn't Satohi use the double SHA-256 + RIPEMD-160 combo that is used in other areas for the POW.  It would provide redundancy in the (highly unlikely) scenario that SHA-2 is broken rapidly.

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.

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)

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.

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?

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.

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.

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.


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.

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.

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. 

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.

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...]

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.

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!

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.