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

interesting to know this

You would compute PubKeyB from PrivKeyB.  


It depends on how severe the break in the hashing algorithm is.   Current to find a PubKeyHash preimage requires 2^160 inputs.  That is computationally infeasible.  If both RIPEMD-160 & SHA-256 were found to be significantly weakened through cryptanalysis it is possible (although unlikely in my opinion) that the average number of operations to produce a preimage would be reduced to a level that would make it computationally possible feasible to produce that number of keypairs.

That being said I honestly don't think this will be a useful attack vector, just pointing it out for he sake of completeness.  IMHO it is far more likely that ECDSA (or ECC in general or the specific curve used for Bitcoin) will be "broken" (and Bitcoin will migrate to new stronger address systems)  than either hashing algorithm (much less both of them).   Hashing algorithms have stood the test of time better than Public Key crypto and that advantage is compounded by the fact that Bitcoin uses two different algorithms.

Slight off topic but related: One thing I have always wondered is why Satoshi didn't "harden" mining the same way.  Something made Satoshi decide to "harden" the PubKeyHash by using two separate algorithms.  Why didn't he use the same hashing algorithm for both mining and pubkeys (i.e.  hash = RIPEMD-160(SHA-2(SHA-2(input)))  or hash = RIPEMD-160(SHA-2(input)) for both PubKeyHash and BlockHash )?  Whatever enhanced protected (however small or academic) it provides one it would provide the other.    It is likely academical because a break in SHA-256 might not even undermine mining but the code was there why not use it in both places?  We likely will never know.

This implies a break in EC crypto as well, since by definition there is no efficient way to generate the private key from the public key the only way of doing this is by trial and error.

1. How do you get Private Key B that's needed to sign the transaction?

2. Isn't address generation RIPEMD-160(SHA-256(PubKey)) rather than RIPEMD-160(SHA-256(SHA-256(PubKey))?

You could "just" break RIPEMD-160 & SHA-256 OR ECDSA (limited to addresses where the PubKey is known).

Find a PubKeyB such that for an existing PubKey A they both produce the same PubKeyHash.

i.e.
PubKeyA =/= PubKey B
RIPEMD-160(SHA-256(PubKeyA)) == PubKeyHashA
RIPEMD-160(SHA-256(PubKeyB)) == PubKeyHashB
PubKeyHashA == PubKeyHashB

If PubKeyHashA == PubKeyHashB then the private key for either PubKeyA or PubKeyB can spend coins sent to Address A or B. In a "normal" Bitcoin tx (PayToPubKeyHash) you are not locking funds to a specific PubKey but locking them to a specific PubKeyHash.

 

Great way to find out an amount of lost bitcoins - if coins on ASIC side of the fork will worth anything

First, you are absolutely correct.

Second, if you wanted to be able get people's passwords, you might want to have trojan code that sends the contents of the value being hashed to a central server somewhere at the NSA or wherever to be stored for future use. It's still pretty ludicrous. And it would be impossible to hide. I'm just answering the "why" part.

Why would SHA2* have a *backdoor*?

It is a HASHING ALGORITHM NOT AN ENCRYPTION ALGORITHM.....

Change it today (with a delayed start in 6 block months) as a test on how many people verify the code they are running before upgrading.

Change the POW the day BFL ships to their last customer...   

Its not that they would make it public, it is that finding this backdoor would be the equivelent of the holy grail in cryptography.  It would instantly give you +1 quadrillion nerd points and make you a recognized name in the field.  You could get any job in cryptography anywhere in the world with your paper as your entire resume. Every cryptographer in the WORLD has been looking for flaws either intentional or merely unintended weakness for over a decade.   It has been extensively studied, analyzes, countless papers on theoretical vulnerabilities have been written, the basis for SHA-2 (DM construct) is lectured about in computer science and math courses.   It isn't just a couple cryptographers in academia looking for a flaw, we are talking about cryptographers working for foreign governments, cryptographers working for financial institutions.  You don't think if a researching working for the Russians or Chinese couldn't use this as a way to discredit the US they wouldn't. That is the power of open source.  The NSA has some smart people, but the backdoor would have to be soooooooo freaking amazingly good that the entire planet couldn't find it despite actively looking for it for the better part of the decade.  If nobody has found the backdoor then they might not for decades to come.  So why design the SHA-3 standard (which was selected in an open and transparent way) and kill your own backdoor?

To put it into context there was a RNG based on ECC which had a backdoor (NIST still claims it is merely a vulnerability).  Despite not even being popular, almost nobody was even using it, most people hadn't even heard of it, the flaw was found and published by a cryptographer just a few months after NIST published the spec.  That was a nothing compared to the effort that has gone into validating SHA-2.  It is the cornerstone of the entire cryptographic world.  Everything from secure communication, to military codes, to the global financial system depends on SHA-2.  The potential damages could run into the trillions making the effect on Bitcoin look like a rounding error. Obviously disproving a negative is impossible, but it is precisely because of the amount of time spent studying SHA-2 trying to find a vulnerability ANY vulnerability and coming up empty for over a decade that SHA-2 is consider strong cryptography, not because anyone trusts the NSA.

