Hash functions

A hash function is a mathematical function that maps (or compresses) data of arbitrary size to fixed-size values, with the output sometimes called hash values, digests, or simply hashes. Given any input, it should be easy (or efficient) to compute the output. The number of possible output values is limited by the fixed output size, whereas the number of possible inputs is not restricted in the same way. Consequently, although the output is specific to the input, there will be many different inputs that map to the same output value.

The core properties of cryptographic hash functions are:

• Pre-image resistance (one way): Given a hash output, it should be difficult (computationally infeasible) to find any input that hashes to that given output.

• Collision resistance: It should be difficult to find two distinct messages m1 and m2 that hash to the same value. That is, where hash(m1) = hash(m2) for m1≠m2. Such a pair is called a collision. An algorithm-independent upper bound on the difficulty of finding collisions comes from the Birthday paradox, which implies that when searching for collisions by hashing random inputs, the expected number of trials before finding a collision is given by the square root of the number of possible outputs. That is, for collision resistance, the security level in bits is half that of the hash output bit length.

• Second pre-image resistance: For a given input, it should be difficult to find any second input that hashes to the same output. Note that collision resistance implies second pre-image resistance.

Documentation on hash functions is currently under construction, and we are actively working on providing users with a comprehensive overview of this technology.