cryptographic hash functions

A cryptographic hash function is a hash function that has special properties desirable for cryptographic applications:

• pre-image resistance
  • given a hash , it’s computationally infeasible to find the original input
• second pre-image resistance
  • Given , it’s computationally infeasible to find a different s.t.
• collision resistance
  • Computationally infeasible to find any two different and s.t.

Hashing are used in various cryptographic applications including

• password hashing
• data integrity verification (see MAC): verify the transmitted data has not been tampered
• digital signatures: verify that a document has not been altered since it was signed

Pre-image Resistance

Pre-image resistance means that the hash function is resistant against attacks on its preimage (set of all possible input).

It has two flavors:

• pre-image resistance
  • Given a hash , it’s computationally infeasible to find the original input
• second pre-image resistance
  • Given , it’s computationally infeasible to find a different s.t.

Generally, second pre-image resistance is considered a stronger property and harder to achieve than pre-image resistance.

Pre-image resistance is a useful property for password hashing. If the attacker obtains the hash, they cannot recover the original password. Second pre-image resistance is also useful, as attacker can’t use another password to obtain the same hash.

Collision Resistance

See also: collision attack

Even though the pigeonhole principle means that any hash function with more input than outputs will necessarily have collisions, a good hash function should make collisions as hard to find as possible.

The birthday paradox place an upper-bound on collision resistance. If a hash function produces bits of output, an attack who compute hash operations on random input is likely to find two matching outputs (birthday attack).

Examples

• SHA-1 - has been cryptographically broken but still used for non-security purposes (e.g. Git)
• MD5 - also suffer from vulnerabilities. But suitable for non-cryptographic purpose, for example to use as checksum to verify data integrity against unintentional corruption
• SHA-256

See Also

• encryption - unlike hashing, encryption is reversible with the correct key
• avalanche effect - The desired property that a small change in input drastically changes the hash output