Content deleted Content added
clean up using AWB |
|||
Line 1:
In [[cryptography]], [[cryptographic hash functions]] can be divided into two main categories. In the first category are those functions whose designs are based on a mathematical problem and thus their security follows from rigorous mathematical proofs, [[Computational complexity theory|complexity theory]] and [[Reduction (complexity)|formal reduction]]. These functions are called '''Provably Secure Cryptographic Hash Functions'''. However this does not mean that such a function could not be broken. To construct them is very difficult and only a few examples were introduced. The practical use is limited.
In the second category are functions that are not based on mathematical problems but on an ad hoc basis, where the bits of the message are mixed to produce the hash. They are then believed to be hard to break, but no such formal proof is given. Almost all widely-spread hash functions fall in this category. Some of these functions are already broken and are no longer in use.
== Types of Security of Hash Functions ==
Generally, the ''basic'' security of [[cryptographic hash functions]] can be seen from three different angles: pre-image resistance, second pre-image resistance and collision resistance.
* '''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 attack]]s.
Line 14:
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.
However, non-existence of a polynomial time algorithm does not automatically ensure that the system is secure. It is equally important to choose the parameters sensibly (e.g. a length of the numbers that the system works with). For instance, factoring 21 is easy although in general [[integer factorization]] is considered a hard problem.
Line 21:
Most hash functions are built on an ad hoc basis, where the bits of the message are nicely mixed to produce the hash. Various [[bitwise operation]]s (e.g. rotations), [[Modular arithmetic|modular additions]] and [[One-way compression function|compression functions]] are used in iterative mode to ensure high complexity and pseudo-randomness of the output. In this way, the security is very hard to prove and the proof is usually not done. Only a few years ago, one of the most popular hash functions, [[SHA-1]], was shown to be less secure than its length suggested: collisions could be found in only 2<sup>51</sup><ref>http://eprint.iacr.org/2008/469.pdf</ref> tests, rather than the brute-force number of 2<sup>80</sup>. The search for a "good" hash function has thus become a hot topic.
In other words, most of the hash functions in use nowadays are not provably collision-resistant. These hashes are not based on purely mathematical functions. This approach results generally in more effective hashing functions, but with the risk that a weakness of such a function will be eventually used to find collisions. The famous case is [[MD5]].
Meaning of "hard to find collision" in these cases means "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 meaning of the term is therefore somewhat dependent on the application, since the effort that a malicious agent may put into the task is usually proportional to his expected gain. However, since the needed effort usually grows very quickly with the digest length, even a thousandfold advantage in processing power can be neutralized by adding a few dozen bits to the latter.
Line 67:
| contribution = Hard and easy Components of Collision Search in the Zémor-Tillich hash function:new Attacks and Reduced Variants with Equivalent Security
| contribution-url = http://www-rocq.inria.fr/secret/Jean-Pierre.Tillich/publications/CTRSA.pdf }}</ref>
* [[Hash functions from Sigma Protocols]] - there exists a general way of constructing a provably secure hash, specifically from
==References==
| |||