Hash Function

Cryptographic hash functions are designed to make it infeasible to find collisions or reverse the digest. Hashes are used for integrity, signatures, and password storage (with appropriate slow hashing).

A function H that maps an arbitrary, variable length bit string, s, into a fixed length string, h = H(s) (called the "hash result"). For most computing applications, it is desirable that given a string s with H(s) = h, any change to s that creates a different string s' will result in an unpredictable hash result H(s') that is, with high probability, not equal to H(s).

"A (mathematical) function which maps values from a large (possibly very large) domain into a smaller range. A 'good' hash function is such that the results of applying the function to a (large) set of values in the domain will be evenly distributed (and apparently at random) over the range." [X509] Tutorial: A hash function operates on variable length input (e.g., a message or a file) and outputs a fixed length output, which typically is much shorter than most input values. If the algorithm is "good" as described in the "O" definition, then the hash function may be a candidate for use in a security mechanism to detect accidental changes in data, but not necessarily for a mechanism to detect changes made by active wiretapping. (See: Tutorial under "checksum".) Security mechanisms require a "cryptographic hash function" (e.g., MD2, MD4, MD5, SHA 1, Snefru), i.e., a good hash function that also has the one way property and one of the two collision free properties: "One way property": Given H and a hash result h = H(s), it is hard (i.e., computationally infeasible, "impossible") to find s. (Of course, given H and an input s, it must be relatively easy to compute the hash result H(s).) "Weakly collision free property": Given H and an input s, it is hard (i.e., computationally infeasible, "impossible") to find a different input, s', such that H(s) = H(s'). "Strongly collision free property": Given H, it is hard to find any pair of inputs s and s' such that H(s) = H(s'). If H produces a hash result N bits long, then to find an s' where H(s') = H(s) for a specific given s, the amount of computation required is O(2 n); i.e., it is necessary to try on the order of 2 to the power n values of s' before finding a collision. However, to simply find any pair of values s and s' that collide, the amount of computation required is only O(2 (n/2)); i.e., after computing H(s) for 2 to the power n/2 randomly chosen values of s, the probability is greater than 1/2 that two of those values have the same hash result. (See: birthday attack.)