Hash Functions

A hash function is a function which takes an arbitrary long string of bits and produces a fixed-length output. Hash functions have applications in data structures, string-searching and even in video game design. Here we're interested in a subset of hash functions which are suitable for cryptographic purposes.

Cryptographic hash functions are designed to be one-way: functions that are practically impossible to invert. This is in contrast to the functions used in asymmetric cryptography, where trapdoor functions are infeasible to invert unless some additional secret knowledge is known.

Cryptographic hash functions are used to verify message integrity, compute digital signatures, and safely store passwords in databases. In asymmetric cryptography, hash functions are particularly useful in compressing arbitrary length messages to a value which has a smaller bit-length than the modulus when signing messages with RSA or protocols such as (EC)DSA or Elgamal.

For a hash function to be cryptographically secure, it must be resistant to the following three attacks:

• Pre-image attacks: given the output of a hash function x = hash(m), it must be practically impossible to find a message m0 such that hash(m0) = x. This is another way of saying that the hash must be a one-way function.
• Second pre-image resistance: given a message m1, it must be practically impossible to find a message m2 such that hash(m1) = hash(m2).
• Collision resistance: it should be practically impossible to find two messages m1, m2 such that hash(m1) = hash(m2). Note the difference to the second pre-image attack, in that we can vary both m1 and m2.

We can think of this as a linked set of dependencies, if a pre-image attack is known, so are second pre-image attacks and collision attacks. But if a collision attack is known, this doesn't generically allow pre-image attacks against the hash function.

Ultimately, it is impossible for a hash function to be totally secure against these attacks, in the same way symmetric and asymmetric ciphers can have their protocols brute forced. Even given a perfect one-way function, as the output has a fixed length, there will be infinitely many inputs that yield any chosen output. The goal for a cryptographic hash function is then to have algorithms designed to make the above problems "sufficiently" hard assuming an attackers compute power.

In the following challenges, we present custom hash functions which do not meet these criteria, or older cryptographic hash functions which have been found to be vulnerable to attacks.