SHA-2* family maybe broken in several years.

[DeathAndTaxes]

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.

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.

[1714690273]

1714690273

[1714690273]

1714690273

[razorfishsl]

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

[stdset]

Remember though that SHA-2 is used in the creation of addresses and a preimage vulnerability here could allow theft of funds.

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.

[DeathAndTaxes]

Remember though that SHA-2 is used in the creation of addresses and a preimage vulnerability here could allow theft of funds.

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.

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.

[stdset]

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.

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?

[the_beast]

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.

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.

[DeathAndTaxes]

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.

[the_beast]

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.

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. 

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.  

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

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.

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.

[smscotten]

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

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

[CasinoBit]

[boot52]

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.

[smscotten]

I wouldn't be surprised at all if it turned out that SHA-2 had a backdoor.

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.

[boot52]

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

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.

[smscotten]

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

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.

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.

[DeathAndTaxes]

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

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.

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.

[WastedLTC]

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

[DeathAndTaxes]

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

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.

[razorfishsl]

Why would SHA2* have a *backdoor*?

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

[smscotten]

Why would SHA2* have a *backdoor*?

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

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.

[smolen]

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

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.

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