Pages:
Author

Topic: What needs to be changed when SHA-256 is broken? - page 3. (Read 438 times)

copper member
Activity: 821
Merit: 1992
Pawns are the soul of chess
Quote
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.

Quote
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.

Quote
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.

Quote
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.

Quote
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 " OP_DROP 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.

Quote
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.

Quote
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.

Quote
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).
legendary
Activity: 1512
Merit: 7340
Farewell, Leo
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.
sr. member
Activity: 333
Merit: 506
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.
legendary
Activity: 1512
Merit: 7340
Farewell, Leo
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.
jr. member
Activity: 34
Merit: 35
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!
Pages:
Jump to: