4 ms·
I would like to see the collision distribution on /usr/share/dict/words. I have found that 'fast hash algorithms' can have very unequal hash distributions on s
by ltbarcly3 2y ago
I would like to see the collision distribution on /usr/share/dict/words. I have found that 'fast hash algorithms' can have very unequal hash distributions on short strings.
- barkbyte 2y agoDeleted
- glitchc 2y agoAES is more than just sboxes. The multiple rounds (including XORs) are integral to collision resistance.
- zimpenfish 2y agoUsing https://gist.github.com/rjp/3bbf33911aaf9ed7a07be417adb4b8f1 https://gist.github.com/rjp/3bbf33911aaf9ed7a07be417adb4b8f1 on Arch Linux `words` 2.1-8 (which defaults to the `usa` word list) gives collisions for the 32 bit hash (but none for the 64 bit or the 128 bit variants.) > ./target/debug/gxwords | cut -d' ' -f1 | sort | uniq -c | awk '$1>1' 2 28273056 2 8e264f8 2 f7bce777 Which then gives us > ./target/debug/gxwords | egrep '28273056|8e264f8|f7bce777' | sort 28273056 counterclaiming 28273056 oncogene's 8e264f8 ingrates 8e264f8 toadstool's f7bce777 Carib's f7bce777 stemming
- bravura 2y agoStrange that all three collisions include "'s"
- judofyr 2y agoConsidering 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
- filleokus 2y agoGP 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.
- vlovich123 2y agocounterclaiming 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.
- airstrike 2y agooncogene'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
- bravura 2y agoYes. 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.
- airstrike 2y agobut 43% of the words contain s, not 's
- zimpenfish 2y ago> 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.
- vlovich123 2y agoWouldn’t that be true for any 32-bit hash? The birthday paradox would suggest you only need 2^16 input values to generate a collision right?
- zimpenfish 2y agoxxhash32 does give a couple of collisions on the same file, yep. 734c8981 abloom 734c8981 sating ef336a7d contravene ef336a7d seducers
- jcelerier 2y agoI thought interesting that all three collision pairs have an 's ending, but looking into this dictionary, no less than 25% of the words finish by it. weird dict.
- ted_dunning 2y agoThe article emulates that result by synthesizing words. The problem with using /user/dict/words is that there aren't enough to get a really good statistical estimate of collisions at more than very small scale. Also the core primitive is AES which should calm most such worries.
- vlovich123 2y agoNot to mention you should be using the 64-bit variant for collision resistance and the 128-bit variant for integrity.