What needs to be changed when SHA-256 is broken?

[Adam_xx]

I have found a lot of threads about PoW but not much about other aspects of SHA-256 dependence so I hope this won't be a duplicate.

Assumptions:

1) Let's say we know that SHA-256 is weakened in every possible way (collisions/preimage attacks/second preimage attacks) and will become risky to use within 10 years.
2) We have 10 years to migrate (we know the attacks will be possible but will come gradually, not overnight)
3) Let's say we have a safe replacement in the form of, for example, SHA-3 (just theoretically, it can be any hash function of the future, it is not important for the following questions)

How critical do you think the situation would be for Bitcoin? Not particularly concerned about PoW at the moment.

Questions:

1) What would have to be upgraded in Bitcoin besides mining - txids, merkle trees, block headers, signature hashes?
2) How hard would be to migrate these parts of Bitcoin with a minimum damage?
3) What would happen to all the UTXOs in e.g. P2SH, P2WPKH, etc. - could they still be moved after the hash function change (which would be a hardfork probably)?

I know we probably won't have to deal with this in our lifetime, but again, in theory, I would like to know how you think about a similar emergency scenario.

Thanks a lot!

[1714017028]

1714017028

[1714017028]

1714017028

[1714017028]

1714017028

[1714017028]

1714017028

[1714017028]

1714017028

[BlackHatCoiner]

Not that I'm a genius when it come to hash functions, but wouldn't it be much more likely to have 160-bit collisions (from RIPEMD-160) first? I remember reading that SHA2 is more computationally expensive than RIPEMD-160. That would mean drastic measures way before 256-bit hashing algorithms become weak.

1) What would have to be upgraded in Bitcoin besides mining - txids, merkle trees, block headers, signature hashes?

Multi-sig Pay-to-Witness-Scripts are SHA256 encoded with bech32. SHA256 is also used in address generation of every other address type, although the 256-bit number that is resulted from it is then hashed with RIPEMD-160. This shouldn't change unless RIPEMD-160 became weak. Then, it's the Lightning Network.

2) How hard would be to migrate these parts of Bitcoin with a minimum damage?

I have a feeling that it won't be that hard. As far as I know, Bitcoin has had a hard fork only once, with the value overflow incident, but if it's a necessity (as it was in 2010), I believe consensus will be found.

In other words: If it's favoring every user, it's reasonable to assume that there won't to be a lot of noise. If we're bordering on benefits, such as back then with the block size war, it's going to be tough.

3) What would happen to all the UTXOs in e.g. P2SH, P2WPKH, etc. - could they still be moved after the hash function change (which would be a hardfork probably)?

There are two choices.

• We leave them untouched, which means they can be taken by those who own the required computational power.
• We announce that SHA256 will not be recognizable by the hard-forked client after block x. This could leave few years for their owners to upgrade to a collision-safe algorithm. Those who had lost access to them or wouldn't want to upgrade for some reason, would have them removed from the hard-forked Bitcoin's circulation.

[kaggie]

3) What would happen to all the UTXOs in e.g. P2SH, P2WPKH, etc. - could they still be moved after the hash function change (which would be a hardfork probably)?

There are two choices.

• We leave them untouched, which means they can be taken by those who own the required computational power.
• We announce that SHA256 will not be recognizable by the hard-forked client after block x. This could leave few years for their owners to upgrade to a collision-safe algorithm. Those who had lost access to them or wouldn't want to upgrade for some reason, would have them removed from the hard-forked Bitcoin's circulation.

If there is a flaw found, then it's first come, first serve. You can't get around it because there isn't an unquestionable registry of attached names to all the addresses used, and there won't be.

As BHC suggests, it may be that addresses subject to the flaw will be locked, but it's the same effect as if they were not locked: the value goes down. If it becomes trivially easy to crack the hashes of old unused addresses, then all associated bitcoin will automatically become worth less and less in either case without a new solution. Locking them might actually cause a bigger crash then coming to a different solution.

Another solution rather than locking them is changing the fungibility between address types - like enforcing an additional (transaction?) cost with a new kind of address when coming from an older address.  Right now, all kinds of addresses can be traded to the other kinds of addresses, but if a critical flaw were discovered, that should not be the case. It would create multiple networks within a network, which I suspect is unavoidable over a very, very long period.

