Content deleted Content added
Created. |
m Typo |
||
Line 1:
In [[cryptography]], we can divide [[cryptographic hash functions]] into two main categories. In the first category are those functions, where their security is based on rigorous mathematical prove, complexity theory and formal reduction. These functions are called '''Provably Secure Cryptographic Hash Functions'''. To construct such a function is very difficult and only a few examples were introduced. Their practical use is limited.
In the second category are functions that were or are believed to be hard to break, but no such formal prove was given. Almost all widely-spread hash functions fall in this category. Some of these functions
== Types of Security of Hash Functions ==
Line 16:
== Classical Hash Functions - Practical Approach to Security ==
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|bitwise operations]] (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 hash functions|SHA-1]], was shown to be less secure than its length suggested: collisions could be found in only 2^{69} tests, rather than the brute-force number of 2^{80}. 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
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 thousand-fold advantage in processing power can be neutralized by adding a few dozen bits to the latter.
==
In this approach, we base the security of hash function on some hard mathematical problem and we prove that finding collisions of the hash is as hard as breaking the underlying problem. This gives much stronger security than just relying on complex mixing of bits as in the classical approach.
A cryptographic hash has '''provable security against collision attacks''' if finding collisions is provably [[Polynomial-time reduction|polynomial-time reducible]] from problem P which is supposed to be unsolvable in polynomial time. The function is then called provably secure, or just provable.
It means that if finding collisions would be feasible in polynomial time by algorithm A, we could find and use polynomial time algorithm R (reduction algorithm) that would use algorithm A to solve problem P, which is widely supposed to be unsolvable in polynomial time. That is a contradiction. This means, that finding collisions cannot be easier than solving P.
Line 42:
* Current collision-resistant hash algorithms that have provable security reductions are too inefficient to be used in practice.
=== Example of (unpractical)
Hash(''m'') = ''x''<sup>''m''</sup> mod ''n'' where ''n'' is hard to factor composite number, and ''x'' is some prespecified base value. A collision ''x''<sup>''m1''</sup> congruent to ''x''<sup>''m2''</sup> reveals a multiple ''m1 - m2'' of the order of ''x''. Such information can be used to factor ''n'' in polynomial time assuming certain properties of ''x''.
But the algorithm is quite inefficient because it requires on average 1.5 multiplications modulo ''n'' per message-bit.
=== More practical
* [[Very smooth hash|VSH - Very Smooth Hash function]] - a provably secure collision-resistant hash function assuming the hardness of finding nontrivial modular square roots modulo composite number (this is assumed to be as hard as integer factorization).
* [[Elliptic Curve Only hash function|ECOH - Elliptic Curve Only hash function]]
* [[Fast Syndrome-Based hash function|FSB - Fast Syndrome-Based hash function]] - it can be proven that breaking FSB is at least as difficult as solving a certain NP-complete problem known as Regular Syndrome Decoding.
* [[SWIFT hash function|SWIFT - Software Implemented Fault Tolerance]]
* [[Chaum, van Heijst, Pfitzmann hash function]]
* [[Knapsack-based hash functions]]
* [[The Zémor-Tillich hash function]]
| |||