Contingency plans

[TierNolan]

On the wiki, there are various contingency plans.

The 2 big ones are ECDSA break and SHA-256 break.

SHA256 break

    Attacker may be able to defeat OP_CHECKSIG, which hashes transactions before signing

If the hash_type in signatures to select an alternative hashing function.  If SHA was broken, nodes could switch to RIPEMD instead.

I think this has to be a hard fork though.  You have to run at least one of the SHA-256 signatures.

Maybe certain hash types could consume 2 signatures.  If the MSB is set in a signature, it means the two signatures are provided. 

It still only pops one of them though.  That means that it is a soft fork.

Code:

[ <sig-RIPEMD:0x01> <sig-Sha256:0x91> <public-key ] [ OP_DUP OP_HASH160 <hash160(public-key)> OP_EQUAL_VERIFY OP_CHECKSIG ]

For multi-sig, it would have to be 2 sets of signatures, to maintain backward compatibility.

This would work for standard transactions, but transactions which take advantage of non-standard scripts might be unprotected.   

This is worth it, even if it only protects some of them.

    Attacker may be able to split the network by creating identical transactions or blocks with the same hashes.
    Attacker may be able to create blocks very quickly.

Ideally, two separate hashing functions would be used.  This is a hard-fork though.

It also breaks ASICS.

If the function is

- Hash1(Hash2(header))

and Hash1 is broken, then an attacker can create lots of blocks with the same hash.

Maybe, create something like

H1 = Hash1(message)
H2 = Hash2(message)

H_combined = bit_interleave(H1, H2)

If 1 Hash function is secure and the other just "scrambles", I think you still get the full POW protection.

When a hash function is broken, you have to be able to tweak the message.  There would be no way to allow that, since it would cause the other hash function to effectively generate random bits. 

    The alert system may be compromised.

Alerts could be updated to be signed twice with 2 different hashing functions.

[Code for all of this should be prepared.]

Has that been prepared?

ECDSA Break

    Attacker can spend money that is not his in a large number of cases. Transactions to addresses that have never been used before may be protected if SHA-256 and RIPEMD-160 are still strong.

For addresses that have never been used, a formal process could be created.

- sign the transaction with ECDSA
- txid:index and hash(signature) as OP_RETURNs
- Wait 100+ blocks
- submit transaction that spends the output

This has potential DOS problems though.

    Alert system may be compromised.

Alert could be updated to use 2 different signing algorithms.

The reserved field in the alert message could be used.

Assuming the RSA algorithm was used as the 2nd algorithm, the reserved field would need to include
- ECDSA + RIPEMD160 signature
- RSA + SHA256 signature
- RSA + RIPEMD160 signature

The altert would be protected unless either both signing algorithms were broken or both hashing algorithms were broken.

For quantum protection, the 2nd signing system could be Lambert signatures.  An alert could be sent to update the Lambert merkle root, if the number of public keys is exhausted.  This updated alert could be added to the blockchain as an OP_RETURN.

[telepatheic]

I think the thing you are forgetting is that these protocols (ECDSA, SHA256) are highly unlikely to fail completely. It is much more likely that their security will be shown to be reduced slightly as we have seen with other protocols (MD5, RC4), that will give developers more than enough time to come up with a plan to change to a more secure option. (Indeed RC4 and MD5 are still widely used on the internet despite their modest security).

If ECDSA or SHA256 were to fail completely, there would be many more problems than just bitcoin failing, most of the internet would become insecure. Even switching to other protocols may not help depending on the type of vulnerability found. No one way function has been mathematically proven except under the assumption that P!== NP

There is no real need right now to worry about the low level cryptography, when the main challenge bitcoin faces is securing wallets in a reliable and fail safe way that everyone can use.

[TierNolan]

There is no real need right now to worry about the low level cryptography, when the main challenge bitcoin faces is securing wallets in a reliable and fail safe way that everyone can use.

The MD5 break requires that you can control 128 bytes in a row.  Since the bitcoin header is only 80 bytes, even MD5 would still be fine for header chain/POW hash.

It could break the merkle trees though.

I think hardening the alert system is worth doing.  If there was a break to the alert system, then it makes communication with nodes harder.

It doesn't cost much anyway, since alerts aren't sent very often.

Having code to handle breaks more safely would give time to update all the clients rather than the network having to go into emergency mode and have a few weeks of no transactions being possible.

[jonald_fyookball]

which one seems less likely to break?

To me, SHA-256 seems less likely.

[DeathAndTaxes]

which one seems less likely to break?

To me, SHA-256 seems less likely.

Public key systems generally speaking are weakened faster due to cryptanalysis.   They rely on certain operations being infeasible and the study of mathematics is not complete. As people discover new algorithms which are more efficient the effective security of the system is reduced.

