Topic: Why rely on a single hash function? (Read 607 times)

Although I'm not a mathematician but that's not what he proved. He proved that in any mathematical system there are some statements that are considered true but can not be proven. Not that everything that is true such as basic math could be false! That would be crazy talk.

We know today that reversing hashes is impossible and will always be. If you know that the hash is 4, and your hash function is mod10, then you can use 4, 14, 24, 34, 44, ..., and you will never know, which value was hashed. You could know that only in one case: if you would know some properties of the hashed data. So, if you know that some ASCII string is hashed, then it may be possible to prove that this particular 256-bit hash will only match "Hello World", because nothing else is matching ASCII values (or nothing else is in your "dictionary"), and you can try to prove that, based on context. But if something is totally random, for example some private key, some signature nonce, things like that, then you will never know, what was really hashed, and what was recovered as a second preimage.

I think the answer is quite simple: because using two or more hash functions can make the system more complex, and will not make it more secure at the same time, so it is not worth it. But as I described, you can do it yourself, if you really want. You can implement it, you can promote it, you can convince people to switch to things like that, but I think the consensus will be formed around single hash function, unless something serious will be broken (or will show some serious weakness). Also, to add something more to SHA-256, you have to know, how it can be attacked, because you don't want to add mod10 and other useless hash functions when they are not needed and can be as "broken" as SHA-256, so it may turn out that for example SHA-3 is even worse in case of some particular attack vector, that's why it should be attack-vector-based, and not randomly picked.

Well, 90 years ago Kurt Gödel proved such absolute statements are false.

That said - and thanks to bitcoin - we would never know if one is capable to easy reverse hashes. If NSA and similar cannot do it yet, then they would never be able to. Anybody coming close to an answer would be very incentivized to keep it to himself, and never ever share.

Simply because you won't be able to generate hashes like these just like that. There has never ever been any attacks which allows users to find pre-image in this manner.

You can do that, but the community won't recognize your chain as valid. It is quite obvious which chain to follow.

As I've mentioned, the manner which the topic postulates SHA-256 to be broken seems to suggest a catastrophic failure of it and for which I'm inclined to believe that the only scenario that happens is when all the other algorithms are also broken. Speed ups in the PoW is counter-acted by difficulty increase, at best there would be a minor reduction in the complexity of pre-image but not financially sensible enough to exploit it.

I think there is a clear distinction between what should be classified as a point of failure, which in this case is how the algorithm can become insecure. I don't doubt that SHA-256 would eventually be broken, but what I do doubt is that it would be broken in this manner. The most likely scenario is that we would recognize its weakness decades in advance and when it finally becomes (remotely) feasible, then we would've long shifted from using SHA256 as the PoW algorithm.

Why would the latter not be possible? Assuming that I can mine essentially for free, I can just re-create a version of the full blockchain, keeping all transactions identical to the original, except for the destination address in some coinbase transactions (those which are attributed to Satoshi in the original chain). Not sure what would prevent me from doing this.


Ok, but breaking SHA-256 would not imply that one-way functions don't exist (and neither would breaking ten or a hundred different hash functions).

Anyway, it still seems to me that there is a lot (too much) riding on the fact that SHA-256 will not be broken, or if so, that it would be broken in a slow, and visible fashion. I am quite surprised by this, seeing as Bitcoin's main tenet is immutability guaranteed by PoW, which falls apart in case of a break. Admittedly I don't know anything about cryptography, but the single point of failure strikes me as strange.

We are all eagerly awaiting your math proof of P != NP...

Most of the applications of cryptography in real life requires the property of it having to have a certain degree of pre-image resistance. If that were to be broken, the hash is no longer a one way function, to which it becomes useless for certain real-life applications. Even before that, we have the collision resistance being broken, which already means that the hash function wouldn't be very useful for sensitive operations.
The latter is not possible. As for the former, if you were to approach NSA or related organizations directly, you would probably have a guaranteed payout rather than to attack the chain and risk being labelled a criminal and getting yourself investigated. You'd probably have much better things to do if you could discover a feasible way to generate collisions anyways (at low costs of course).

Anyways, current resistance is still sufficiently high and that is expected for the near future.
Because historically well studied algorithms has never been broken with very little computational power/efforts. If you were to prove that one-way function don't exist, ie. P=NP, then any other cryptography functions would also be dead.
Proving P=NP would be sufficient to prove SHA256 is not a one-way function.

Nope. That is just not what ASICs do.

Then a concrete proof would be good, either that of a past algorithm that has been broken or any theoretical attacks.
You can't really do much once you prove P=NP.

It is and it will always be impossible to reverse hashes until the end of time, this is even true for non-cryptographic hash functions like MurmurHash. That's for a very simple reason: math.

