Hash Collisions in Wordlists
Hash Collisions in Wordlists
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...
We first check the sizes of the wordlist for some random languages.
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]
Out[]//Short=
{abnego085a026d,cancer085a026d,abnocto0b5c02e7,adeptio0b5c02e7,abortio0b8a02f1,dictito0b8a02f1,iaculum0b8a02f1,abruptio0f100367,sacratus0f100367,absque08a40282,aliter08a40282,acriter0b7602eb,carnero0b7602eb,559,uter047001c1,vixi047001c1,volo047001c1,uterque0c55030c,vulnero0c55030c,velum0682022a,veris0682022a,vergo067a0224,vobis067a0224,viduo067c0228,vigor067c0228,vinum06980230,vitis06980230}
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!