Bitcoin Forum

This guy makes Bitcoin seem immortal.

D&T is a respected member of the community who falls into the "brilliant" category when it comes down to mathematics and mining.  you have to at least respect his opinion.

Bitcoin as we know it isn't immortal. SHA256 will definitely be broken eventually, stopping Bitcoin mining completely.

But the concept behind Bitcoin, future forks of it, and its spirit will likely last until the fall of humanity.

yes, the fork that will take Bitcoin beyond SHA 256

Is this really the case? "Definitely?" If bitcoin's algo's become useless to the point of causing bitcoin to completely fail, I'm not sure people would ever have faith in cryptocurrency again. At least not the public. Hell, I wouldn't.

I read time and time again that if catastrophic flaws in SHA256 are discovered, bitcoin is the least of our problems. Not really sure if that is true or not, though.

what about the coins in this case then? please point it out for a new member of the comunity.  :)

When sha256 becomes broken, the way it will be detected is that the blocks will be be solved faster than anticipated.  Perhaps someone finds a weakness in sha256 which will make it a little easier to solve blocks.  This happens in cryptography once in a blue moon.  When this happens, the dev team will change the algorithm to something that is unbroken and tell everyone to upgrade.

All ASIC miners will become obsolete.  CPU miners will once again be used to solved blocks for maybe a month.  Then GPU and FPGA miners will be reprogrammed to solved the new cyptographic puzzle.

Bitcoin will endure until quantum computing becomes a reality but that is so far in the future.  At that time, advances in cryptography will allow the Bitcoin devs to adapt to Shor's algorithm.

As a side note, the way I understand it, the private keys are encrypted using elliptical curve cryptography which is different from solving blocks which use sha256.

Every past hash function has failed at some point.  It's likely only a matter of time.  However, they are usually broken in increments (instead of 256 bits of protection, you only practically get 256 - X bits).  Before X reaches 128 bits, I'd expect to see bitcoin (and anything else using SHA256) to move to a newer, more robust algorithm.

Bitcoin won't fail because of this.  Even with a partially broken SHA256, difficulty will just go up because miners can use the shortcuts just as easily as attackers.  When the time comes, the switch will require a hard fork, but what miner would want to stay with the old, broken algorithm?  The biggest threat is if we have two competing algorithms to replace it.  However, by the time we get there I would think there would be several companies and individuals in the position (the funds and motivation) to really analyze the options thoroughly and to be able to reach an information based consensus.

we will have a sense well before then.  reports will start surfacing from the academic/mathematics community that a "solution" to SHA 256 is on the verge of happening.  it will be then, if not before, that the cryptographers will need to get to work to find the next solution.  i think Bitcoin will be able to outrun any of these new discoveries as it has it the past.  remember that Bitcoin and all open source projects are leveraging the use of the worldwide community as a whole rather than select closed groups of individuals.

ok thank you! but what will happen with the old coins? they become worthless and need to be replaced with new ones?

Here is an example post of sha1 being broken by a chinese university team:

http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html

no.  these new algorithms will be constructed to perpetuate the usage of existing coins.

Thank you for explaining this to me. So it will more likely follow the demise of MD5, correct?

Also, I'm assuming the only way to fix that problem in the future will be a hard fork. (I'd like to see a thread about the problems of an organized fork, I'm headed to the search bar)

@jimbobway
How would that appear any different than more hashing power added to the network? I'm guessing no one will know that it's broken until someone draws up a proof.

If sha256 is broken then, I think, everyone will keep their coins.  It's just that it is easier to solve blocks so the hackers* get more of the newly mined coins.

If elliptical curve cryptography is broken, what a hacker would do, for maximum profit/destruction is to target the wallet address with the most bitcoins and hack that address to determine the private key.  ECC is very, very strong and it is unlikely it will be broken without the use of a quantum computer.

* EDIT: Actually they would not be hackers, IMO.  They just found a better way to mine.

thank you! great! and now spread this to "ordinary" people...  ;D

The only problem would be if the fork was poorly organized, and people were still sending their coins around about the time of the fork. I'm scared of a blockchain fork.

Too many people have too much money put into this thing for something to be poorly organized.

With that said, I'm sold on Bitcoins now.

yeah it's like if greece will give up the Euro in the future and the greek government has nobody to tell it and it should happen during a weekend.

Good point.  Depending on the strength of the cryptographic attack, let's supposed 100 blocks where solved in an hour.  It would raise a lot of suspicion since 100 is a lot.  The bitcoin client would then readjust the difficulty level and all other miners would not solve very many blocks.  Miners would complain and most likey the bitcoin dev team would change the algorithm.

But, if 10 blocks were solved in an hour and then the difficulty adjusted it could have been pure luck and there would be no sure fire way to prove it without mathematical proof.

I don't think breaking sha256 is "hacking".  It's like a gold miner finding the motherload.  However, I think breaking EC would be hacking.

