[Contentless] ITT you post right now [ASAP] your current thought [Brains][Thinking][Personal][#20] (999)

588 Name: i L_T`j : 1993-09-8256 00:27

Have they actually tested handling of hash collisions?

589 Name: (*ﾟーﾟ) : 1993-09-8256 01:27

>>588
I was wondering that too, so I looked into it. Unless the algorithm that designates that hash is just prone to collision, then the 32 byte hash should make it statistically unlikely that a collision would occur. There are 2^256 = 1.16e77 possible hashes. Say that hashes were generated every millisecond, then you would use all the hashes at 1.16e77ms*(1s/1000ms)*(1min/60s)*(1hr/60min)*(1day/24hours)*(1year/365days)*(1(age of the universe)/(13.8e9years)) = 2.67e56(age of the universe). But if there are reasons to be concerned about hash collision other than the size of the hash, I'm not aware of them.

590 Name: (*ﾟーﾟ) : 1993-09-8256 01:46

>>589
Also, there should be someway to calculate the probability of a collision happening within in one age of the universe using the birthday paradox, but I'm not smart enough to do that.

594 Name: i L_T`j : 1993-09-8256 10:03

>>589
>>590
That's not very reassuring. We used to think md5sum was good. Now we don't, and we've known how to create collisions for it for a decade (http://www.mathstat.dal.ca/~selinger/md5collision/). SHA-1 is a 160-bit hash that we used to think was good. We now have (kinda) collision generation for it (https://eprint.iacr.org/2015/967 - read the Recommendations at https://sites.google.com/site/itstheshappening/ for a good overview of where on the enot goodf scale it falls).

To invoke the birthday paradox as you requested, the average time before A Bad Thing is given by the time to generate 2^(256/2) hashes for a 256-bit sum. Using your calculations, it's ~1e17 * AOU. Note that the same calculations for SHA-1 yield ~3e4 * AOU, and SHA-1 is considered unsafe. Even the humble md5sum yields ~0.04 * AOU, and I can generate a collision in seven minutes on a five year old personal computer (http://www.mathstat.dal.ca/~selinger/md5collision/).

Who is to say that their hash function will never be enot goodf? Is there a way of sanely upgrading the infrastructure to use a different hash function later?

Alternately, there could be a very good reason why the hash can't be exploited. Git's design makes hash collisions only detrimental to the collider (you can't use a SHA-1 collision to send a poison commit that screws up a remote repository, it just results in your commit getting dropped (I think)). I don't immediately see that similar logic applies to this project, but if it does, it would be the best-case scenario.

Return Entire thread Last 50 posts
This thread has been closed. You cannot post in this thread any longer.