Lets discuss what to do if SHA256d is actually broken
8 messages, 3 to 5 Jun 2014. Started by xor.
Rusty Russell (2), xor, Luke Dashjr, Ethan Heilman, Kevin, Ashley Holman, Charlie 'Charles' Shrem
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
On Tuesday, June 03, 2014 4:29:55 AM xor wrote:
Quoted text (6 lines)
> 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.
C) fabricate past blocks entirely.
If SHA256d is broken, Bitcoin as it is fails entirely.
Luke
An attack on the mining difficulty algorithm does not imply violation of the typical security properties of a cryptographic hash function*.
Assume someone discovers a method which makes it far easier to discover new blocks, this method: may or may not be implementable by the current SHA256 ASIC hardware.
1. If it is usable by the mining hardware, then there will be brief period of overproduction and then difficulty will adjust. If the attack is so bad that difficulty can't scale and we run out of a leading zero's, then the SHA256 collision resistance is broken and we have bigger problems. Under this scenario, everyone would see the need to immediately switch to new hardware as people could create cycles and irreconcilable forks in the block chain
2. If the attack is not usable by the mining hardware, then the miners will need to switch to new ASICs anyways and the hash function can be changed without resistance.
But lets ignore all that and say, for some unspecified reason, the bitcoin community wants to switch hash functions and has some lead time to do so. One could require that miners find two blocks, one computed using SHA256 and one computed using the new hash function. We could then slowly shift the difficulty from SHA256 to the new hash function. This would allow miners a semi-predicable roadmap to switch their infrastructure away from SHA256.
* It would be a distinguisher which would be bad, but collision resistance could be merely weakened.
On Tue, Jun 3, 2014 at 12:52 AM, Luke Dashjr <luke@dashjr•org> wrote:
Quoted text (27 lines)
> On Tuesday, June 03, 2014 4:29:55 AM xor wrote: > > 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. > > C) fabricate past blocks entirely. > > If SHA256d is broken, Bitcoin as it is fails entirely. > > Luke > > > ------------------------------------------------------------------------------ > 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 > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development >
Luke Dashjr <luke@dashjr•org> writes:
Quoted text (11 lines)
> On Tuesday, June 03, 2014 4:29:55 AM xor wrote: >> 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. > > C) fabricate past blocks entirely. > > If SHA256d is broken, Bitcoin as it is fails entirely.
I normally just lurk, but I looked at this issue last year, so thought I'd chime in. I never finished my paper though...
In the event of an *anticipated* weakening of SHA256, a gradual transition is possible which avoids massive financial disruption.
My scheme used a similar solve-SHA256-then-solve-SHA3 (requiring an extra nonce for the SHA3), with the difficulty of SHA256 ramping down and SHA3 ramping up over the transition (eg for a 1 year transition, start with 25/26 SHA2 and 1/26 SHA3).
The hard part is to estimate what the SHA3 difficulty should be over time. My solution was to adjust only the SHA3 target on every *second* difficulty change (otherwise assume that SHA2 and SHA3 have equally changed rate and adjust targets on both).
This works reasonably well even if the initial SHA3 difficulty is way off, and also if SHA2 breaks completely halfway through the transition.
I can provide more details if anyone is interested.
Cheers, Rusty.
On 6/3/2014 12:29 AM, xor wrote:
Quoted text (88 lines)
> -----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 > Bitcoin-development@lists•sourceforge•net > 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.
There is a relevant post from Satoshi on this:
https://bitcointalk.org/index.php?topic=191.msg1585#msg1585
Quote:
"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."
On Tue, Jun 3, 2014 at 9:21 PM, Ethan Heilman <eth3rs@gmail•com> wrote:
Quoted text (75 lines)
> An attack on the mining difficulty algorithm does not imply violation of > the typical security properties of a cryptographic hash function*. > > Assume someone discovers a method which makes it far easier to discover > new blocks, this method: may or may not be implementable by the current > SHA256 ASIC hardware. > > 1. If it is usable by the mining hardware, then there will be brief period > of overproduction and then difficulty will adjust. If the attack is so bad > that difficulty can't scale and we run out of a leading zero's, then the > SHA256 collision resistance is broken and we have bigger problems. Under > this scenario, everyone would see the need to immediately switch to new > hardware as people could create cycles and irreconcilable forks in the > block chain > > 2. If the attack is not usable by the mining hardware, then the miners > will need to switch to new ASICs anyways and the hash function can be > changed without resistance. > > But lets ignore all that and say, for some unspecified reason, the bitcoin > community wants to switch hash functions and has some lead time to do so. > One could require that miners find two blocks, one computed using SHA256 > and one computed using the new hash function. We could then slowly shift > the difficulty from SHA256 to the new hash function. This would allow > miners a semi-predicable roadmap to switch their infrastructure away from > SHA256. > > * It would be a distinguisher which would be bad, but collision resistance > could be merely weakened. > > > On Tue, Jun 3, 2014 at 12:52 AM, Luke Dashjr <luke@dashjr•org> wrote: > >> On Tuesday, June 03, 2014 4:29:55 AM xor wrote: >> > 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. >> >> C) fabricate past blocks entirely. >> >> If SHA256d is broken, Bitcoin as it is fails entirely. >> >> Luke >> >> >> ------------------------------------------------------------------------------ >> 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 >> Bitcoin-development@lists•sourceforge•net >> https://lists.sourceforge.net/lists/listinfo/bitcoin-development >> > > > > ------------------------------------------------------------------------------ > 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 > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development > >
Hey Rusty,
This is intriguing, do you have a writeup somewhere I can read more about ?
Thanks,
Charlie
CharlieShrem.com | *Please **encrypt messages with my PGP key <http://charlieshrem.com/contact/>*
On Tue, Jun 3, 2014 at 8:45 AM, Rusty Russell <rusty@rustcorp•com•au> wrote:
Quoted text (50 lines)
> Luke Dashjr <luke@dashjr•org> writes: > > On Tuesday, June 03, 2014 4:29:55 AM xor wrote: > >> 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. > > > > C) fabricate past blocks entirely. > > > > If SHA256d is broken, Bitcoin as it is fails entirely. > > I normally just lurk, but I looked at this issue last year, so thought > I'd chime in. I never finished my paper though... > > In the event of an *anticipated* weakening of SHA256, a gradual > transition is possible which avoids massive financial disruption. > > My scheme used a similar solve-SHA256-then-solve-SHA3 (requiring an > extra nonce for the SHA3), with the difficulty of SHA256 ramping down > and SHA3 ramping up over the transition (eg for a 1 year transition, > start with 25/26 SHA2 and 1/26 SHA3). > > The hard part is to estimate what the SHA3 difficulty should be over > time. My solution was to adjust only the SHA3 target on every *second* > difficulty change (otherwise assume that SHA2 and SHA3 have equally > changed rate and adjust targets on both). > > This works reasonably well even if the initial SHA3 difficulty is way > off, and also if SHA2 breaks completely halfway through the transition. > > I can provide more details if anyone is interested. > > Cheers, > Rusty. > > > ------------------------------------------------------------------------------ > 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 > Bitcoin-development@lists•sourceforge•net > https://lists.sourceforge.net/lists/listinfo/bitcoin-development >
Charlie 'Charles' Shrem <cshrem@gmail•com> writes:
Quoted text (3 lines)
> Hey Rusty, > > This is intriguing, do you have a writeup somewhere I can read more about ?
OK, ignore the FIXMEs, but I rehashed my stupid sim code, added some graphs to the (clearly unfinished) paper and uploaded it to github:
https://github.com/rustyrussell/bitcoin_hashchange
PDF is in there too, for easier reading.
Cheers, Rusty.