Introduction to Hash Functions
1 Security Requirements
The security properties that hash functions are expected to provide, are summarized in the following three basic requirements:
- Collision resistance: it is infeasible in practice to find two messages m and m^* != m such that h(m) = h(m^*).
- Second preimage resistance: for a given message m, it is infeasible in practice to find a second message m^* != m such that h(m) = h(m^*).
- Preimage resistance: it is infeasible in practice to find, for a given hash value y, a message m such that h(m) = y.
In practice there are several other requirements, but for sake of simplicity we stick to them.
2 On the construction of hash functions
Most hash functions in use today are designed following the Damg{\aa}rd-Merkle design principle The idea is to split the input message $m$ into $\ell$-bit blocks, which are then processed one after another by iterating a compression function $f$. Messages whose length is not a multiple of $\ell$ bits need to be padded first.
Ivan Damg\aard - A Design Principle for Hash Functions
- CRYPTO 435:416-427,1989
- http://link.springer.de/link/service/series/0558/bibs/0435/04350416.htm
BibtexAuthor : Ivan Damg\aard
Title : A Design Principle for Hash Functions
In : CRYPTO -
Address :
Date : 1989
Ralph C. Merkle - One Way Hash Functions and DES
