40. On the Possibility of a Cryptographic Weakness

40

On the Possibility of a Cryptographic Weakness

SEVERAL THREADS covered different issues to which Satoshi suggested the same solution. Two of the threads below concern SHA-256, which is the cryptographic hash function used to create the “message digest” of the blocks used as the public ledger, each containing a set of bitcoin transactions. SHA-256 is used by the banking industry and other financial institutions. Were any weaknesses to one day be discovered in this encryption method, it would affect the whole financial industry, which would then be forced to change over to a new method. Satoshi suggests the same policy for Bitcoin.

The second thread was in regard to the discovery of a major cryptographic weakness. At first, Satoshi refers to his earlier post on SHA-256 Collisions, but user llama specifies the case where a major weakness is discovered in the elliptic curve cryptographic code that is used for the Bitcoin private key.

Re: Dealing with SHA-256 Collisions

Satoshi Nakamoto June 14, 2010, 08:39:50 AM

Quote from: lachesis on June 14, 2010, 01:01:11 AM

A mathematician friend of mine pointed out that there arevery few if any hash protocols that have survived for 10 years or more. What would Bitcoin’s solution be if SHA256 were to be cracked tomorrow?

SHA-256 is very strong. It’s not like the incremental step from MD5 to SHA1. It can last several decades unless there’s some massive breakthrough attack.

If SHA-256 became completely broken, I think we could come to some agreement about what the honest block chain was beforethe 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.

Re: Major Meltdown

Satoshi Nakamoto July 10, 2010, 04:26:01 PM

Quote from: llama on July 01, 2010, 10:21:47 PM

Satoshi, That would indeed be a solution if SHA was broken (certainly the more likely meltdown), because we could still recognize valid money owners by their signature (their private key would still be secure).

However, if something happened and the signatures were compromised (perhaps integer factorization is solved, quantum computers?), then even agreeing upon the last valid block would be worthless.

True, if it happened suddenly. If it happens gradually, we can still transition to something stronger. When you run the upgraded software for the first time, it would re-sign all your money withthe new stronger signature algorithm. (by creating a transaction sending the money to yourself with the stronger sig)

Re: Hash() function not secure

Satoshi Nakamoto July 16, 2010, 04:13:53 PM

SHA256 is not like the step from 128 bit to 160 bit.

To use an analogy, it’s more like the step from 32-bit to 64-bit address space. We quickly ran out of address space with 16-bit computers, we ran out of address space with 32-bit computers at4GB, that doesn’t mean we’re going to run out again with 64-bit anytime soon.

SHA256 is not going to be broken by Moore’s law computational improvements in our lifetimes. If it’s going to get broken, it’ll be by some breakthrough cracking method. An attack that could so thoroughly vanquish SHA256 to bring it within computationally tractable range has a good chance of clobbering SHA512 too.

If we see a weakness in SHA256 coming gradually, we can transition to a new hash function after a certain block number. Everyone would have to upgrade their software by that block number. The new software would keep a new hash of all the old blocks to make sure they’re not replaced with another block with the same old hash.