News for hackers. Stuff that matters.
Re:GxHash is a fast and robust non-cryptographic hashing alg... by bravura on Monday May 13, 2024 @03:51PM (#40347552)
Strange that all three collisions include "'s"
Re:GxHash is a fast and robust non-cryptographic hashing alg... by judofyr on Monday May 13, 2024 @04:20PM (#40347930)
Considering that 43% of the words (in my dictionary at least) include "s" it's not so strange:

    $ cat /usr/share/dict/words | wc -l
      235976
    $ cat /usr/share/dict/words | grep s |  wc -l
      101882
Re:GxHash is a fast and robust non-cryptographic hashing alg... by filleokus on Monday May 13, 2024 @04:45PM (#40348205)
GP meant that all collisions contained 's - a possessive apostrophe (if I remember my grammar correctly?). oncogene's, toadstool's, Carib's.

The /usr/share/dict/words on my macOS machine doesn't seem to have any 's words in it.

Re:GxHash is a fast and robust non-cryptographic hashing alg... by vlovich123 on Monday May 13, 2024 @04:59PM (#40348346)
counterclaiming Doesn’t have any s and stemming doesn’t have any possessive. I think drawing conclusions from a 32bit hash against a 123k word list is fruitless. You’d expect at least 1 collision due simply to birthday paradox.
Re:GxHash is a fast and robust non-cryptographic hashing alg... by airstrike on Monday May 13, 2024 @05:22PM (#40348637)

    oncogene's <> counterclaiming

    ingrates <> toadstool's

    Carib's <> stemming
all 3 pairs have one word ending in "'s", which I think is what the GGGP (?) was pointing out
Re:GxHash is a fast and robust non-cryptographic hashing alg... by bravura on Monday May 13, 2024 @05:40PM (#40348830)
Yes. But I didn't realize that 43% of the words in that dictionary contain "'s".

In that case, the probability that, for 3 collisions, there is at least one element in every collision contains "'s" is 31%. That seems reasonable to me.

Re:GxHash is a fast and robust non-cryptographic hashing alg... by airstrike on Monday May 13, 2024 @06:04PM (#40349062)
but 43% of the words contain s, not 's
Re:GxHash is a fast and robust non-cryptographic hashing alg... by zimpenfish on Monday May 13, 2024 @05:32PM (#40348757)
> counterclaiming Doesn’t have any s and stemming doesn’t have any possessive.

But "oncogene's" (collides with counterclaiming) and "Carib's" (collides with stemming) do.

Also I did point out that the 64 and 128 bit variants have no collisions.

Re:GxHash is a fast and robust non-cryptographic hashing alg... by vlovich123 on Monday May 13, 2024 @07:48PM (#40349945)
Yeah, but it's an uninteresting test. As others point out, 32-bit XXH3 has the same issue. It wouldn't surprise me if 32-bit AES did too. It has nothing to do with the quality of the hash algorithm & more to do with the fact that you're not building a perfect hash with such a small hash size.
Re:GxHash is a fast and robust non-cryptographic hashing alg... by zimpenfish on Tuesday May 14, 2024 @01:29AM (#40351916)
> Yeah, but it's an uninteresting test.

On its own, yes, fair, but it was combined with the 64 and 128 bit variants which aren't uninteresting.

> As others point out, 32-bit XXH3 has the same issue.

Yes, me.

> It has nothing to do with the quality of the hash algorithm

The original post asked "I would like to see the collision distribution on /usr/share/dict/words." and that is what they got a demonstration of - some collisions on 32 bit, none on 64 or 128 bit. What else could be done to satisfy their original request in a way that would be interesting to you?

Re:GxHash is a fast and robust non-cryptographic hashing alg... by vlovich123 on Tuesday May 14, 2024 @10:34AM (#40355638)
Point to the fact that it passes smasher in addition to that 64-bit and 128-bit variants don’t have collisions and ignore 32-bit altogether. I don’t know why libraries even bother producing 32-bit variants at this point because of how easy a collision is.