Hash levels

Note: This categorisation system is a work in progress. Please do not hesitate to contact me if you have suggestions or find flaws in the following text.

Until now hash functions have generally been categorised as either cryptographic or non-cryptographic. However, there are several different hash function capabilities that are useful for different purposes. I here try to categorise the most useful capability sets. A complete description consists of a level, which describes what types of capabilities a hash implements, an output size, and possibly a seed size. The output size and seed size describe how hard it is for an attacker to break the capabilities, either through luck or computation.

Level 1 (n bits of output)

A level 1 hash should, given two different inputs, produce a collision with a probability of 1 in 2n. This must hold true even if the inputs differ only by minor differences, such as inserted, deleted, altered or moved sections. It may be possible, with relatively little effort, to intentionally design input that collides. In order to avoid signalling level 2 capabilities, a level 1 hash should not accept a seed, nonce or similar.

Level 2 (n bits of output) (s bits of seed)

A level 2 hash must take a seed as part of the input. In addition to level 1 capabilities a level 2 hash must be designed so that an attacker, given no knowledge of the seed or any output from the hash, cannot produce a c-way multicollision with a probability greater than 1 in 2min(s,n (c-1)).

Level 3 (n bits of output) (s bits of seed)

In addition to level 2 capabilities, a level 3 hash must be designed so that an attacker with limited access to compute hashes for arbitrary input, without knowing the seed, must not be able to recover the seed, or any derivative thereof that is useful for computing hashes, with probability 1 in 2p, using less computations than the equivalent of computing 2s-p hashes. Producing a collision with certainty must be no easier than recovering the seed. Generating a c-way multicollision with probability 1 in 2q must not be possible for q<min(s,n (c-1)).

Level 4 (n bits of output)

It must take computation equivalent to 2n/2 hash computations to produce a collision. The hash may take a seed as part of the input, if it does, it must also have all capabilities of a level 3 hash.

Level 5 (n bits of output)

It must take computation equivalent to 2n (c-1)/c hash computations to produce a c-way multicollision. The hash may take a seed as part of the input, if it does, it must also have all capabilities of a level 3 hash.


For all hash levels it should be possible to drop part of the output and maintain all capabilities for the new output size.

Hash functions may claim lower capabilities than their implemented output and seed size suggest. Authors of such functions should generally advertise output and seed sizes according to capabilities.

A level 1 hash is useful for cases where there are absolutely no adversaries. Level 1 is what is usually referred to as a non-cryptographic hash.

Level 2 hashes are useful as internal hash functions for hash maps and similar data structures, where an adversary could use collisions in a level 1 hash to cause a denial of service. Beware that while a practical attack on a level 2 hash seems unlikely, timing attacks could reveal a small amount of information about hash values, thus technically breaking the premise of an attacker having no knowledge of hash values.

Level 3 hashes can also be used for hash maps, and suffer no theoretical deficiency for this job. They can also be used for generating message authentication codes.

Level 4 and level 5 functions can be used for identifying and verifying the integrity of a piece of data, without the need for a secret seed. Level 5 is what is usually called a cryptographic hash.