Because we don't know what the most severe flaws will exist yet, it's fine to have fungibility between address types. Having several strong hedges against flaws hopefully helps. Blindly discovering the key to any reasonably random address is costly and probably impossible right now, regardless of address type. Presently having multiple address types provides a protection against those unknowns, such that including even P2PK despite Pollard's kangaroo provides a protection, because the other addresses may have flaws yet undiscovered.

Bitcoin has proven itself against numerous flaws over the past 13 years, and so is reasonably well established. Moving to new types of hashes may present worse unknown flaws without as rigorous of testing.

[BlackHatCoiner]

Moving to new types of hashes may present worse unknown flaws without as rigorous of testing.

Let alone that if it hasn't even shown a sign of weakness, as ECDLP has, it won't do any good all. No one tells us that the new algorithm won't become weak in few decades, but the system will get less efficient. There's also the temporary community upheaval asides.

[garlonicon]

Let's say we know that SHA-256 is weakened in every possible way

You can test that case. Just replace 64 rounds of SHA-256 with 16 rounds of SHA-256. Then you can test all attacks you want, you will have full control over this hash function.

we know the attacks will be possible but will come gradually, not overnight

Just create some honest nodes that will check hashes incrementally. Then, create one node that will produce stronger and stronger hashes, raising difficulty to the insane levels. You will quickly see, how that scenario looks like.

Let's say we have a safe replacement in the form of, for example, SHA-3

Try fixing your 16 rounds SHA-256 with real SHA-3 and see, why it is not so trivial.

Not particularly concerned about PoW at the moment.

It is probably the first problem you will see, because if SHA-256 is fully broken, then you can create a block with zero hash. That would also mean, it would be a previous block from the Genesis Block perspective, so you will have a ring, instead of a chain. By breaking SHA-256, you can quickly realize that your attack will shut down nodes, will freeze the chain, will cause huge blockchain reorganization after passing difficulty adjustment, and will cause huge damage, unless carefully planned and gradually introduced.

What would have to be upgraded in Bitcoin

Bitcoin Message signing (outside of on-chain signatures of regular transactions). Also all hashed public keys (because if you can execute a preimage attack, then you can replace public keys). All hashed scripts (faster than hashed public keys, because you can just use "<randomData> OP_DROP <yourPubKey> OP_CHECKSIG" everywhere and spend that). The same with commitments (if you commit anything to the chain and it uses SHA-256, then that commitment is no longer valid). All timestamps outside Bitcoin that used block hashes will be invalid. In short, it would be just a public database that anyone can modify, so it will be useless, unless fixed.

How hard would be to migrate these parts of Bitcoin with a minimum damage?

Porting txids: every txid should be re-hashed, just like in Segwit you have txid and hash, here you will have one more field for a new hash.
Mining: you will have two difficulties, one to preserve the old, SHA-256 chain, and the new, to keep it unaltered.
Merkle trees: each merkle tree should be re-hashed, it could be a commitment, like in Segwit, but could be also better compressed.
Block headers: you will have 80-byte new header that would contain both old and new data, in a combined and compressed form.
Signature hashes: you have to use new hashes, and re-hash old signatures, because it is the same (or even worse) case than txids.
Bitcoin Message: the same solution as for signature hashes; also encourage upgrading to signet-way-of-signing-things.
Hashed public keys: old coins should be moved to the new addresses; it could be spendable or not, whatever option will win.
Hashed scripts: the same solution as for hashed public keys.
Commitments: the new chain will be started with one, huge commitment, containing the whole old chain.
Timestamps: they are invalid, new timestamps should be year-2038-resistant and year-2106-resistant, it could be modulo 2^32, but should be clearly defined, whatever it will be.

could they still be moved after the hash function change (which would be a hardfork probably)?

It could be a soft-fork if done correctly. It is just a matter of data format. We can stick to the old format, but just put more rules on top of that, making it as soft as Segwit or Taproot.

but wouldn't it be much more likely to have 160-bit collisions (from RIPEMD-160) first?

It would be. We have ASIC's for SHA-256d, we could have ASIC's for RIPEMD-160(SHA-256) faster than SHA-256 will be fully broken (they now would require 2^80 operations, but I think it could be simplified to something like 2^64, that would make it as real as SHA-1 collision).

