next up previous
Next: Compare-by-hash in detail Up: An Analysis of Compare-by-hash Previous: Introduction


Traditional applications of hashing

The review in this section may seem tedious and unnecessary, but I believe that a clear understanding of how hashing has been used in the past is necessary to understand how compare-by-hash differs.

A hash function maps a variable length input string to fixed length output string -- its hash value, or hash for short. If the input is longer than the output, then some inputs must map to the same output -- a hash collision. Comparing the hash values for two inputs can give us one of two answers: the inputs are definitely not the same, or there is a possibility that they are the same. Hashing as we know it is used for performance improvement, error checking, and authentication. One example of a performance improvement is the common hash table, which uses a hash function to index into the correct bucket in the hash table, followed by comparing each element in the bucket to find a match. In error checking, hashes (checksums, message digests, etc.) are used to detect errors caused by either hardware or software. Examples are TCP checksums, ECC memory, and MD5 checksums on downloaded files1. In this case, the hash provides additional assurance that the data we received is correct. Finally, hashes are used to authenticate messages. In this case, we are trying to protect the original input from tampering, and we select a hash that is strong enough to make malicious attack infeasible or unprofitable.


next up previous
Next: Compare-by-hash in detail Up: An Analysis of Compare-by-hash Previous: Introduction
2003-06-16