Security of cryptographic hash functions: Difference between revisions

Revision as of 14:25, 5 January 2010

Revision as of 13:25, 7 January 2010

Line 1:

In [[cryptography]], we can divide [[cryptographic hash functions]] into two main categories. In the first category are those functions, where their securitydesign is based on a mathematical problem and thus their security follows rigorous mathematical proveproves, [[Computational complexity theory|complexity theory]] and [[Reduction (complexity)|formal reduction]]. These functions are called '''Provably Secure Cryptographic Hash Functions'''. ToHowever constructthis does not mean that such a function could not be broken. To construct them is very difficult and only a few examples were introduced. TheirThe practical use is limited.

In the second category are functions that wereare ornot based on mathematical problems but on an ad hoc basis, where the bits of the message are nicely mixed to produce the hash. They are then believed to be hard to break, but no such formal prove wasis 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 ==

Line 36:

* [[Quadratic residue|Finding Modular Square Roots]]

* [[Integer factorization|Integer Factorization Problem]]

* [[Subset sum problem|Subset Sum Problem]]

=== 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 comparisioncomparison to clasicalclassical 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 [[Average-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. [[Fast Syndrome-Based hash function]] is an example.

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

=== Example of (unpractical) Provably Secure Hash Function ===

Line 50:

=== More practical Provably Secure Hash Functions ===

* [[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).

* [[MuHASH]]

* [[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.

Line 56 ⟶ 57:

* [[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}}

[[Category:Cryptographic hash functions]]