Security of cryptographic hash functions: Difference between revisions

Revision as of 18:22, 9 February 2010

Revision as of 04:47, 13 February 2010

Line 13:

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

Most hash functions are built on an ad hoc basis, where the bits of the message are nicely mixed to produce the hash. Various [[Bitwisebitwise operation|bitwise operations]]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 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 provably secure collision-resistant. These hashes are not based on purely mathematical functions. This approach results generally in more effective hashing algorithms, but with the risk that a weakness of such a function will be eventually used to find collisions. The famous case is [[MD5]].

Line 40:

=== Downsides of Provable Approach ===

* Current collision-resistant hash algorithms that have provable security [[Reduction (complexity)|reductions]] are too inefficient to be used in practice. In comparison to classical hash functions, they tend to be relatively slow and do not always meet all of criteria traditionally expected of cryptographic hashes. [[Very smooth hash]] is an example.

* The proof is often a reduction to a problem with asymptotically hard [[Worst-case complexity|words-case]] or [[Averageaverage-case complexity|average-case]] complexity. Worst-case measures the difficulty of solving pathological cases rather than typical cases of the underlying problem. Even a reduction to a problem with hard average complexity offers only limited security as there still can be an algorithm that easily solves the problem for a subset of the problem space. For example, early versions of [[Fast Syndrome Based Hash]] turned out to be insecure. This problem was solved in the latest version.

* Constructing a hash function with provable security is much more difficult than using a classical approach where we just hope that the complex mixing of bits in the hashing algorithm is strong enough to prevent adversary from finding collisions.

Line 53:

* [[Elliptic curve only hash|ECOH - Elliptic Curve Only hash function]] - based on the concept of Elliptic curves, Subset Sum Problem and summation of polynomials. The security proof of the collision resistance was based on weakend assumptions and eventually a second pre-image attack was found.

* [[Fast Syndrome Based Hash|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.

* [[SWIFFT]] - SWIFFT is based on the [[Fast fourier transform]] and is provably collision resistant, under a relatively mild assumption about the worst-case difficulty of finding short vectors in cyclic/ideal [[lattice|lattices]]s.

* [[Chaum, van Heijst, Pfitzmann hash function]] - A compression function where finding collisions is as hard as finding a [[discrete logarithm|discrete logarithm problem]] in a finite group <math>F_{2p+1}</math>.

* [[Knapsack-based hash functions]] - A family of hash functions based on the [[Knapsack problem]].

* [[The Zémor-Tillich hash function]] - A family of hash functions that rely on the arithmetic of the group of matrices [[Special linear group|SL2]]. Finding collisions is at least as difficult as finding factorization of certain elements in this group. This is supposed to be hard, at least [[PSPACE-complete]].

* [[Hash functions from Sigma Protocols]] - there exists a general way of constructing a provably secure hash, specifically from a any (suitable) [[The Sigma Protocol|sigma protocol]]. A speed-up version of [[Very smooth hash|VSH ]] (called VSH*) could be obtained in this way.

{{Crypto navbox | hash}}