BitcoinTalk

Dealing with SHA-256 Collisions

68
Satoshi-only
BitcoinTalk
#1
From:
lachesis
Subject:
Dealing with SHA-256 Collisions
Date:
A mathematician friend of mine pointed out that there are very few if any hash protocols that have survived for 10 years or more. What would Bitcoin's solution be if SHA256 were to be cracked tomorrow?
BitcoinTalk
#2
From:
theymos
Subject:
Re: Dealing with SHA-256 Collisions
Date:
I don't think that broken cryptography could ever be the end of BitCoin if it becomes popular. Since the block chain can be forked without losing too much data, modifications to all aspects of BitCoin are possible. If SHA-256 was broken, a new version of BitCoin would be released that would switch to a stronger hash function for addresses. Changing the hash function used for blocks might not be necessary if the weakness still required some non-trivial amount of computation. The new version would ignore SHA-256 blocks after a certain point in time, but most old transactions would survive.

In case the weakening of SHA-256 is gradual instead of sudden (much more likely, IMO), BitCoin could stretch the process of switching to a different hash algorithm over a long time. First accept SHA-512 (or whatever) in addition to SHA-256, then use SHA-512 by default, and finally stop accepting SHA-256 for new blocks.
BitcoinTalk
#3
From:
Xunie
Subject:
Re: Dealing with SHA-256 Collisions
Date:
Quote from: theymos on June 14, 2010, 02:34:57 AM
In case the weakening of SHA-256 is gradual instead of sudden (much more likely, IMO), BitCoin could stretch the process of switching to a different hash algorithm over a long time. First accept SHA-512 (or whatever) in addition to SHA-256, then use SHA-512 by default, and finally stop accepting SHA-256 for new blocks.

Wouldn't the users lose their coins?
BitcoinTalk
#4
From:
lachesis
Subject:
Re: Dealing with SHA-256 Collisions
Date:
So it's possible to switch "on the fly" to a new hash function? Wouldn't all the old transactions then be compromised (because they could be trivially recomputed)?

SHA-256 has already been weakened by a factor of 16 (according to my friend. I can't find documentation on that, but I trust him). That's 16 out of 2^256, so not a huge deal, but still.
BitcoinTalk
#5
From:
theymos
Subject:
Re: Dealing with SHA-256 Collisions
Date:
Quote from: lachesis
Wouldn't all the old transactions then be compromised (because they could be trivially recomputed)?

After thinking about this some more, I've realized that breaking the hash function used in blocks would be more disastrous than I had originally thought. But it should still be possible to change the hash function "on-the-fly" by including secure hashes of each real block in the old chain with the new BitCoin release. Some mechanism of doing this (hopefully more elegant) would also have to be used for a gradual hash change.

Quote from: Xunie
Wouldn't the users lose their coins?

Everyone's balance is publicly available, so it should always be possible to preserve this data, no matter what changes are made to BitCoin.
BitcoinTalk
#6
From:
satoshi
Subject:
Re: Dealing with SHA-256 Collisions
Date:
SHA-256 is very strong.  It's not like the incremental step from MD5 to SHA1.  It can last several decades unless there's some massive breakthrough attack.

If SHA-256 became completely broken, I think we could come to some agreement about what the honest block chain was before the trouble started, lock that in and continue from there with a new hash function.

If the hash breakdown came gradually, we could transition to a new hash in an orderly way.  The software would be programmed to start using a new hash after a certain block number.  Everyone would have to upgrade by that time.  The software could save the new hash of all the old blocks to make sure a different block with the same old hash can't be used.