Subject: Re: [Bitcoin-development] Lets discuss what to do if SHA256d is actually broken

From: Kevin <[email-masked]>
Date: Tue, 03 Jun 2014 10:43:39 -0400

On 6/3/2014 12:29 AM, xor wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA256
>
> Hi,
>
> I thought a lot about the worst case scenario of SHA256d being broken in a way
> which could be abused to
> A) reduce the work of mining a block by some significant amount
> B) reduce the work of mining a block to zero, i.e. allow instant mining.
>
> Bitcoin needs to be prepared for this as any hash function has a limited
> lifetime. Usually crypto stuff is not completely broken instantly by new
> attacks but gradually. For example first the attack difficulty is reduced from
> 2^128 to 2^100, then 2^64, etc.
> This would make scenario A more likely.
>
> Now while B sounds more dangerous, I think in fact A is:
> Consider how A would happen in real life: Someone publishes a paper of a
> theoretical reduction of SHA256d attacks to 2^96 bit. Mathematicians will
> consider this as a serious attack and create a lot of riot.
> If no plan is made early enough, as in now, the Bitcoin Core team might then
> probably want to just do the easiest approach of replacing the hash function
> after a certain block number, i.e. a hard fork.
> But what about the Bitcoin miners, those who need to actually accept a change
> of mining algorithm which renders their hardware which cost MILLIONS
> completely worthless?
> Over the years they have gotten used to exponential growth of the Bitcoin
> networks hashrate, and therefore exponential devaluation of their mining
> hardware. Even if the attack on SHA256d causes a significant growth of
> difficulty, the miners will not *believe* that it is an actual attack on SHA256d
> - - maybe it is just some new large mining operation?  They are used to this
> happening! Why should they believe this and switch to a new hash function
> which requires completely new hardware and therefore costs them millions?
> They will just keep mining SHA256d. Thats why this is more dangerous, because
> changing the hash funciton won't be accepted by the miners even though it is
> broken.
> Something smarter needs to be thought of.
>
> Now I must admit that I am not good at cryptography at all, but I had the
> following idea: Use the altcoin concept of having multiple hash functions in a
> chain. If SHA256d is broken, it is chained with a new hash function.
> Thereby, people who want to mine the new replacement hash function still will
> need ASICs which can solve the old SHA proof of work. So existing ASIC owners
> can amend their code to do SHA256d using the ASIC, and then the second hash
> function using a general purpose CPU.
> This would also allow a smooth migration of difficulty - I don't even know how
> difficulty would react with the naive approach of just replacing SHA with
> something else: It would probably be an unsolvable problem to define new rules
> to make it decrease enough so new blocks can actually be mined by the now
> several orders of magnitude slower CPU-only mining community but still be high
> enough to be able to deal with the fact that millions of people will try their
> luck with mining at the release date.
>
> While this sounds simple in theory, it might be a lot of work to implement, so
> you guys might want to take precautions for it soon :)
>
> Greetings,
> 	xor - A Freenet project developer
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.14 (GNU/Linux)
>
> iQIcBAEBCAAGBQJTjU9DAAoJEMtmZ+8tjWt5pNEP/2460eHu7ujrUSxinJXY7+wF
> E759/NcpNuakqu4NsS3ndi8lSiVIeixiOWZxPwLYkzC0pgPd5JrK5hdrYewsgreL
> Ltkh6LKB4YZLYrV3jm62ZPMTzCopYQ1l872xbN3PJQJoXhEp4fKu99++LDzVg9Gk
> n7rvrk6Iy/nSsZ1IMANpKghbU8/Gtn6ppCJv9rxRE//CZdTso1tTyOXXkEEMTHcV
> y/iv6CHXtTXPvOgEgciU0oCPq0NOUKdIAOD//ybcKzncOoHSmwr1rZdreCTH6/Ek
> 9uwq/HaQnseHPrq9qrIkIKrZDlnjKu7Tqw1BlbyBeCrWdJPCeDJg2kyCXgTvIzFD
> oXwZ6r16tb2QPR4ByyO1lZy9G2Pp26thk12BnadnPYTf1rMvsY15BjfUrCU9ppt/
> YpFAZSFlXUGOuOBKUznUeO8U1bXJylcTTnyER/cudOpcKR8Jt9l5tfm5LTHCB6Q2
> Tjmvsmd0BzwafLEhHD5FHoTZFNVdXWvEUO/w4I/2UWTS7CacbE1qk0rVpsF/4L1K
> /oFVnZIUKqsm5mMMb6WTQq+MjP2TF/eAAwm2UtFYmj0FVML9HBNwyiAc5UKwnD4Y
> Yq3Pl5QfRobwu6pgT3zO7vK+saOl8sePWbU8Skj41OTEDrJM4QIQGAqs1U8xke8+
> YnUYiyzreJ8ofHhNBs4/
> =dkuk
> -----END PGP SIGNATURE-----
>
>
> ------------------------------------------------------------------------------
> Learn Graph Databases - Download FREE O'Reilly Book
> "Graph Databases" is the definitive new guide to graph databases and their
> applications. Written by three acclaimed leaders in the field,
> this first edition is now available. Download your free book today!
> http://p.sf.net/sfu/NeoTech
> _______________________________________________
> Bitcoin-development mailing list
> [email-masked]
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
It is good to start thinking about such things.  Let's face it, it could 
happen.  However, short of having bitcoin use another algorithm for 
encryption, I am not sure much could be done.  That's just me.

-- 
Kevin