Hashes have always been a fascinating class of algorithms to me due to their following characteristics:

  • Fixed output size - the ability to give a function some input, whether the single character “A” or the entire works of Shakespeare, and get a fixed length output is just plain neat
  • Deterministic - you get the same result given the same input
  • One-way functions - it is difficult, and in the case of cryptographic hash functions, computationally infeasible to reverse the hash to get the original input

These characteristics unlock all kinds of useful problem-solving mechanisms. Hash functions generally fall into two categories:

  1. Cryptographic - useful in security contexts, and focus on the following properties:
    1. Preimage Resistance: infeasible to reverse the hash function
    2. Avalanche Effect: A small change in the input should produce a significantly different hash output
    3. Collision Resistance: infeasible to find another value that results in the same hash
  2. Non-Cryptographic - useful for hash-tables/maps & non-secure performance critical operations:
    1. fast hashing
    2. generally smaller hash outputs

Here’s a comparison of some common hash functions to give a feel for the characteristics. Note: the speed column and collision risk are relative.

Hash Function Cryptographic Hash Output Size Speed Collision Risk
MD5* Yes 128-bit Fast High
SHA-1* Yes 160-bit Moderate High
SHA-256 Yes 256-bit Slower Very Low
SHA-3 Yes 224, 256, 384, 512-bit Slower Very Low
bcrypt Yes 192-bit (default) Slow Very Low
MurmurHash No 32-bit, 64-bit, 128-bit Very Fast Moderate
CityHash No 64-bit, 128-bit Very Fast Moderate
CRC32 No 32-bit Very Fast High
SipHash No 64-bit, 128-bit Moderate Low

* Note: MD5 & SHA-1 are considered harmful today for cryptographic use. e.g. OWASP cheat sheet on their avoidance.

A small sampling of real world applications

Cryptographic Hashes

Storing Passwords

Obviously no one should be storing passwords in plain text, so storing salted and hashed passwords will significantly slow bad actors from making use of any compromised password data dumps. Take a look at bcrypt as an example.

Data Integrity

Git uses SHA1 with an eye towards transitioning to SHA256 to uniquely identify content and commits. Ubuntu publishes SHA256 hashes so you can verify that the version you downloaded matches and hasn’t been tampered with. Most operating systems have built-in tools to check hashes. You can verify the hash via sha256sum on mac, sha256sum on linux, or certutil on windows.

Another common use case is digital signatures. For public key cryptography, a sender:

  1. Signs a message by hashing the contents of the message
  2. Encrypts the hashed message using their private key
  3. Sends the original message along with the digital signature to the recipient

The recipient on getting the message:

  1. Hashes the original message using the same hash function
  2. Decrypts the encrypted signature
  3. Compares the decrypted signature with the hashed original message. If they match, the message is authentic.

TLS & HTTPS

Most browsers, e.g. Chrome, have a button you can click to the left of the URL in the address bar. When visiting an https site, you should be able to see a padlock icon that shows a SHA256 hash of the site’s certificate. In essence, a web client can run the certificate of a website through sha256 and verify that the fingerprint matches a value from a known Certificate Authority.

Blockchain

Bitcoin uses SHA-256 in its proof-of-work algorithm - essentially guessing random values until it finds the requisite number of leading 0s to win the block. Other nodes on the network can then quickly verify that the value is correct by running it through the hash and checking if it’s valid. Of course, this approach to block production has generated a lot of debate (and energy consumption). While it was revolutionary when it was released, there have been significant advances in consensus algorithms that use less energy, e.g. proof-of-stake

Non-Cryptographic Hashes

A hash table/map data structure is probably the biggest use case of non-cryptographic hashes.

And of course almost every language calls it something different:

  • Java = HashMap, HashTable
  • Python = dict
  • C++ = unordered_map
  • Go = map It has some phenomenal properties:
    • O(1) search
    • O(1) insertion
    • O(1) delete
    • O(n) space It’s so often used that it’s become a meme, like this one pulled from the /r/programming subreddit

img

What hash algorithms are used here? Well, it depends on your programming language and possibly the hardware as well. And we can see from this golang-nuts discussion of aeshash that, “It is quite a bit faster than portable alternatives like murmurhash or cityhash.” the downside being, “aeshash is only used if on x86 and if aes hardware instructions are available.” - at least at the time of that post.

Dave Cheney gives a good overview of hash table algorithms and comparing Go with other languages here

And then we can see Rust actually uses SipHash - which trades speed for denial of service resistance.

Conclusion

Hashes are everywhere in software. They enable quick validations, secure storage of passwords, consensus algorithms, and are behind the commonly used map/hash-table/dict data structure.

The one you pick will depend on your needs.

The general rule-of-thumb is if you need security, pick a cryptographic hash that is not MD5 or SHA1, and generally more secure algorithms can be selected if you’re willing to trade for slower speeds.

If you don’t need security, there are lots of options too. Need fast error checking for raw data? Take a look at CRC32. If you don’t need a secure hash and aren’t doing some fast error checking, chances are you may be using hashes for a map data structure, in which case the built-in version of maps for your language are likely sufficient - if they are not there are lots of alternatives such as CityHash, MurmurHash and SipHash.

Resources