Security of cryptographic hash functions: Difference between revisions

Revision as of 04:47, 13 February 2010

Revision as of 12:27, 14 February 2010

Line 8:

* '''Pre-image resistance''': given a hash h it should be ''hard'' to find any message m such that h = hash(m). This concept is related to that of one way function. Functions that lack this property are vulnerable to pre-image attacks.

* '''Second pre-image resistance''': given an input m1, it should be ''hard'' to find another input, m2 (not equal to m1) such that hash(m1) = hash(m2). This property is sometimes referred to as weak collision resistance. Functions that lack this property are vulnerable to second pre-image attacks.

* '''Collision resistance''': it should be ''hard'' to find two different messages m1 and m2 such that hash(m1) = hash(m2). Such a pair is called a (cryptographic) hash collision, and this property is sometimes referred to as strong collision resistance. It requires a hash value at least twice as long as what is required for pre-image resistance, otherwise collisions may be found by a [[birthday attack]].

==== The Meaning of "Hard" ====

The basic question is the meaning of "'''hard'''". There are two approaches to answer this question. First is the intuitive/practical approach: "hard means that it is almost certainly beyond the reach of any adversary who must be prevented from breaking the system for as long as the security of the system is deemed important."

The second approach is theoretical and is based on the [[computational complexity theory]]. If problem A is hard, there exists a formal [[Reduction (complexity)|security reduction]] from a problem which is widely supposed to be unsolvable in [[polynomial time]], such as [[integer factorization]] problem or [[discrete logarithm]] problem.

== Classical Hash Functions - Practical Approach to Security ==