Topic: SHA-2* family maybe broken in several years. (Read 7738 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.