The entire algorithm and the source code for the implementations of it are public. You can examine it with a fine-toothed comb, rewrite it from scratch based on the algorithm, compile it yourself… how do you hide a back-door in that? You'd literally have to bribe every programmer, mathematician, and cryptographer in the world to get them to keep quiet.

Yes. But we're talking about the NSA here. They've got more resources than you can shake a stick at. They've been working on this problem hardcore since the end of WWII, because that's what wins wars. If there was a backdoor, you'd have to be incredibly naive to think that they would make this information public.

It's not a program, it's a publicly published algorithm. So such a back door, if one existed, would have to be so cleverly hidden that no programmer or mathematician or otherwise smart person would see it.

It certainly is counterintuitive to think that the government agency tasked with spying on the American people would develop a hashing algorithm designed to protect people from their spying. It was NIST after all that came out with the report claiming that WTC7 collapsed from an office fire (cough). I wouldn't be surprised at all if it turned out that SHA-2 had a backdoor.

I think the bottom line here is that quantum computing will be a huge step forward in processing power especially in certain kinds of operations, but it is not anticipated to be a silver bullet even in the most optimistic estimates. If I'm not off in my limited understanding, being able to break SHA2 four hundred undecillion times faster sounds like a whole lot faster but it would still be take about twenty times longer than the universe has existed, assuming you could get that kind of dramatic increase by magically waving the quantum wand and instantly converted the most powerful supercomputers on earth into quantum versions of themselves.

My math and underlying assumptions may be way off. I'm just saying, "no silver bullet."

Thanks for pointing out the D-Wave system is designed for compute-annealing and is not a full quantum computer (http://en.wikipedia.org/wiki/Quantum_annealing). only 5 or 10 qu-bits computers seems to actually exist. It was so good to be true. 

OK, so as SHA-2 is iterative, quantum doesn't help so much for SHA2 breaking?

About this, my idea is that one best way for brute force is ""parallelizing" (why GPU are better than CPU), so using quantum parallelism would help to "parallelize" with exponential power. But I don't know about decoherence that could bring issues in my simplitic way of seeing quant-computing.

That is not how QC works, although I don't blame you because general media/new treats QC as some kind of computing magic.  A sufficiently large (we are talking tens of thousands of qubits) general purpose QC could use Shor's algorithm to vastly reduce the complexity of breaking public key encryption. However DWave system is not a general purpose QC and is incapable of implementing Shor's algorithm against keys of any size.  QC are a theoretical future risk to many forms of public key cryptogrpahy (such as ECDSA used to sign transaction in Bitcoin).  When QC can break 32 bit keys let me know.

Still none of that applies to SHA-2 (or any hashing algorithm).  Quantum Computers generally speaking are ineffective against Hashing algorithms and symmetric encryption as Shor's algorithm can't be used.  Grover's algorithm can be used but the speed improvement is not as interesting/useful.    With grover's algorithm a preimage can be found in 2^(n/2) operations where n is hash size.  So rather than 2^256 operations SHA-2 "only" requires 2^128 operations.  Even if such a QC existed today 2^128 is a completely infeasible amount of time/power to break a single PubKeyHash.  

Against mining it is beyond useless because miners aren't looking for a single hash they are looking for any one of quadrillions which meet the target requirements.  Even with QC it is many magnitudes more difficult to break a single hash then it is to search by brute force (mining) for "any" hash which is below the the target required by difficulty.

What about quantum computing? A 256-bit quantum computer is said to performed 2^256 operation in parallel.
Nowadays D-Wave company delivers 512-qubit computer: "In 2007, the company [D-Wave] released what it called a 16-qubit quantum computer, and the company’s current model is billed as a 512-qubit machine."

Look at :
http://www.wired.com/wiredenterprise/2013/06/d-wave-quantum-computer-usc/
http://googleresearch.blogspot.co.uk/2013/05/launching-quantum-artificial.html
http://www.isi.edu/research_groups/quantum_computing/about

What do you think about all that?

I don't think owner of these kind of machine would use them to fail Bitcoin. They are used officially for searching/parsing/listening and also trying to go over singularity, speculatively for mass-spying or code-breacking. But (I would know whether) attacking Bitcoin is practically feasible nowadays.

I'm one of the among thinking that the next technological mining gap will be quantum (after CPU, GPU, FPGA and ASIC). I just wonder if we'll use it for mining, this could also be possible to use against the system. The first user using a new technology has always more chance to perform a 51% attack.

I want to share with others guys here and to have their point of view about all this.

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.

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.

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

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

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.

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?