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

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

Quote from: kaggie on April 14, 2022, 12:14:00 PM

2009 was a dead year for near anything but software development. It wasn't a large ecosystem.

And no one outside cryptographic communities was having any idea of how a cryptocurrency would even work. Those who invested time and money had made their research, had cleared out confusions and misconceptions etc. They'd convinced themselves.

Indeed, it's a much larger ecosystem today. If one had found a way to break SHA-256, it'd be a matter of time until Bitcoin lost its purpose. I don't think there could be a way to correct the situation; it's an absolutely fucked up scenario. But, it's highly unlikely to happen overnight.

Quote from: kaggie on April 14, 2022, 12:14:00 PM

You would have havoc everywhere, with bitcoin being the smallest of concerns now.

Not a small-scale concern. As said, it's a large ecosystem now. It'd probably be one of the top concerns along with national security and online banking.

Adam_xx

jr. member

Activity: 34

Merit: 35

My question was more about what would have to be changed if it occurs gradually, not overnight.

Quote

2) We have 10 years to migrate (we know the attacks will be possible but will come gradually, not overnight)

kaggie

sr. member

Activity: 333

Merit: 506

Quote from: BlackHatCoiner on April 14, 2022, 11:45:54 AM

Quote from: kaggie on April 14, 2022, 10:48:12 AM

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?

Did the developers convince them invest into it back in 2009?

2009 was a dead year for near anything but software development. It wasn't a large ecosystem.

Quote from: BlackHatCoiner on April 14, 2022, 11:45:54 AM

So, why should they expect a conviction now?

It's a larger ecosystem. You'd have schisms and splits. You'd not regain the trust that has been built up until now if there was a flaw that occurred rapidly. What you describe next would happen:

Quote from: BlackHatCoiner on April 14, 2022, 11:45:54 AM

If SHA-256 became broken, right now, a chaos would prevail. Besides Bitcoin and other PoW cryptos that wouldn't be able to prevent double-spending in that case, software's integrity verification, passwords and encrypted messages that use SHA-256 could all be altered and read.

That was the point I was trying to make. You would have havoc everywhere, with bitcoin being the smallest of concerns now. On top of that, you'd have large cultural shifts into many different factions of currencies. You'd lose a major coin and the benefit that brings (like increasing stability). It would take time to recover, which it never would into the exact same thing.

BlackHatCoiner

legendary

Activity: 1512

Merit: 7340

Farewell, Leo

Quote from: kaggie on April 14, 2022, 10:48:12 AM

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?

Did the developers convince them invest into it back in 2009? No, they entered the system at their own will; they had convinced themselves that it's worth the money. So, why should they expect a conviction now?

If SHA-256 became broken, right now, a chaos would prevail. Besides Bitcoin and other PoW cryptos that wouldn't be able to prevent double-spending in that case, software's integrity verification, passwords and encrypted messages that use SHA-256 could all be altered and read.

kaggie

sr. member

Activity: 333

Merit: 506

Quote from: Adam_xx on April 14, 2022, 01:19:56 AM

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.

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: Adam_xx on April 14, 2022, 01:19:56 AM

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.

Adam_xx

jr. member

Activity: 34

Merit: 35

Quote from: garlonicon on April 07, 2022, 02:50:28 PM

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.

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.

garlonicon

copper member

Activity: 821

Merit: 1992

Pawns are the soul of chess

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

Adam_xx

jr. member

Activity: 34

Merit: 35

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

copper member

Activity: 821

Merit: 1992

Pawns are the soul of chess

Quote

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.

Quote

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

jr. member

Activity: 34

Merit: 35

Quote from: garlonicon on April 09, 2022, 02:14:30 PM

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

copper member

Activity: 821

Merit: 1992

Pawns are the soul of chess

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.

Quote

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.

Quote

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

jr. member

Activity: 34

Merit: 35

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

copper member

Activity: 821

Merit: 1992

Pawns are the soul of chess

Quote

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:

Quote

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.

ABCbits

legendary

Activity: 2870

Merit: 7490

Crypto Swap Exchange

Quote from: kaggie on April 09, 2022, 02:59:46 AM

Quote from: Adam_xx on April 09, 2022, 01:47:31 AM

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?

When you upgrade your wallet/node, it's not necessary to close your LN channel. You could utilize LN watchtower to prevent another party cheating. Regardless, people migrate at different time so it's not like total LN channel/node/capacity drastically reduced shortly after the update is available.

kaggie

sr. member

Activity: 333

Merit: 506

Quote from: Adam_xx on April 09, 2022, 01:47:31 AM

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?

Adam_xx

jr. member

Activity: 34

Merit: 35

Quote from: garlonicon on April 07, 2022, 02:50:28 PM

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

sr. member

Activity: 333

Merit: 506

Quote from: garlonicon on April 08, 2022, 08:59:08 AM

Quote

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.

garlonicon

copper member

Activity: 821

Merit: 1992

Pawns are the soul of chess

Quote

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.

Kakmakr

legendary

Activity: 3514

Merit: 1963

Leading Crypto Sports Betting & Casino Platform

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

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