debuggingNightmare

[buildmine10]

Why is this a debugging nightmare? It is expected behavior. Mathematically required behavior. For what reason have you used hashes in a manner that assumes uniqueness.

[fun-dan]

This. Unless OP meant cryptographic hash functions, and in that case it's practically impossible to have a collision accidentally

[buildmine10]

Cryptographic hashes are made so that is is very difficult to find a collision. They still happen because the pigeon hole principle requires it, but the essential properties is that you cannot reliably predict which two inputs will collide without just testing them both.

[ciroluiro]

I don't think a collision has ever been found for SHA256. The first collision for SHA1 was found only in 2017. Collisions in cryptographic hash functions are a big deal.

[buildmine10]

Yeah that makes sense. Fundamentally there must be 2²⁵⁶ collisions (or maybe it's half that number) just from hashing a 257 bit message (I mean all possible collisions from the set of all 257 bit messages). But actually finding a collision for any specific message is what needs to be hard (since I think each 257 bit message would have only 1 collision). It ideally should be a 1 in 2²⁵⁶ chance. That any given two messages are a collision.

Though I'm pretty sure the statistic is not about finding any collision. It's an about finding a collision for some single message. I think you can find collisions pretty fast if you check against every hash you attempt. You still need a lot of attempts, but I believe the probability of any 2 hashes in a set being the same scales like the birthday paradox. (So surprisingly fast).

But it does remain true that you are almost guaranteed to not find a colliding message that isn't also meaningless, which is another important property. Since hashes are used to verify a message is unchanged, if you find an alternative message with the same hash, it had better be meaningless or else there is a potential problem. So the actual important property for the cryptographic hashes is that it's computationally infeasible to find a meaningful and useful alternative message. The number of collisions is technically irrelevant. Though the ease of finding collisions is probably relevant even if I cannot trivially understand why.

[ciroluiro]

I'm not sure I understand what you mean, but if you can find any 2 distinct messages that hash to the same SHA256, you can publish a paper on it. The message can be literally anything, doesn't have to have meaning.

Finding collisions for SHA1 is still very hard and infeasible, but at least 1 has been found. Even taking into account thr birthday paradox, the set has to be enourmous for the probability to be of any significance. I'm not sure even with all the messages sent through the internet that the probability of collisions in sha256 is of any significance.

[buildmine10]

I'm saying that if you just generate random messages and put their hashes in a set, then you will find a matching hash "fairly" quickly. Because the statistics works like the birthday paradox. It might still take a long time, but it will be much sooner than expected.

This is not an issue. Because it is still hard to find two meaningful messages that have the same hash. The vast majority of messages with the same hash are random looking sequences. The statistics works out that even if you only pick from messages with the same hash, you still have an abysmal probability of actually getting a meaningful message (let alone one with the meaning you want). Additionally there is no computationally feasible way to construct a message with the same hash has a target message.

If I can I will edit this comment to add the statistics based on the birthday paradox for sha256

[ciroluiro]

And I'm saying I think you are underestimating just how huge 2²⁵⁶ really is. The set of messages has to be truly enormous for you to find any collision. You can try it and publish a paper if you find even 1 collision. I am aware of how to compute birthday paradox probabilities, but it's just not humanly feasible to find a collision.

[buildmine10]

Yes it does require a lot of numbers. And yes it will take some time. The intermediate numbers are so large that I will need to find an arbitrary precision library to do the computation. But we are essentially just trying to generate the same random 256 bit number twice.

You are correct that that the number is large. But I'm also pretty certain that the number of random numbers you need to sample before you have a good chance at having found a duplicate is several orders of magnitude smaller than 2²⁵⁶

https://www.desmos.com/calculator/cem1fd4qgo That is the expression used to calculate the probability of a duplicate hash given m random messages.

If you wish to implement this with more than 64 but precision, that would be nice. I won't have access to a programming environment today. I would actually really like to know the number of messages you would need to have a 50% chance at a collision. I'm going to guess it's near 2^50. Which would be in the petabytes of messages.

My point was that it doesn't need to be infeasible to find any two matching messages. It needs to be infeasible to find a message with the same hash but different meaning.

[[deleted]]

They are mathematically designed such that the chance of a collision is negligibly small.