Difference between revisions of "Introduction to Hash Functions"
Crechberger (talk | contribs) |
m (HashIntro moved to Introduction to Hash Functions: Add blank spaces.) |
||
| (5 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
| − | + | = Security Requirements = | |
The security properties that hash functions are expected to provide, | The security properties that hash functions are expected to provide, | ||
are summarized in the following three basic requirements: | are summarized in the following three basic requirements: | ||
| − | - '''Collision resistance''': it is infeasible in practice to find two messages m and m | + | - '''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 | + | - '''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. | - '''Preimage resistance''': it is infeasible in practice to find, for a given hash value y, a message m such that h(m) = y. | ||
| Line 12: | Line 12: | ||
In practice there are several other requirements, but for sake of | In practice there are several other requirements, but for sake of | ||
simplicity we stick to them. | simplicity we stick to them. | ||
| + | |||
| + | = On the construction of hash functions = | ||
| + | |||
| + | Most hash functions in use today are designed following the | ||
| + | Damgaard-Merkle design principle | ||
| + | The idea is | ||
| + | to split the input message m into l-bit blocks, which are | ||
| + | then processed one after another by iterating a compression function | ||
| + | f. Messages whose length is not a multiple of l 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> | ||
Latest revision as of 18:17, 2 November 2008
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 Damgaard-Merkle design principle The idea is to split the input message m into l-bit blocks, which are then processed one after another by iterating a compression function f. Messages whose length is not a multiple of l 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
