SHA-256 broken, collisions found... Bitcoin then?

[hahahafr]

Hello,

So my understanding is that Bitcoin relies at its core on SHA-256 to ensure it is secure and works. Since RIPEMD-160 is just a shortening layer, and nobody seems to worry about the ECDSA secp256k1 curve, let's talk about SHA-256 and Bitcoin.

It is just a matter of time before SHA-256 gets broken. By brute-force we are fine (centuries, or centuries/2 with quantum computing).
But what about flaws in the "design", like every other cryptographic hashing algorithm before, it will be broken down by cryptanalysts. Question is when? 5 years? 10 years?

2nd Question: how is Bitcoin network going to react? Are there already plans for this?

Some links I gathered while quicksearching on the subject:
http://security.stackexchange.com/questions/6458/security-of-sha256-and-bitcoins
https://bitcointalk.org/index.php?topic=18211.0
https://www.google.com/search?q=quantum+sha256
https://bitcointalk.org/index.php?topic=3008.0
http://en.wikipedia.org/wiki/Post-quantum_cryptography
https://bitcointalk.org/index.php?topic=7769.0
http://en.wikipedia.org/wiki/Comparison_of_cryptographic_hash_functions#Cryptanalysis

[moni3z]

Every world cryptographer has no reservations about SHA-224, SHA-256, SHA-384 or SHA-512, which is why a few of them including Bruce Schneier (who submitted Skein) thought the new SHA-3 standard wasn't necessary just yet, but NIST chose one anyways a month ago. http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html

I would assume bitcoin is fine, and they can probably go to SHA-3 whenever it needs to be done

SHA-1 is the problem http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html
"A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021"

[DannyHamilton]

If SHA-256 is ever found to have a flaw, it won't allow anyone to spend or "steal" your coins.  It won't allow someone to create counterfeit coins. It might allow someone to increase the number of coins they mine, and it might allow someone to double-spend coins that they own, but the bitcoin community is aware of this weakness and is likely to notice if something like this starts to happen.

Changing the proof-of-work hashing algorithm would be a pretty significant change, but if it is discovered that there is a weakness in SHA-256, there would be enough incentive that it would likely be accepted by the community and a new proof-of-work algorithm would likely be implemented pretty fast.  Until it was, spending bitcoin through the blockchain might be a bit difficult (since people would be wary of accepting bitcoin that might be double-spent).

Of course if we are talking about 10 or more years from now, a large percentage of bitcoin denominated transfer may not go through the blockchain, so that the delay waiting for a new proof-of-work algorithm might not significantly affect the ability for individuals to engage in commerce.

[kjj]

Catastrophic breaks in hashes are pretty much unheard of these days.  What happens is that they get weaker gradually, with plenty of warning.  For example, MD5 is considered to be totally broken now, and should never be used.  On the other hand, if it was used in bitcoin transactions, those transactions would still be totally safe, for at least a few more years, because all of the attacks require conditions that can't be met in the bitcoin system.  As in, if we changed one of the NOPx opcodes to OP_LOL_CHECKMD5SIG which used MD5(MD5(key)) instead of RIPE-MD160(SHA256(key)), it would still take decades to crack, probably centuries.

And your estimate of how long a brute force attack on SHA-256 would take is wrong, it isn't centuries, it is billions and billions of years, minimum.  If you converted the entire mass of the sun into energy, and used all of that energy to increment a counter using the absolute limit of physics for minimum energy used to flip a bit, you'd get to around 2²²⁵.  You'd need 2³¹ suns of similar mass to finish just iterating through all of the possible inputs.  So, billions of stars, or trillions or quadrillions if you want to actually perform the hashes too.

There are no "plans" exactly, on what to do next, but it is widely understood that we can swap out the primitive operations when needed.  We might not be alive then, why should we presume that the people that will actually be doing the work want to follow our plans instead of making their own?

[deepceleron]

Hash twice? Oh, wait, already done...

[b!z]

