View source for Introduction to Hash Functions

= 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.

= 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.

<bibtex>
@inproceedings{cryptoDamgard89a,
  author    = {Ivan Damg{\aa}rd},
  title     = {A Design Principle for Hash Functions},
  booktitle = {CRYPTO},
  year      = {1989},
  pages     = {416-427},
  url        = {http://link.springer.de/link/service/series/0558/bibs/0435/04350416.htm},
  editor    = {Gilles Brassard},
  publisher = {Springer},
  series    = {LNCS},
  volume    = {435},
  isbn      = {3-540-97317-6},
}
</bibtex>

<bibtex>
@inproceedings{cryptoMerkle89a,
  author    = {Ralph C. Merkle},
  title     = {One Way Hash Functions and DES},
  booktitle = {CRYPTO},
  year      = {1989},
  pages     = {428-446},
  url        = {http://link.springer.de/link/service/series/0558/bibs/0435/04350428.htm},
  editor    = {Gilles Brassard},
  publisher = {Springer},
  series    = {LNCS},
  volume    = {435},
  isbn      = {3-540-97317-6},
}
</bibtex>