[Kakmakr]

There are currently a few coins using the SHA-3 algorithm, namely Nexus / TERA / MaxCOIN / Bitcoin Classic / Cruzbit ...so the lessons learned from these coins will show us how successful a hard fork will be for Bitcoin (BTC) ...right?

Can something like this not be tested on a TestNet for Bitcoin (BTC) to see what impact it will have? I think Ethereum uses KECCAK-256 and it does not follow the FIPS-202 based standard?  

https://eprint.iacr.org/2019/147.pdf

Old article ...: https://www.csoonline.com/article/3256088/why-arent-we-using-sha3.html

[garlonicon]

Can something like this not be tested on a TestNet for Bitcoin (BTC) to see what impact it will have?

It can be even better than that: it is possible to store it as a SHA-3 prefix in the previous block hash. It could be backward-compatible, so that only upgraded nodes would use rehashed chain with SHA-3. Then, all nodes will be in the same network as non-upgraded nodes, no matter if it is mainnet, testnet, signet, regtest, or dragon-lives-there-network. Also, it is possible to have an activation rule, expressed as SHA-256 collision or SHA-256 preimage, things like that. We even have existing outputs with such challenges, so it is trivial to plan automatic soft-fork activation from the block, where any of such coin will be moved for the first time.

So, to sum up, you can safely run SHA-3 node on mainnet, if you do that correctly, and if you know how to make it compatible with non-upgraded nodes. It is the same case as chain compression: there are nodes that use compressed format and they are still in the same network.

[kaggie]

Can something like this not be tested on a TestNet for Bitcoin (BTC) to see what impact it will have?

It can be even better than that: it is possible to store it as a SHA-3 prefix in the previous block hash. It could be backward-compatible, so that only upgraded nodes would use rehashed chain with SHA-3.

You would have to avoid exposing the new hash with the old.
If SHA256 or RIPE hashes are compromised and the key is discovered, then that would cause SHA-anything to also be compromised if the same key is used. Nevermind that a key now has two points of failure for derivation  (although still practically impossible to discover).

For an added step, how about: all willing transactions incorporate a second key which is hashed with SHA-3 or other. The user would have to store this somehow, and the network might make sure it didn't interact with the network until ready. This separate key could be chosen by the user or in Core, perhaps derived by a longer generating key. The SHA-3 hash could be put into something like the OP_RETURN, and activated when the network was appropriate. Until the new network machinery was activated, you simply ignore these SHA-3 hashes, so it would add a byte cost, but at the chance of additional security when needed.

