Security of cryptographic hash functions

In cryptography, 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, and . 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.

1 Types of security of hash functions
- 1.1 The meaning of “hard”
2 Cryptographic hash functions
3 Provably secure hash functions
4 Source
5 See Also on BitcoinWiki

Types of security of hash functions

Generally, the basic security of 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 the . Functions that lack this property are vulnerable to .
Second pre-image resistance: given an input $m_1$ , it should be hard to find another input, $m_2$ (not equal to $m_1$ ) such that $hash(m_1) = hash(m_2)$ . This property is sometimes referred to as weak collision resistance. Functions that lack this property are vulnerable to .
Collision resistance: it should be hard to find two different messages $m_1$ and $m_2$ such that $hash(m_1) = hash(m_2)$ . Such a pair is called a (cryptographic) hash collision. 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 .

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 . If problem A is hard, there exists a formal from a problem which is widely considered unsolvable in , such as problem or problem.

However, non-existence of a polynomial time algorithm does not automatically ensure that the system is secure. The difficulty of a problem also depends on its size. For example, relies on the difficulty of . However, it is considered secure only with keys that are at least 1024 bits large.

Cryptographic hash functions

Most hash functions are built on an ad hoc basis, where the bits of the message are nicely mixed to produce the hash. Various (e.g. rotations), and 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⁵¹ tests, rather than the brute-force number of 2⁸⁰.

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.

Provably secure hash functions

In this approach, we base the security of hash function on some hard mathematical problem and we prove that finding collisions of the hash functions 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 function has provable security against collision attacks if finding collisions is provably 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.

Hash functions with the proof of their security are based on mathematical functions.

Hard problems

Examples of problems, that are assumed to be not solvable in polynomial time

Downsides of provable approach

Current collision-resistant hash algorithms that have provable security 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.
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.
The proof is often a reduction to a problem with asymptotically hard or . 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 turned out to be insecure. This problem was solved in the latest version.

SWIFFT is an example of a hash function that circumvents these security problems. It can be shown that for any algorithm that can break SWIFFT with probability P within an estimated time T, we can find an algorithm that solves the worst-case scenario of a certain difficult mathematical problem within time T’ depending on T and P.

Example of (impractical) Provably Secure Hash Function

Hash(m) = x^m mod n where n is hard to factor composite number, and x is some prespecified base value. A collision x^m1 congruent to x^m2 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 provably secure hash functions

VSH – Very Smooth Hash function – a provably secure collision-resistant hash function assuming the hardness of finding nontrivial modular square roots modulo composite number $n$ (this is proven to be as hard as $n$ ).
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 weakened assumptions and eventually a second pre-image attack was found.
– 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 and is provably collision resistant, under a relatively mild assumption about the worst-case difficulty of finding short vectors in cyclic/.
– A compression function where finding collisions is as hard as solving the in a finite group $F_{2p+1}$ .
– A family of hash functions based on the .
– A family of hash functions that rely on the arithmetic of the group of matrices . Finding collisions is at least as difficult as finding factorization of certain elements in this group. This is supposed to be hard, at least . For this hash, an attack was eventually discovered with a time complexity close to $2^{n/2}$ . This beat by far the birthday bound and ideal pre-image complexities which are $2^{3n/2}$ and $2^{3n}$ for the Zémor-Tillich hash function. As the attacks include a birthday search in a reduced set of size $2n$ they indeed do not destroy the idea of provable security of invalidate the scheme but rather suggest that the initial parameters were too small.
– there exists a general way of constructing a provably secure hash, specifically from any (suitable) . A faster version of VSH (called VSH*) could be obtained in this way.