Insecure seeds

Some hash functions are labelled as insecure.

Of course all hashes with less than 160 bits are insecure. They all can be trivially brute-forced in under 2-4 min when the seed is known. But some are even more insecure than that.

For the ones with a 0 verification value, the reason is that a new known hash value can be trivially created from the previous message by just appending the calculated hash to the message. Independent of any random seed. So collisions can be trivially created, typically with the hash value 0, the first hash table bucket.

Affected

• All crc* functions
• poly_X_mersenne
• tabulation

Symptom

• Calulcate the Verification value with --verbose --test=VerifyAll

  e.g. build/SMHasher --verbose --test=VerifyAll | grep SKIP

        multiply_shift - Verification value 0x47C21D89 ....... SKIP (self- or unseeded)
   pair_multiply_shift - Verification value 0x82558D31 ....... SKIP (self- or unseeded)
  

• Edit main.cpp and add these Verification values instead of 0

  { multiply_shift,       64, 0, "multiply_shift", "Dietzfelbinger Multiply-shift on strings", POOR },
  { pair_multiply_shift,  64, 0, "pair_multiply_shift", "Pair-multiply-shift", POOR },
  =>
  { multiply_shift,       64, 0x47C21D89, "multiply_shift", "Dietzfelbinger Multiply-shift on strings", POOR },
  { pair_multiply_shift,  64, 0x82558D31, "pair_multiply_shift", "Pair-multiply-shift", POOR },
  
  

• Recompile SMHasher and test again

  make -C build
  build/SMHasher --verbose --test=VerifyAll | grep multiply
  

• The new Verification values switched from the just entered ones back to 0.

       multiply_shift - Verification value 0x00000000 ....... FAIL (Expected: 0x47C21D89)
  pair_multiply_shift - Verification value 0x00000000 ....... FAIL (Expected: 0x82558D31)
  

Verification value 0x00000000

A different symptom is when the Verification value will always be 0x00000000, even with the given expected value 0. Such as with the initial poly_X_mersenne and tabulation hashes as of commit 4751ea814177d97db29eb1fe4619cf366a71b8e5 You can try different values, the result will always be 0.

     poly_1_mersenne - Verification value 0x00000000 ....... FAIL! (should not be 0)
     poly_2_mersenne - Verification value 0x00000000 ....... FAIL! (should not be 0)
     poly_3_mersenne - Verification value 0x00000000 ....... FAIL! (should not be 0)
     poly_4_mersenne - Verification value 0x00000000 ....... FAIL! (should not be 0)
          tabulation - Verification value 0x00000000 ....... FAIL! (should not be 0)
        tabulation32 - Verification value 0x00000000 ....... FAIL! (should not be 0)

Polynomial hashes, like CRC

They are extremely fast because mostly implemented in hardware. But it is also extremely easy to compute collisions even with random seeds. See above. The computed test for the CRC family of hashes, as with all polynomial hashes, is still missing. I'll add it later.

There are many more reasons a hash can be labelled insecure

They could be easily reversible, are NULL byte insensitive or have other flaws. E.g. there are known attacks on City, Murmur or Perl JenkinsOAAT, as described in the old Hash function lounge. TODO