I doubt that you can avoid having a second network or network-in-network due to eventual changes in technologies at some point. These flaws are hopefully not too soon, and are probably on the orders of multiple decades before occurring (and if bitcoin can't last that long, crypto is hopeless). I hope that there always remain methods to choose to move into it and build naturally rather than be forced.

[Adam_xx]

Hashed public keys: old coins should be moved to the new addresses; it could be spendable or not, whatever option will win.
Hashed scripts: the same solution as for hashed public keys.

Thanks a lot for your excellent answer! What do you think would happen to L2 layers, especially LN? Would all the channels needed to be closed and re-opened again or could there be any better migration path?

[kaggie]

What do you think would happen to L2 layers, especially LN? Would all the channels needed to be closed and re-opened again or could there be any better migration path?

Don't they have to be closed anyways now when upgrading the software on a node?

[garlonicon]

What do you think would happen to L2 layers, especially LN?

If SHA-256 is broken, then you can spend all coins, where you know the public key. You can start with random ECDSA signature, and then create SHA-256 preimage. For example:

Code:

Q=03678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb6 (compressed pubkey from block zero)
z/r=SHA-256("I am not Satoshi!")=3d0e14577c6c0bbfc97644c36900bf941ba3afe23f0840017814afd320f17dcc
r/s=SHA-256("garlonicon")=272fc6644fedff1a897d6034bed23f61859e99440ee699033307976590316723
Q+(z/r)=02b13f778fffa38caffef23d236b7e7a39a22e47200a6bc310f844ecbf205fa60b
R=(Q+(z/r))*(r/s)=0299495c29155cff3bdba965ab209daab3039b4c05388d820604527ded15affb7e
r=99495c29155cff3bdba965ab209daab3039b4c05388d820604527ded15affb7e
z=(z/r)*r=3d0e14577c6c0bbfc97644c36900bf941ba3afe23f0840017814afd320f17dcc*99495c29155cff3bdba965ab209daab3039b4c05388d820604527ded15affb7e
z=abb986eeb49536362f4d845641ae21e813680b4848c1daa84a07c389a65530dc
s=(1/(r/s))*r=(1/272fc6644fedff1a897d6034bed23f61859e99440ee699033307976590316723)*99495c29155cff3bdba965ab209daab3039b4c05388d820604527ded15affb7e
s=b3c543ed385e6b8d5b15fecea33c478538200e032ecf19d28f3446f5d0802761*99495c29155cff3bdba965ab209daab3039b4c05388d820604527ded15affb7e
s=a4e2eb8ff9439df33d6e1aafecf8c35cf67a6c50fe89a343a8a0ccce222bde82
s>7fffffffffffffffffffffffffffffff5d576e7357a4501ddfe92f46681b20a0
s=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141-a4e2eb8ff9439df33d6e1aafecf8c35cf67a6c50fe89a343a8a0ccce222bde82
s=5b1d147006bc620cc291e55013073ca1c4347095b0befcf8173191beae0a62bf

So, let's assume that Satoshi created some transaction and made a signature:

Code:

Q=03678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb6
z=abb986eeb49536362f4d845641ae21e813680b4848c1daa84a07c389a65530dc
r=99495c29155cff3bdba965ab209daab3039b4c05388d820604527ded15affb7e
s=5b1d147006bc620cc291e55013073ca1c4347095b0befcf8173191beae0a62bf

All values are random, this signature is fake, because I don't know any message that can be hashed to z.

I wrote that example some time ago, but it is still valid in the context of this topic. Here, you have "z=abb986eeb49536362f4d845641ae21e813680b4848c1daa84a07c389a65530dc". As long as you don't know any transaction that can be hashed to this value, Satoshi's coins are safe. But if you can do SHA-256 preimage, then you can make such transaction, include (r;s) pair, and his coins are yours.

That means, all LN channels have to move to the new address type, when SHA-256 will be fully broken.

[Adam_xx]

Thanks for this answer, garlonicon, once again.
This is all very helpful!

Two more questions if I may:

1) As I understand quantum computers will be (Bitcoin related and if they will ever exist with enough logical qubits) a threat only to public key cryptography.
Regarding SHA-256 and Grover's algorithm - this should not effect safety of this hashing function in Bitcoin that much, am I right?

2) This will be more about your personal opinion rather than a technical explanation.

What do you think would happen to all the not-moved UTXO's (lost/forgotten/etc. coins) - or what do you think the consesus would be?
I think there would never be a consensus to freeze these coins (and it should not be IMO).
I think these coins should serve more like a honeypot for all the "hash-breakers" or quantum computers (in case of ECDSA).

[garlonicon]

1) I don't know. I don't think quantum computers will be a problem. I think there are more serious issues, like lattice attacks, that can be done on a non-quantum PC's.
2) For now, there is no consensus. No BIP's, no other proposals, just some discussions. But I expect some of them will be created, as we will get closer and closer to 128 leading zero bits in our difficulty.

I think there would never be a consensus to freeze these coins (and it should not be IMO).

If they will not be frozen, the new owner could decide to freeze them anyway, by using OP_RETURN or some unspendable (or potentially unspendable) new address. So, if our consensus will be "just do nothing", then it still depends on future actions of someone, who will move them.

I think these coins should serve more like a honeypot for all the "hash-breakers" or quantum computers (in case of ECDSA).

We already have such honeypots, for example our famous transaction puzzle. I think that kind of puzzles will be solved first, just because they are easier. For now, 64-bit hash is untouched and 120-bit public key is still not moved. Maybe some Taproot-based puzzles will be created, like this testnet3 puzzle: 448b81b2b3c2c8558d268e4f515ff38eb6367d156babbc3733a14834a5a6e7b0

[Adam_xx]

1) I don't know. I don't think quantum computers will be a problem. I think there are more serious issues, like lattice attacks, that can be done on a non-quantum PC's.