To put simply if I told you I had a two digit number and I added its digits to get 10 you will not be able to figure out what that number was until the end of time. You can guess other numbers that give the same result like 10 or 46 or 55,... (ie. find collision) but you will never be able to "reverse" the operation to know what number I really used.

Now imagine if the result (10) wasn't so small and was 256 bit instead and I wasn't just doing x+y and was doing a lot more operations to get the final result. That's what happens in a hash function. Due to chaotic and irreversible nature of each operation it is never going to be possible to reverse it.

i think you might be assuming sha256 is a one-way function. it might not be. and thus there could be an easy way to reverse it that no one ever though of yet.

maybe their approach was just less than optimal.

Not sure about that.

they would just need to use something more secure.

Why would all of cryptography be dead if this was possible for a specific hash function?

1. Would it be useful in other contexts to be able to find "small enough" hashes?
2. Perhaps there are other very valuable uses, but Bitcoin does have half a trillion market cap. You could for example place a gigantic leveraged short on BTCUSD just before publishing your proof that SHA-256 is broken. Or you could rebuild the chain unchanged except for reassigning the Satoshi wallet to yourself.

Thanks! Most of your post is going straight over my head, so I will invest in self-study to try and understand it. But from what I gather in your no-fork proposal, you are saying that I could be (privately) building a parallel chain with alternative hash function, and accumulating some Proof-of-Work in that, which could be used as a bootstrap if a sudden break of SHA-256 appeared, correct? If so, I guess that is an interesting point to consider, although it would basically mean that this work would go unrewarded by the network, and hence likely the accumulated PoW could only be very small, and would not last long vs. an adversary who had the means to break SHA-256.

Good point, I did not define "broken" with any degree of precision. In this context I would call SHA-256 broken if someone is able to find valid block hashes with a much decreased amount of work compared to brute force. If I understand correctly from my Wikipedia readings, breaking pre-image resistance would entail the ability to create a block for any desired hash value, whereas what I refer to is a weaker condition, i.e. finding a block whose hash value is small enough.

Concerning the point of replacing vs. creating a band-aid. I am thinking of scenarios in which it is not apparent that someone has managed to "break" the algo, until it is revealed in a catastrophic fashion when a longer chain is published as an adversarial attack on the Bitcoin network (resulting in sudden destruction of trust and collapse of price), at which point it may be too late to operate a replacement.

Actually NotATether brought up quite an interesting point that I actually didn't consider.

Any reduction in the complexity of SHA256 either requires a very specific set of hardware or just your regular GPU clusters which allows you to parallelize your calculations. ASICs are unfortunately too specific for this. Pre-image attacks are actually not very common still, I know MD2 was cracked but that required an enormous amount of memory and huge computational resources. You must realize that the complexity reduction of those are not significant enough, MD2 being 2^73[1] with varying memory requirements. In fact, SHA hasn't even been cracked yet, to any extent within the realm of feasibility.

There is no such thing as producing a valid block hash with little computations, that is not within our reach for the near future. If that happens, you can be sure that cryptography is dead.


[1] https://eprint.iacr.org/2008/089.pdf

not sure what you're addressing. i was saying it sha256 got cracked, then that would obselete mining hardware from cpus to gpus to asics, everything.

But would the cost be economical for mining farms to consider? After all, they aready have the headache of maximizing profits out of the thin margins of hashpower vs. difficulty. It is unlikely theyhave much cash wiggle-room to rent several hundreds of CPUs (the attacks cannot be carried out on ASICs) for a computation which may not hit a block in time. And if there was any such warning that this is what they were doing (we'd hear roumors and leaks from the news), then the community would act quickly and deploy a BIP + soft-fork with another algorithm instead.

There's no difference between this and newer/more ASICs coming online. You can argue that someone might start mining all of the blocks but even that is unlikely because any breakthrough takes years to progress and SHA256 wouldn't possibly be broken overnight.

interblock times would go down if it had been broken. such that they always beat everyone else to the punch. so that's how you can detect it.

No way of knowing which miners mined which blocks. The only reason you know certain pools are mining blocks is because they explicitly state it in their coinbase. Otherwise, you actually cannot tell them apart and any analysis can be defeated relatively easily (randomized nonce, timestamps, coinbase, etc).

Also defeating (not weaken) SHA256 or any cryptography like that is quite valuable, certainly not valuable enough to use on Bitcoin.

IIRC SHA1 was considered insecure 2 decades ago or thereabout. The attacks were only somewhat practical fairly recently and even so they incurred quite a high cost and time.

The risks of different attacks on all cryptography algorithms are always present but we usually have a pretty good idea about cost of different attacks and the estimation is in the ballpark specially for solid old algorithms such as SHA256. This is why SHA1 was removed from a lot of places where it was used a long time before the successful attack was demonstrated by Google.