I remember this argument he had with hashcoin (https://bitcointalk.org/index.php?topic=3008.msg728434#msg728434) on the subject of quantum computing.  I thought that D&T was wrong throughout the argument, but I'm no expert.  It just kind of ended with neither side coming around to the other's point of view.  Can you imagine??

I think it would take a lot more than disgruntled miners to cause an algo change :P

While this is correct, I'd like to point out that as mining moves to mostly ASIC, we will have the problem that any algorithm change will make all this custom hardware worthless.  I would think the producers of sha256 hardware would be able to quickly swap out the processors for something tuned to the new algorithm, but it still will be a higher barrier to get around.

i tried following that discussion when it happened too.  my mind almost exploded. 

The intent of the post quoted is being misunderstood.  The post simply deals with quantum computing and the very limited set of circumstances in which it could "kill" Bitcoin.  There are more likely threats to Bitcoin than Quantum computing.

From a big picture point of view there are three ways one could attack the cryptographic primatives used in Bitcoin:

• Quantum computing - very unlikely to be a threat (covered in the quoted post of OP).
• Brute force attack - there is insufficient energy remaining in our star to COUNT to 2^256 much less brute force it.
• Cryptographic flaw in one of the cryptographic primitives (ECDSA, SHA-256, RIPEMD-160) - the most plausible attack vector.

Is there a flaw?  It can't be proven.  SHA-256 has been very extensively tested by international community and so far it has remained very resistant to attack.  ECDSA is less tested although still subject to significant scrutiny.  At a minimum we can say no easily exploitable flaw has been found.  Now does a flaw mean "insta-kill bitcoin"?  No.  Most flaws tend to fall under the category of "only interesting to academics".  

SHA-256 (and SHA-512) has a cryptographic flaw.   ???  WTF?  Yup right here:
http://eprint.iacr.org/2009/479.pdf

There is no economic value to this flaw.  However it "could" (eventually) lead to more "practical" attacks in the future.  

So what happens if SHA-256, RIPEMD-160 or ECDSA becomes "cryptographically weak"?
Well if they became weak enough one could attack private keys at a rate faster than an exhaustive brute force search.   Existing addresses would be vulnerable (at least in theory) however Bitcoin as designed to be modified.  Miners by consensus agree to a protocol enhancement which allows creation of addresses based on new cryptographic primitives (much like how Bitcoin now supports sending coins to addresses which are the hash of a script "pay to script hash"). So some future version of Bitcoin would continue to provide LEGACY support for existing addresses AND provide support for new addresses.  The timelines on cryptographic flaws tends to be measured in years so there would be extensive time to deploy a new version, and allow users to transfer coins from old "vulnerable" addresses to new "secure" addresses.  

If eventually ECDSA, SHA-256, or RIPEMD-160 becomes so degraded an attacker may be able to mine older "vulerable" addresses to steal the coins.  Users would have an incentive to upgrade their clients and move coins to newer "secure" addresses.

It is important to understand that even if we moved to a new algorithm as a precaution it might never be possible to use any flaw in practical manner.  I will give you an example.  A flaw has been discovered in SHA-1 which allows a pre-collision attack at 10,000 faster than brute force.  Sound horrible right?  Not really.  If such a flaw existing for SHA-256 it might mean you would have a 1% chance of attacking a private key in the next billion years (instead of 0.00001%).   Still as a precaution (more against future deeper flaws) it would be prudent to enhance the protocol to support newer address types.

Would a flaw in SHA-256 fatally damage the mining aspects of the network?
Under all probable scenarios no.  A round reduction attack would simply make miners more efficient (i.e.a GPU that runs at 1 GH/s might now compute at 520 TH/s).  Since difficulty is simply an arbitrary value it wouldn't really matter.  The nominal difficulty of the network would rise but miners with upgraded software/firmware would simply miner at a higher rate.  1% of network hashing power would still be 1% of network hashing power.  The one exception would be ASICs.  Since they can't be upgraded they would be a competitive disadvantage to both future ASICS (optimized to exploit any flaw) or programmable miners (CPU/GPU/FPGA).  Now granted ASICs are so much more efficient, that any disadvantage might only be academic at best.  

TL/DR version:
1) The post quoted dealt with quantum computing not SHA-256 invulnerability.
2) SHA-256 "may" be degraded someday.
3) Any attack on SHA-256 is likely to take a long time to develop and that will give the community time to upgrade.
4) The Bitcoin protocol can be enhanced to support new "strong addresses" while retaining legacy support for older "vulnerable" addresses.

I thought the fact that RIPEMD-160 was only used in conjunction with SHA-256 made an attack on it ineffective.
I mean, if bitcoin addresses were just RIPEMD-160 of public keys then a compromise of RIPEMD-160 would be catastrophic. But since it's RIPEMD-160(SHA-256(pub_key)) an attacker would have to break *both* SHA-256 and RIPEMD-160 in order to steal people's money, right? And at that point the protocol is broken anyway because mining relies on SHA-256.

That's not an attack on SHA-256 and SHA-512. That's an attack on 41-Step SHA-256 and 46-Step SHA-512. Big difference :). SHA-256 and SHA-512 are, respectively, 64 and 80 rounds, by definition. But I'm sure you knew that. Just wanted to point that out.

Thank you D&T. I find all your posts extremely didactic.