RIPEMD-160 and SHA-256 are well understood Merkle–Damgard designs which have been extensively studied for over a decade.  So I believe ECDSA will be weakened long before either of the hashing algorithms.

[jonald_fyookball]

which one seems less likely to break?

To me, SHA-256 seems less likely.

Public key systems generally speaking are weakened faster due to cryptanalysis.   They rely on certain operations being infeasible and the study of mathematics is not complete. As people discover new algorithms which are more efficient the effective security of the system is reduced.

RIPEMD-160 and SHA-256 are well understood Merkle–Damgard designs which have been extensively studied for over a decade.  So I believe ECDSA will be weakened long before either of the hashing algorithms.

Basically, you're repeating what I just said. 

[DeathAndTaxes]

Ideally, two separate hashing functions would be used.  This is a hard-fork though.

It also breaks ASICS.

If the function is

- Hash1(Hash2(header))

Backwards compatibility with existing ASIC hardware can be preserved.   Due to mining looking for a set of possible valid block hashes it is unlikely any public weakness in SHA-256 would break the proof of work.  If the weakness allowed faster hashing (unlikely) it could just be seen as an optimization of the hashing algorithm.   All ASIC designers would quickly incorporate this and we would see something similar to the first ASIC "gold rush" all over again.  Any private weakness in SHA-256 would be undetectable from a conventional very fast attacker.

The larger issue isn't that miners could make blocks faster, it is they could produce a collision with an existing block.   The blockchain assumes that the prior block hash in every block only corresponds to one and only one block solution.  If there are two block A & B which have the same hash which one is the legit one.

Luckily that problem can be solved in a backwards compatible way.   Modify the header to contain a new block hash (say SHA-3).  The prior block hash after a certain block will refer not to the proof of work hash but this "inner" identity hash.  Now hash the header using SHA-256.  ASICs are optimizes to essentially hash a "blob" plus nonce.   They have no idea what the blob represents.  SHA-256 hashes one block (512 bits) of input at a time.  The header is already larger than 512 bits so the first portion of the header is hashed outside the ASIC (usually at the pool server).   Due to block design the header could be extended in increments of 512 bits to be as long as needed.  Instead of providing the ASIC an H0 which represents the output of the SHA-256 function for the first 512 bits it could be the output of the first 1,024 bits (or more).

The block would have two different hashing functions
a) identity hash (an unweakened hash stored in the header which is referenced by future blocks in the prior block hash header element)
b) proof of work hash (SHA-256 to maintain backwards compatibility with deployed hardware = security)

In SHA-256 is weakened sufficiently then merkle tree and tx hashes are almost vulnerable to preimage attack however they could be replaced with more secure hashing function without breaking backwards compatibility.

[TierNolan]

In SHA-256 is weakened sufficiently then merkle tree and tx hashes are almost vulnerable to preimage attack however they could be replaced with more secure hashing function without breaking backwards compatibility.

It depends on how you define backward compatibility.

The suggestion to have the alert signed 4 ways (2 hashes and 2 signature algorithms) is completely backward compatible.  Old clients will accept the new alerts, they just won't be as secure.

Changing the chain formation system requires a hard fork.  Old clients will no longer be on the main chain.

With ASICs there could be a delay until the new hashing algorithm was used.  If a year's notice was given, then most ASICs would have time to update.  1 year old ASICs are pretty obsolete, so there would be little loss.

If SHA-256 was broken but the double version was not, then giving time for the update would be reasonable.  The same would apply if a weakness was found in SHA-256, even if it wasn't fully broken.  If it took 2^224 steps instead of 2^256 steps to find a preimage, then that is still pretty secure.

[jonald_fyookball]

What are these so called alerts and how are they being used currently? Thanks.

[DeathAndTaxes]

In SHA-256 is weakened sufficiently then merkle tree and tx hashes are almost vulnerable to preimage attack however they could be replaced with more secure hashing function without breaking backwards compatibility.

It depends on how you define backward compatibility.

Sorry I was just speaking about mining (proof of work) meaning that replacement of other uses of SHA-256 is easier as there is no hardware compatibility to worry about.

With ASICs there could be a delay until the new hashing algorithm was used.  If a year's notice was given, then most ASICs would have time to update.  1 year old ASICs are pretty obsolete, so there would be little loss.

I don't think hardware compatibility will be broken.  Also improvements to mining hardware will decline one all developers are on the current process node, the hardware becomes commoditized, and margins decline.  The largest component of lifecycle cost will become energy and process node improvements are showing declining improvement in work/J.  In the future the ammortized life of hardware may be measured in years.   Also ASIC developers will have significant sunk cost in terms of chip design and will be reluctant to give that up.   Speaking pragmatically I find it very unlikely a consensus will be formed around changing the proof of work. 

