Secure hash functions
If we use a strong hash function such as
the 64-bit hash mentioned, we expect the chances of stumbling upon two items with an
identical hash to be negligible in practice. But for some applications, we actually
need it to be impossible in practice to find a collision. Such applications
- Representing an item by its hash, but where a hash collision is more critical.
For example, consider the databases of "illegal files" kept by law enforcement agencies
so that they can search people's computers for those files. In practice,
it would probably not be feasible to store and run the search against the actual
bytes of every file in the universe that the Chinese government deems unacceptable.
So instead, a database of hashes is used. For various reasons, it could be
a "bad thing" if the text file containing your chocolate chip cookie recipe was
mistakenly identified as an "incitement to hatred" by our friends at Scotland Yard.
(Really, my chocolate chip cookies aren't that bad...)
So in practice, we want every distinct file content found on any computer in the world to
have a distinct hash code.
- Where a hash is uesd to validate data. For example, when sending
data across a network, it's common to append a hash of that data. The recipient can
then re-hash the data and check that his calculated hash matches that sent by the
sender. If they don't match, either a network error occurred, or an eavesdropper tampered
with the data. It would be a bad thing if an eavesdropper could change the data without
us realising (which could occur if they were able to find some other sequence of data
that hashed to the same value).
- In some protocols where broadly speaking
we want to commit to an answer without revealing what answer we're committing to.
The essential idea is that we can initially communicate the hash of the answer
we're committing to, and then later communicate the actual answer.
A common variant is where we want to check a password entered by a user is correct, but we don't
actually want to store the password on disk; in this case, if our hash function is
secure, we can store a hash of the password; then, at the time of login,
if the hash of the password they enter matches the hash on disk, we assume they
knew the password, as we assume it would be impossible for somebody to come up with an aribitrary
password to match a given hash. Similarly, in a voting system,
different counters could commit to having counted a particular number without actually
revealing what number they had counted until the moment of final correlation.
(In practice, we usually don't hash literally just the information: we
need to take extra steps in both cases to
protect against so-called dictionary attacks.)
Note that what we call secure hash functions here
are sometimes called cryptographic
hash functions, one-way hash functions
or message digests.