Collision resistance

The collision resistance property requires that two different input messages should not hash to the same output. In other words, h(x) != h(z). This property is also known as strong collision resistance.

All these properties are shown in the following diagram:

Due to their very nature, hash functions will always have some collisions. This is where two different messages hash to the same output. However, they should be computationally impractical to find. A concept known as the avalanche effect is desirable in all hash functions. The avalanche effect specifies that a small change, even a single character change in the input text, will result in an entirely different hash output.

Hash functions are usually designed by following an iterated hash functions approach. With this method, the input message is compressed in multiple rounds on a block-by-block basis in order to produce the compressed output. A popular type of iterated hash function is Merkle-Damgard construction. This construction is based on the idea of dividing the input data into equal block sizes and then feeding them through the compression functions in an iterative manner. The collision resistance of the property of compression functions ensures that the hash output is also collision-resistant. Compression functions can be built using block ciphers. In addition to Merkle-Damgard, there are various other constructions of compression functions proposed by researchers, for example, Miyaguchi-Preneel and Davies-Meyer.

Multiple categories of hash function are introduced in the following subsections.