A cryptographic hash function is a hash function with certain additional security properties. A hash function takes a long string (or message) as input and produces a "digest" of that message. The security properties ensure that the digest looks "random" and does not leak any information about the message itself.
Mathematically, a cryptographic hash function is a hash function such that:
- Preimage resistant ("one way"-ness)
- Given h such that h=hash(m1) it should be hard to find m1.
- Second preimage resistant
- Given h and m1 such that h=hash(m1) it should be hard to find m2 != m1 such that h=hash(m2).
- Collision-free
- It should be very hard to find two messages m1 and m2 such that hash(m1)=hash(m2). Because of the birthday paradox this means the hash function has to have a larger image than is required by being preimage-resistant.
A typical use of a crytographic hash would be as follows: Alice poses to Bob a tough math problem and claims she has solved it. Bob would like to try it himself, but would yet like to be sure that Alice is not bluffing. Therefore, Alice writes down her solution, computes its hash and tells Bob the hash value (while keeping the solution secret). This way, when Bob comes up with the solution himself a few days later, Alice can verify his solution but still be able to prove that she had the solution earlier.
In practice, of course, Alice and Bob would be computer programs, and the secret would be something less frivolous. In cryptography, the above application is called timestamping. The other important application of secure hashes is verification of message integrity.
SHA-1 and MD5 are the most commonly used cryptographic hash functions.
See also: digital signature.