Catastrophic breaks in hashes are pretty much unheard of these days.  What happens is that they get weaker gradually, with plenty of warning.  For example, MD5 is considered to be totally broken now, and should never be used.  On the other hand, if it was used in bitcoin transactions, those transactions would still be totally safe, for at least a few more years, because all of the attacks require conditions that can't be met in the bitcoin system.  As in, if we changed one of the NOPx opcodes to OP_LOL_CHECKMD5SIG which used MD5(MD5(key)) instead of RIPE-MD160(SHA256(key)), it would still take decades to crack, probably centuries.

And your estimate of how long a brute force attack on SHA-256 would take is wrong, it isn't centuries, it is billions and billions of years, minimum.  If you converted the entire mass of the sun into energy, and used all of that energy to increment a counter using the absolute limit of physics for minimum energy used to flip a bit, you'd get to around 2²²⁵.  You'd need 2³¹ suns of similar mass to finish just iterating through all of the possible inputs.  So, billions of stars, or trillions or quadrillions if you want to actually perform the hashes too.

There are no "plans" exactly, on what to do next, but it is widely understood that we can swap out the primitive operations when needed.  We might not be alive then, why should we presume that the people that will actually be doing the work want to follow our plans instead of making their own?

I completely agree with what you are saying.
It seems very true.

[Mike Hearn]

If I had to make a list of risks to Bitcoin, flaws in any of the underlying mathematical primitives would be right at the bottom. ECC is old enough now that it's been widely studied. You do see breaks in very new forms of cryptography like pairing-based crypto, but ECC seems ok.

Catastrophic failure is far more likely to be caused by unnoticed bugs in the implementation. Bitcoin is phenomenally complicated and there are many subtle ways to break it.

DoS attacks, problems with the way people use the software: not using encrypted wallets, malware that can steal from encrypted wallets, privacy leaks, failure to make backups, etc. All of these can give Bitcoin a bad name and scare people away.

[Etlase2]

A collision or preimage attack on SHA256 wouldn't have any effect on bitcoin, as far as I can tell. This does not increase the brute-forcing ability of finding m + nonce where h < difficulty.
A collision attack on RIPEMD160 would be worrisome, but you still need to know the private key of the public key being hashed, and private key ECDSA operations are many magnitudes slower than hashing.

[hamdi]

worst case we would have to do some kind of rollback.

[Realpra]

Catastrophic failure is far more likely to be caused by unnoticed bugs in the implementation. Bitcoin is phenomenally complicated and there are many subtle ways to break it.

I hear this a lot, but is it really true?

You can't print BTC without sha256 and you can't steal peoples money without EC. Both are very secure as has been noted - even algorithmic weaknesses would likely only lower the brute forcing time, not remove it.

Sure you might scam and cheat a few guys clients if you found some bug or isolated them, but is there really something that could cause a complete breakdown when the 2 main principles are SO iron clad?

Now light clients and online wallets is another story... what we need is faster/smarter clients so everyone can do some verification.

[molecular]

2nd Question: how is Bitcoin network going to react? Are there already plans for this?

There are plans: The "important people" meet online and make overnight hard fork to some other hashing scheme.

[Realpra]

2nd Question: how is Bitcoin network going to react? Are there already plans for this?

There are plans: The "important people" meet online and make overnight hard fork to some other hashing scheme.

.. while persisting the blockchain db backups prior to the crash as hardcoded into the new fork.

The effect would be minor I think.

[molecular]

2nd Question: how is Bitcoin network going to react? Are there already plans for this?

There are plans: The "important people" meet online and make overnight hard fork to some other hashing scheme.

.. while persisting the blockchain db backups prior to the crash as hardcoded into the new fork.

The effect would be minor I think.

Effect on bitcoin network and security might well be minor.

However: effects on other stuff that uses sha-256 that can't be switched quickly might be major, no?

[malevolent]

