I had a bit of down time after work today so I thought I would go over some hash functions.

I never really got hash tables. Like truly understood them. I could see the purpose but where was the justification for them being everywhere?  Fortunately Uni is exactly the time and place to be smashed down for having silly thoughts like that! Hashing is used for a whole lot of really useful, really cool stuff. Or hash functions rather

Hash Function Image

Passwords - think about login credentials can be stored securely on a server. Your password to neopets.com is a closely guarded secret, but how is it kept secure? Before I go any further, it’s important to note that the hash functions I’m talking about now, are not the same as the hash functions used in hash tables. A hash table can search, insert or delete keys in  O(1)  in the average case and  O(n)  (meaning that most of the time, the time it takes to find something in a hash table is directly proportional to the amount of things you have in the hash table). A hash function for a table is made for speed, not security.

So please don’t use your (x mod y) hash function to store or encrypt passwords.

There are all sorts of different cryptographic hash functions, that but they should all do the same thing. Ideally they:

  • Can easily make a hash value for any given message
  • Manipulate a message in such a way that it’s hard to generate a message just from the hash value
  • Make it difficult to modify the message without also modifying the hash value
  • Make it incredibly unlikely that two different messages evaluate to the same hash (for reasons that should hopefully be obvious!)

This is all in an ideal world, in reality, sometimes you can’t use an ideal function, there are always tradeoffs to be made in terms of speed vs security etc, and there are a bunch of ways that such schemes can be broken.

Wikipedia quotes three such angles:

  • Pre Image Resistance
  • Second Pre Image Resistance and
  • Collision Resistance

Actually I have to leave it there, I don’t understand enough about the different angles yet.

Note to self, Don’t forget to continue this series.

In the mean time, read a bunch of wikipedia!