The good news is that a degraded hash doesn't compromise proof of work because the difficulty of mining is already many magnitudes below what is considered cryptographically secure.  Miners aren't looking for a specific preimage any hash in the set of hashes smaller than the target.  At current difficulty mining is just as "easy" as breaking a 64 bit hash.  Even if SHA-256 is "weakened" (I don't like term broken as it implies a binary scenario) the most probable scenarios is that it is weakened to a point which is still harder to find a preimage than it is to find a hash below the target.

However as I pointed out if SHA-256 was weakened to a point where it became possible to preimage the hash of a block, transaction, or alert message then instead of trying to double spend by performing a 51% attack one could double spend by replacing a tx or block that is already within the blockchain.  So those hashes would need to be upgraded.  By separating the identity purpose and proof of work purposes for the block hash you could maintain backwards compatibility with existing hardware.

[DeathAndTaxes]

What are these so called alerts and how are they being used currently? Thanks.

They are messages which can be sent to all clients alerting them of security issues.  It was most recently used in the 2013 chain fork and in the 2014 Heartbleed vulnerability to warn users they need to upgrade.   To prevent anyone from spamming the network with false messages the alert messages are signed by a private key known to the developers and verified against a public key hardcoded in the client.

[TierNolan]

What are these so called alerts and how are they being used currently? Thanks.

The dev team can send messages to all clients with warnings etc.

If the hashing algorithm or ECDSA is broken, then the alert system is also (potentially) broken.

The break creates an emergency and also makes it hard to send notifications to users.  They could be spammed with false alerts.

I don't think hardware compatibility will be broken.  Also improvements to mining hardware will decline one all developers are on the current process node, the hardware becomes commoditized, and margins decline.  The largest component of lifecycle cost will become energy and process node improvements are showing declining improvement in work/J.  In the future the ammortized life of hardware may be measured in years.   Also ASIC developers will have significant sunk cost in terms of chip design and will be reluctant to give that up.   Speaking pragmatically I find it very unlikely a consensus will be formed around changing the proof of work.  

I think if SHA-256 was shown to be massively weakened, then ASIC manufacturers may have difficulty blocking changes.

The good news is that a degraded hash doesn't compromise proof of work because the difficulty of mining is already many magnitudes below what is considered cryptographically secure.  Miners aren't looking for a specific preimage any hash in the set of hashes smaller than the target.

It depends.  The attack might also make the POW task easier.  A preimage means all bits match, but trying to find a reduced number of bits could easier.

It might still be OK though.  There would be block spam and then it would settle at a higher difficulty.

The real break would be if a full preimage was to easy.

A big break would likely obsolete all current hardward anyway.  There could be a short period where CPU/GPU mining took off again.

However as I pointed out if SHA-256 was weakened to a point where it became possible to preimage the hash of a block, transaction, or alert message then instead of trying to double spend by performing a 51% attack one could double spend by replacing a tx or block that is already within the blockchain.  So those hashes would need to be upgraded.  By separating the identity purpose and proof of work purposes for the block hash you could maintain backwards compatibility with existing hardware.

Fair enough.

[jonald_fyookball]

What are these so called alerts and how are they being used currently? Thanks.

The dev team can send messages to all clients with warnings etc.

If the hashing algorithm or ECDSA is broken, then the alert system is also (potentially) broken.

The break creates an emergency and also makes it hard to send notifications to users.  They could be spammed with false alerts.

Is it a high priority to fix?  What should we do?

[justusranvier]

    Attacker may be able to defeat OP_CHECKSIG, which hashes transactions before signing

If the hash_type in signatures to select an alternative hashing function.  If SHA was broken, nodes could switch to RIPEMD instead.

I think this has to be a hard fork though.  You have to run at least one of the SHA-256 signatures.

Maybe certain hash types could consume 2 signatures.  If the MSB is set in a signature, it means the two signatures are provided.

I'd suggest a hard fork where you make OP_CHECKSIG consume an additional stack item which represents the algorithm type. This would make the future upgrades which add new signature types less disruptive.

At the same time, make the clients use P2SH by default so that the extra space the new parameter consumes stays out of the UTXO set.

[gmaxwell]

check multsig is already designed that way. But even ignoring that I think a hardfork to increase some speculative flexibility against speculative attacks would be a very poorly justified risk. New signature algorithms can happily be deployed in soft forks (e.g. how P2SH effectively replaced the scripting system in a soft fork).

[theymos]

I think hardening the alert system is worth doing.  If there was a break to the alert system, then it makes communication with nodes harder.

The Contingency Plans page is is somewhat out of date. The alert system can now be deactivated by sending a special alert message. So in the worst-case scenario where ECDSA or SHA-256 is broken and the alert key is compromised, the alert message will quickly be changed to say, "URGENT: Alert key compromised, upgrade required," and then no more alerts will be possible.