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.

languages={"English","Latin","Swedish","German","Danish","Dutch" , "Italian","Russian"};
SortBy[{#,Length[WordList["KnownWords",Language->#]]} & /@ languages,Last]// TableForm

One would expect that the probabilities of hash collisions are larger for the larger wordlists.

First we define some helper functions for the explorations.

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.

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?

hashCollision["Latin",md5]

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.

{#,hashCollision[#,md5]} & /@ languages

{#,hashCollision[#,md4]} & /@ languages

{#,hashCollision[#,md2]} & /@ languages

Perhaps the smaller (32 bit) hashes, CRC32 and Adler32, give any collisions?
CRC32 is first out on this.

{#,hashCollision[#,crc32]} & /@ languages

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.

danishWords = WordList["KnownWords",Language->"Danish"];
crc32Danish = crc32[#] & /@ danishWords;
crc32DanishCounts = Counts[crc32Danish];
crc32DanishMap = AssociationThread[danishWords->crc32Danish];
CountDistinct[crc32Danish] != Length[danishWords]
{CountDistinct[crc32Danish], Length[danishWords]}

Identify the hashes:

collisions = Keys@Select[crc32DanishCounts,# > 1&]
Table[Select[crc32DanishMap, # == c & ], {c, collisions}]

What does these words mean?

TextTranslation["åndevæsen","Danish"->"English"]
TextTranslation["godtgør","Danish"->"English"]

Since there are also collision for the Dutch wordlist, we need a function for this.

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}] 
]

listCollisions["Danish",crc32]

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”

listCollisions["Dutch",crc32]
Length@%

TextTranslation["ongezeglijker","Dutch"->"English"]
TextTranslation["persoonlijkst","Dutch"->"English"]

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.

{#,hashCollision[#,adler32]} & /@ languages

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.

SortBy[countHashCollision[#,adler32] & /@ languages,Last]//Reverse//TableForm

For the Latin wordlist there are 634 collisions on the 8777 words, i.e.  about 7.2%.

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!

AbsoluteTiming[Short[listCollisions["English",adler32],10]]

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 :

alpha=Flatten[{CharacterRange["a","z"],CharacterRange["A","Z"],CharacterRange["0","9"]}];
RandomSample[Table[StringJoin[#]&/@Tuples[alpha,n],{n,1,3}]//Flatten,30]

We reuse some of the functions from above:

crc32[word_]:=Hash[word,"CRC32","HexString"]
adler32[word_]:=Hash[word,"Adler32","HexString"]

generateWords[] generate all possible strings of length 1..n.

generateWords[n_] := Module[{words},
words = Table[StringJoin[#] & /@Tuples[alpha,len],{len,1,n}]//Flatten
]

The number of generated words for each size (1..4):

Table[{n,Length[generateWords[n]]},{n,1,4}]//TableForm

The function listCollisions2[] lists the collisions (if any) for a given list of words and a hash function. Returns {} if there are no collisions.

listCollisions2[words_,fun_]:=Module[{hashList,counts,hashMap,collisions},hashList=fun[#]&/@words;
If[Length[hashList]!=Length[words],counts=Counts[hashList];
hashMap=AssociationThread[words->hashList];
collisions=Keys@Select[counts,#>1&];
Table[Select[hashMap,#==c&],{c,collisions}],
{}  (* else: no collisions *)
]
]

As mentioned above, we don’t found any hash collisions for CRC32 or Adler32 for sizes up to 4:

Table[{n,listCollisions2[generateWords[n],crc32]},{n,1,4}]//AbsoluteTiming

Table[{n,listCollisions2[generateWords[n],adler32]},{n,1,4}]//AbsoluteTiming

One major problem with this approach is that the size of wordlists increases very fast and soon be forbiddingly large :

Table[{n,Length[generateWords[n]]},{n,1,4}]//TableForm

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:

FindSequenceFunction[{62,3906,242234,15018570}]
{#,%[#]}&/@Range[1,10]//TableForm

Thus, generateWords[5] would give a wordlist of 931 151 402 words .

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 .

Short[{#,adler32[#]}&/@generateWords[4],20]

Testing with some longer words we see that it (still) uses the same principle of two counters :

{#,adler32[#]}&/@{"aaaaa","aaaab","aaaac","aaaaaaaaaaa","aaaaaaaaaab","aaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaab"}//TableForm

The hashes for CRC32 is much more random like :

Short[{#,crc32[#]}&/@generateWords[4],20]