This notebook explores hash collisions in WL’s wordlists for the smaller hash function in the Wolfram Language, such as MD5, MD4, MD2, CRC32, and Adler32.
Note that this is not a very serious crypto analysis of hash collisions, since we know that these hash functions are not secure (and some of them are not designed to be crypto secure). But it is a fun exercise. Also note that some of these tests might take some time to run; I have not optimized for speed, but for fun...
Note that this is not a very serious crypto analysis of hash collisions, since we know that these hash functions are not secure (and some of them are not designed to be crypto secure). But it is a fun exercise. Also note that some of these tests might take some time to run; I have not optimized for speed, but for fun...
We first check the sizes of the wordlist for some random languages.
In[]:=
languages={"English","Latin","Swedish","German","Danish","Dutch","Italian","Russian"};SortBy[{#,Length[WordList["KnownWords",Language->#]]}&/@languages,Last]//TableForm
Out[]//TableForm=
Latin | 8777 |
Russian | 31801 |
German | 76155 |
English | 84923 |
Italian | 116854 |
Swedish | 121430 |
Dutch | 229365 |
Danish | 376468 |
One would expect that the probabilities of hash collisions are larger for the larger wordlists.
First we define some helper functions for the explorations.
In[]:=
md5[word_]:=Hash[word,"MD5","HexString"]md4[word_]:=Hash[word,"MD4","HexString"]md2[word_]:=Hash[word,"MD2","HexString"]crc32[word_]:=Hash[word,"CRC32","HexString"]adler32[word_]:=Hash[word,"Adler32","HexString"]
This function hashCollision[] checks if there are any collisions in the wordlist. It simply compares the number of words with the number of generated hashes, and returns true if they are not the same.
In[]:=
hashCollision[language_,fun_]:=Module[{words},words=WordList["KnownWords",Language->language];CountDistinct[fun[#]&/@words]!=Length[words]]
Are there any hash collisions in the Latin wordlist generated by MD5?
In[]:=
hashCollision["Latin",md5]
Out[]=
False
Since the Latin wordlist is so small (8777 words) the probably of collision is quite small.
Let’s test this a little more systematically. First the larger sized hash functions: MD5, MD4, and MD2 (all using 128-bits). None of these give any hash collisions.
Let’s test this a little more systematically. First the larger sized hash functions: MD5, MD4, and MD2 (all using 128-bits). None of these give any hash collisions.
In[]:=
{#,hashCollision[#,md5]}&/@languages
Out[]=
{{English,False},{Latin,False},{Swedish,False},{German,False},{Danish,False},{Dutch,False},{Italian,False},{Russian,False}}
In[]:=
{#,hashCollision[#,md4]}&/@languages
Out[]=
{{English,False},{Latin,False},{Swedish,False},{German,False},{Danish,False},{Dutch,False},{Italian,False},{Russian,False}}
In[]:=
{#,hashCollision[#,md2]}&/@languages
Out[]=
{{English,False},{Latin,False},{Swedish,False},{German,False},{Danish,False},{Dutch,False},{Italian,False},{Russian,False}}
Perhaps the smaller (32 bit) hashes, CRC32 and Adler32, give any collisions?
CRC32 is first out on this.
CRC32 is first out on this.
In[]:=
{#,hashCollision[#,crc32]}&/@languages
Out[]=
{{English,False},{Latin,False},{Swedish,False},{German,False},{Danish,True},{Dutch,True},{Italian,False},{Russian,False}}
Aha! For the two largest wordlists (Danish and Dutch) there are some hash collisions!
We start with the Danish words (since I know a little Danish).
Here we see that for the 376 468 Danish words there are only 376 458 hashes: there are actually 10 hash collisions.
We start with the Danish words (since I know a little Danish).
Here we see that for the 376 468 Danish words there are only 376 458 hashes: there are actually 10 hash collisions.
In[]:=
danishWords=WordList["KnownWords",Language->"Danish"];crc32Danish=crc32[#]&/@danishWords;crc32DanishCounts=Counts[crc32Danish];crc32DanishMap=AssociationThread[danishWords->crc32Danish];CountDistinct[crc32Danish]!=Length[danishWords]{CountDistinct[crc32Danish],Length[danishWords]}
Out[]=
True
Out[]=
{376458,376468}
Identify the hashes:
In[]:=
collisions=Keys@Select[crc32DanishCounts,#>1&]Table[Select[crc32DanishMap,#==c&],{c,collisions}]
Out[]=
{faca9287,e8c06a0f,ca1abfdc,18bed883,e7eb053a,5f15a39c,126ba3cd,72878fad,e9b482fb,96083297}
Out[]=
{åndevæsenfaca9287,godtgørfaca9287,arbitragøre8c06a0f,langrende8c06a0f,billedanalyserca1abfdc,forhandlingssuccesca1abfdc,Broby18bed883,flikflakkenes18bed883,debutromane7eb053a,deltagene7eb053a,dykningen5f15a39c,sjældenheders5f15a39c,energiministeriets126ba3cd,hyrde126ba3cd,glashusenes72878fad,kammertjener72878fad,glinse9b482fb,kommunikationene9b482fb,sørøvere96083297,terrazzogulvets96083297}
What does these words mean?
In[]:=
TextTranslation["åndevæsen","Danish"->"English"]TextTranslation["godtgør","Danish"->"English"]
Out[]=
spirit creature
Out[]=
Proves
Since there are also collision for the Dutch wordlist, we need a function for this.
In[]:=
listCollisions[language_,fun_]:=Module[{words,hashList,counts,hashMap,collisions},words=WordList["KnownWords",Language->language];hashList=fun[#]&/@words;counts=Counts[hashList];hashMap=AssociationThread[words->hashList];collisions=Keys@Select[counts,#>1&];Table[Select[hashMap,#==c&],{c,collisions}]]
In[]:=
listCollisions["Danish",crc32]
Out[]=
{åndevæsenfaca9287,godtgørfaca9287,arbitragøre8c06a0f,langrende8c06a0f,billedanalyserca1abfdc,forhandlingssuccesca1abfdc,Broby18bed883,flikflakkenes18bed883,debutromane7eb053a,deltagene7eb053a,dykningen5f15a39c,sjældenheders5f15a39c,energiministeriets126ba3cd,hyrde126ba3cd,glashusenes72878fad,kammertjener72878fad,glinse9b482fb,kommunikationene9b482fb,sørøvere96083297,terrazzogulvets96083297}
The Dutch wordlist has even more hash collisions: 12 collisions.
Some collisions are especially interesting since it shows that CRC32 don’t follow to the Avalance principle, i.e. that small changes in input should give large difference in the generated hash.
* “ongezeglijker” and “persoonlijkst”
* ”ongezeglijkere” and “persoonlijkste”
* “ongezeglijkst” and ”persoonlijker”
* ”ongezeglijkste” and “persoonlijkere”
Some collisions are especially interesting since it shows that CRC32 don’t follow to the Avalance principle, i.e. that small changes in input should give large difference in the generated hash.
* “ongezeglijker” and “persoonlijkst”
* ”ongezeglijkere” and “persoonlijkste”
* “ongezeglijkst” and ”persoonlijker”
* ”ongezeglijkste” and “persoonlijkere”
In[]:=
listCollisions["Dutch",crc32]Length@%
Out[]=
{eerbaarst75fafc7c,methodologische75fafc7c,genegeerden529ec563,mondainste529ec563,gereconstrueerden41ee8366,scannen41ee8366,kerstboomverlichtingd258eb37,vensterramend258eb37,kritieker220e62e5,wagenkilometers220e62e5,meubelstoffeerder49985f1c,strekking49985f1c,ongezeglijker47ae49c6,persoonlijkst47ae49c6,ongezeglijkere9d9ab396,persoonlijkste9d9ab396,ongezeglijkstb2555924,persoonlijkerb2555924,ongezeglijksted36bcbd2,persoonlijkered36bcbd2,terugdreef10cb3422,zomerzon10cb3422,touwslagereb7a55a2,watergekoeldeb7a55a2}
Out[]=
12
In[]:=
TextTranslation["ongezeglijker","Dutch"->"English"]TextTranslation["persoonlijkst","Dutch"->"English"]
Out[]=
more unspeakable
Out[]=
most personal
And last, let’s see how well (or bad) Adler32 do on this.
Well, not good at all: All the tested wordlists has collisions!
And there’s a lot of collisions.
Well, not good at all: All the tested wordlists has collisions!
And there’s a lot of collisions.
In[]:=
{#,hashCollision[#,adler32]}&/@languages
Out[]=
{{English,True},{Latin,True},{Swedish,True},{German,True},{Danish,True},{Dutch,True},{Italian,True},{Russian,True}}
In[]:=
countHashCollision[language_,fun_]:=Module[{words,numWords,numHashes},words=WordList["KnownWords",Language->language];numWords=Length[words];numHashes=CountDistinct[fun[#]&/@words];{language,numWords,numWords-numHashes,N[(numWords-numHashes)/numWords]}]
Here we show the number of words, the number of hash collisions, and the percentage of collision in the wordlists.
In[]:=
SortBy[countHashCollision[#,adler32]&/@languages,Last]//Reverse//TableForm
Out[]//TableForm=
Dutch | 229365 | 89875 | 0.391843 |
Italian | 116854 | 39219 | 0.335624 |
Danish | 376468 | 120774 | 0.320808 |
English | 84923 | 17402 | 0.204915 |
Swedish | 121430 | 22669 | 0.186684 |
Latin | 8777 | 634 | 0.0722342 |
German | 76155 | 5267 | 0.0691616 |
Russian | 31801 | 661 | 0.0207855 |
For the Latin wordlist there are 634 collisions on the 8777 words, i.e. about 7.2%.
In[]:=
Short[listCollisions["Latin",adler32],10]
Note that this is quite/very slow for the larger wordlist such as the English. For the English words, Adler32 yield over 17 000 collisions!
A related idea: smallest hash collisions
A related idea: smallest hash collisions
A related idea is to search for the smallest hash collisions for the two weak hash functions (CRC32 and Adler32) and use all possible strings of a certain size .
Unfortunately, for the generated wordlists that I could test, there wasn’t any hash collisions which surprised me a little. Anyway, here' s the idea and the code.
Let' s assume that we use words with strings of the characters [a - zA - Z0 - 9] and generate all possible strings up to a certain length, i .e. size = 3 generates all possible strings of length 1, 2, and 3.
Here' s the alphabet and 30 random samples :
Unfortunately, for the generated wordlists that I could test, there wasn’t any hash collisions which surprised me a little. Anyway, here' s the idea and the code.
Let' s assume that we use words with strings of the characters [a - zA - Z0 - 9] and generate all possible strings up to a certain length, i .e. size = 3 generates all possible strings of length 1, 2, and 3.
Here' s the alphabet and 30 random samples :
We reuse some of the functions from above:
generateWords[] generate all possible strings of length 1..n.
The number of generated words for each size (1..4):
The function listCollisions2[] lists the collisions (if any) for a given list of words and a hash function. Returns {} if there are no collisions.
As mentioned above, we don’t found any hash collisions for CRC32 or Adler32 for sizes up to 4:
One major problem with this approach is that the size of wordlists increases very fast and soon be forbiddingly large :
For size 5, I couldn’t even generate the wordlist (got the error "No more memory available. Mathematica kernel has shut down"), but using WL' s excellent FindSequenceFunction[] we can at least estimate the sizes of the wordlists for larger sizes:
Thus, generateWords[5] would give a wordlist of 931 151 402 words .
Afterthought
Afterthought
(This was added as an update.)
Perhaps it's not that surprising that there are no hash conflicts for Adler32. Here are some of the words and their Adler32 hashes for the size 4 generated words, i .e. the hashes are distinct and just incrementing from the last (with two “counters”) and are in order .
Perhaps it's not that surprising that there are no hash conflicts for Adler32. Here are some of the words and their Adler32 hashes for the size 4 generated words, i .e. the hashes are distinct and just incrementing from the last (with two “counters”) and are in order .
Testing with some longer words we see that it (still) uses the same principle of two counters :
The hashes for CRC32 is much more random like :