Never heard of it but a little bit of googling and it looks quite scary.
How serious do you think it could become? Can there be any countermeasures against these attacks?

[garlonicon]

How serious do you think it could become?

Quite serious, because with two signatures, 128-bit public keys can be broken. With more signatures, it gets easier and easier, so maybe it is possible to get, I don't know, 100 signatures, break 240-bit keys (or something around it), then tweak the real key 2^16 times, and you will have it.

Can there be any countermeasures against these attacks?

Yes, as usual, the whole cryptography is based on unsolved mathematical problems. If ECDSA is gone, but lattice attacks are not, then lattice-based cryptography can be used. By introducing new opcodes like OP_CHECKLATTICE instead of OP_CHECKSIG, it could be possible to solve that. Definitely breaking ECDSA is less scary than breaking SHA-256, because in that case we can still use the heaviest Proof of Work to choose the right way (and in case of breaking SHA-256, ECDSA is also gone).

[Adam_xx]

I know the form of past breaks do not imply how fast the future breaks will be.
But if the past repeats the breaks will be rather gradual than 0-day so we have hopefully enough time to migrate.
Your opinion/"hopes" on that? 

[garlonicon]

I can only guess that it will be gradual, because it was in the past.

[Adam_xx]

How hard would be to migrate these parts of Bitcoin with a minimum damage?

Porting txids: every txid should be re-hashed, just like in Segwit you have txid and hash, here you will have one more field for a new hash.
Mining: you will have two difficulties, one to preserve the old, SHA-256 chain, and the new, to keep it unaltered.
Merkle trees: each merkle tree should be re-hashed, it could be a commitment, like in Segwit, but could be also better compressed.
Block headers: you will have 80-byte new header that would contain both old and new data, in a combined and compressed form.
Signature hashes: you have to use new hashes, and re-hash old signatures, because it is the same (or even worse) case than txids.
Bitcoin Message: the same solution as for signature hashes; also encourage upgrading to signet-way-of-signing-things.
Hashed public keys: old coins should be moved to the new addresses; it could be spendable or not, whatever option will win.
Hashed scripts: the same solution as for hashed public keys.
Commitments: the new chain will be started with one, huge commitment, containing the whole old chain.
Timestamps: they are invalid, new timestamps should be year-2038-resistant and year-2106-resistant, it could be modulo 2^32, but should be clearly defined, whatever it will be.

One more question - would everything above (txids, merkle trees, signature hashes, etc.) need to be re-hashed back to the Genesis Block or the new client would rehash only the new "activity" - like from the UTXO set state at a certain point of time, from some UTXO commitment (I mean practically importing the UTXO set into the new system)? If it is back to Genesis Block and every client would need to do that, it would be computationally difficult I suppose.

[pooya87]

One more question - would everything above (txids, merkle trees, signature hashes, etc.) need to be re-hashed back to the Genesis Block or the new client would rehash only the new "activity" - like from the UTXO set state at a certain point of time, from some UTXO commitment? If it is back to Genesis Block and every client would need to do that, it would be computationally difficult I suppose.

It really comes down to what "broken" means. For example SHA1 is considered broken but you still can't reverse it or you can't find another message that produces the same hash unless you also control the initial message.
It would be the same for SHA256, if there is a chance that the content of the chain could be changed then some extreme measures needs to be taken that may include a hard fork that discards the previous chain and all its hashes and replaces it with something new.

[kaggie]

One more question - would everything above (txids, merkle trees, signature hashes, etc.) need to be re-hashed back to the Genesis Block or the new client would rehash only the new "activity" - like from the UTXO set state at a certain point of time, from some UTXO commitment (I mean practically importing the UTXO set into the new system)? If it is back to Genesis Block and every client would need to do that, it would be computationally difficult I suppose.

You could only do it back to the accepted version where everyone believed it wasn't tampered with. Before that, it's hopeless.
The benefit of validation nodes, both mining and non-mining, is that they keep this transaction history, so you wouldn't lose with the general consensus that they provide distributed throughout all of the hard disks globally.

The much bigger problem is really one of culture and politics. If SHA-256 was broken, would you be able to convince all of the previously invested interests to invest in a new system - if it wasn't already built in? I doubt that there would be a quick consensus about what the new system would be. It would take a long time to recover.