The only problem to worry now and in the future about is user incompetence - looking at the amount of hacks (or 'hacks' - see this thread: https://bitcointalk.org/index.php?topic=83794.0;all ) an average user or business owner knows little about protecting himself from losing BTC. I am afraid this will not change as more and more people are drawn into bitcoin. I believe this is where the Bitcoin Foundation could start doing something.

[sgravina]

SHA-256 does have a flaw:  I don't understand it.  If you cant explain it to me then it is too complicated.

[molecular]

SHA-256 does have a flaw:  I don't understand it.  If you cant explain it to me then it is too complicated.

maybe this helps to figure it out?

nick@zero ~ $ echo "123" | sha256sum
181210f8f9c779c26da1d9b2075bde0127302ee0e3fca38c9a83f5b1dd8e5d3b  -
nick@zero ~ $ echo "124" | sha256sum
ca2ebdf97d7469496b1f4b78958f9dc8447efdcb623953fee7b6996b762f6fff  -
nick@zero ~ $ echo "125" | sha256sum
a5e45837a2959db847f7e67a915d0ecaddd47f943af2af5fa6453be497faabca  -
nick@zero ~ $ echo "verylongdatalongerthaneventhechecksumitselfjustaddingrandombitsnow9823480293849 20834092834029834029834028934092834" | sha256sum
3dff4001b5954d595b6d6b3a4ec3971c2eef82da397e6a81a514090052918ed7  -

now let's mine for a bit

nick@zero ~ $ for nonce in {0..999}; do echo $nonce x`echo $nonce | sha256sum`; done | grep x00
691 x0024839ec9632d382486ba7aac7e0bda3b4bda1d4bd79be9ae78e7e1e813ddd8 -
964 x00ae0900e3ba03583e3561d76de50754935c10913065d737f9cf4c8e86e54bda -
996 x009cbb4830299d01fc84a6a56d4f07707d7d073673f6cde576027bafbac75168 -

ah, found 3 blocks, cool

[Remember remember the 5th of November]

Every world cryptographer has no reservations about SHA-224, SHA-256, SHA-384 or SHA-512, which is why a few of them including Bruce Schneier (who submitted Skein) thought the new SHA-3 standard wasn't necessary just yet, but NIST chose one anyways a month ago. http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html

I would assume bitcoin is fine, and they can probably go to SHA-3 whenever it needs to be done

SHA-1 is the problem http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html
"A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021"

Ugh, no they can't. Since ASIC devices will be obsolete then. And if they are as expensive as today, well you can guess what happens then.

[malevolent]

I think there will be pressure not to change the protocol even if such a need arises because so many people have invested in ASICs (and AFAIK in most cases those ASICs cannot be repurposed to do anything other than mine Bitcoins). I hope this does not kill Bitcoin one day.

[molecular]

I think there will be pressure not to change the protocol even if such a need arises because so many people have invested in ASICs (and AFAIK in most cases those ASICs cannot be repurposed to do anything other than mine Bitcoins). I hope this does not kill Bitcoin one day.

In general, everyone can mine the chain he wants to mine. If sha256 is "broken" ("easily collidable"), there is no sense to use ASIC. They are instantly worthless scrap because the sha256-fork can be "fake-mined" with no effort.

So that "pressure" you're talking about is like demanding noone was to mine any other chain. That's absurd.

[sippsnapp]

Every world cryptographer has no reservations about SHA-224, SHA-256, SHA-384 or SHA-512, which is why a few of them including Bruce Schneier (who submitted Skein) thought the new SHA-3 standard wasn't necessary just yet, but NIST chose one anyways a month ago. http://csrc.nist.gov/groups/ST/hash/sha-3/winner_sha-3.html

I would assume bitcoin is fine, and they can probably go to SHA-3 whenever it needs to be done

SHA-1 is the problem http://www.schneier.com/blog/archives/2012/10/when_will_we_se.html
"A collision attack is therefore well within the range of what an organized crime syndicate can practically budget by 2018, and a university research project by 2021"

Ugh, no they can't. Since ASIC devices will be obsolete then. And if they are as expensive as today, well you can guess what happens then.

There are two parties, those heavily invested in gpu mining and those who preordered and heavily invested in asic mining.
EDIT: Guess the asic manufacturers are sitting on a unpredictable risk when a algo change is seriously considered at anytime.