Security of cryptographic hash functions

Last updated March 14, 2022

In cryptography, cryptographic hash functions can be divided into two main categories. In the first category are those functions whose designs are based on mathematical problems, and whose security thus follows from rigorous mathematical proofs, complexity theory and formal reduction. These functions are called Provably Secure Cryptographic Hash Functions. To construct these is very difficult, and few examples have been introduced. Their practical use is limited.

In the second category are functions which are not based on mathematical problems, but on an ad-hoc constructions, in which the bits of the message are mixed to produce the hash. These are then believed to be hard to break, but no formal proof is given. Almost all hash functions in widespread use reside in this category. Some of these functions are already broken, and are no longer in use. See Hash function security summary.

Types of security of hash functions

Generally, the basic security of cryptographic hash functions can be seen from different angles: pre-image resistance, second pre-image resistance, collision resistance, and pseudo-randomness.

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 one-way function. Functions that lack this property are vulnerable to pre-image attacks.
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 second pre-image attacks.
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 birthday attack.
Pseudo-randomness: it should be hard to distinguish the pseudo-random number generator based on the hash function from a random number generator, e.g., it passes usual randomness tests.

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 computational complexity theory. If problem A is hard, there exists a formal security reduction from a problem which is widely considered 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. The difficulty of a problem also depends on its size. For example, RSA public key cryptography relies on the difficulty of integer factorization. However, it is considered secure only with keys that are at least 2048 bits large.

Password case

Also, if the set of inputs to the hash is relatively small or is ordered by likelihood in some way, then a brute force search may be practical, regardless of theoretical security. Likelihood of recovering the preimage depends on the input set size and the speed or cost of computing the hash function. A common example is the use of hashes to store password validation data. Rather than store the plaintext of user passwords, an access control system typically stores a hash of the password. When a person requests access, the password they submit is hashed and compared with the stored value. If the stored validation data is stolen, the thief will only have the hash values, not the passwords. However most users choose passwords in predictable ways and often passwords are short enough so that all possible combinations can be tested if fast hashes are used.^[1] Special hashes called key derivation functions have been created to slow searches. See Password cracking.

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 bitwise operations (e.g. rotations), modular additions 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⁵¹^[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 a somewhat stronger notion of 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 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.

However, this only indicates that finding collisions is difficult in 'some' cases, as not all instances of a computationally hard problem are typically hard. Indeed, very large instances of NP-hard problems are routinely solved, while only the hardest are practically impossible to solve.

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 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.
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 worst-case or 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.

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.^{[ citation needed ]}

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 factoring $n$ ).
MuHASH
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.
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 lattices.
Chaum, van Heijst, Pfitzmann hash function - A compression function where finding collisions is as hard as solving the discrete logarithm problem in a finite group $F_{2p+1}$ .
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 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.^{[ dubious – discuss ]} 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 or invalidate the scheme but rather suggest that the initial parameters were too small.^[3]
Hash functions from Sigma Protocols - there exists a general way of constructing a provably secure hash, specifically from any (suitable) sigma protocol. A faster version of VSH (called VSH*) could be obtained in this way.

Related Research Articles

The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.

In cryptography, SHA-1 is a cryptographically broken but still widely used hash function which takes an input and produces a 160-bit (20-byte) hash value known as a message digest – typically rendered as a hexadecimal number, 40 digits long. It was designed by the United States National Security Agency, and is a U.S. Federal Information Processing Standard.

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems. Not being one-to-one is not considered sufficient for a function to be called one-way.

A cryptographic hash function (CHF) is a mathematical algorithm that maps data of an arbitrary size to a bit array of a fixed size. It is a one-way function, that is, a function for which it is practically infeasible to invert or reverse the computation. Ideally, the only way to find a message that produces a given hash is to attempt a brute-force search of possible inputs to see if they produce a match, or use a rainbow table of matched hashes. Cryptographic hash functions are a basic tool of modern cryptography.

In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm for computing the discrete logarithm or order of an element in a finite abelian group by Daniel Shanks. The discrete log problem is of fundamental importance to the area of public key cryptography.

In cryptography, a preimage attack on cryptographic hash functions tries to find a message that has a specific hash value. A cryptographic hash function should resist attacks on its preimage.

In cryptography, collision resistance is a property of cryptographic hash functions: a hash function H is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b where a ≠ b but H(a) = H(b). The pigeonhole principle means that any hash function with more inputs than outputs will necessarily have such collisions; the harder they are to find, the more cryptographically secure the hash function is.

In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish between a function chosen randomly from the PRF family and a random oracle. Pseudorandom functions are vital tools in the construction of cryptographic primitives, especially secure encryption schemes.

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly or approximately to the original data.

In cryptography a universal one-way hash function, is a type of universal hash function of particular importance to cryptography. UOWHF's are proposed as an alternative to collision-resistant hash functions (CRHFs). CRHFs have a strong collision-resistance property: that it is hard, given randomly chosen hash function parameters, to find any collision of the hash function. In contrast, UOWHFs require that it be hard to find a collision where one preimage is chosen independently of the hash function parameters. The primitive was suggested by Moni Naor and Moti Yung and is also known as "target collision resistant" hash functions; it was employed to construct general digital signature schemes without trapdoor functions, and also within chosen-ciphertext secure public key encryption schemes.

In computational complexity theory, a computational hardness assumption is the hypothesis that a particular problem cannot be solved efficiently. It is not known how to prove (unconditional) hardness for essentially any useful problem. Instead, computer scientists rely on reductions to formally relate the hardness of a new or complicated problem to a computational hardness assumption about a problem that is better-understood.

In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case complexity which considers the maximal complexity of the algorithm over all possible inputs.

Lattice-based cryptography is the generic term for constructions of cryptographic primitives that involve lattices, either in the construction itself or in the security proof. Lattice-based constructions are currently important candidates for post-quantum cryptography. Unlike more widely used and known public-key schemes such as the RSA, Diffie-Hellman or elliptic-curve cryptosystems, which could, theoretically, be easily attacked by a quantum computer, some lattice-based constructions appear to be resistant to attack by both classical and quantum computers. Furthermore, many lattice-based constructions are considered to be secure under the assumption that certain well-studied computational lattice problems cannot be solved efficiently.

In cryptography, Very Smooth Hash (VSH) is a provably secure cryptographic hash function invented in 2005 by Scott Contini, Arjen Lenstra and Ron Steinfeld. Provably secure means that finding collisions is as difficult as some known hard mathematical problem. Unlike other provably secure collision-resistant hashes, VSH is efficient and usable in practice. Asymptotically, it only requires a single multiplication per log(n) message-bits and uses RSA-type arithmetic. Therefore, VSH can be useful in embedded environments where code space is limited.

In computational complexity theory, the complexity class PPP is a subclass of TFNP. It is the class of search problems that can be shown to be total by an application of the pigeonhole principle. Christos Papadimitriou introduced it in the same paper that introduced PPAD and PPA. PPP contains both PPAD and PWPP as subclasses. These complexity classes are of particular interest in cryptography because they are strongly related to cryptographic primitives such as one-way permutations and collision-resistant hash functions.

In cryptography, the fast syndrome-based hash functions (FSB) are a family of cryptographic hash functions introduced in 2003 by Daniel Augot, Matthieu Finiasz, and Nicolas Sendrier. Unlike most other cryptographic hash functions in use today, FSB can to a certain extent be proven to be secure. More exactly, it can be proven that breaking FSB is at least as difficult as solving a certain NP-complete problem known as regular syndrome decoding so FSB is provably secure. Though it is not known whether NP-complete problems are solvable in polynomial time, it is often assumed that they are not.

The elliptic curve only hash (ECOH) algorithm was submitted as a candidate for SHA-3 in the NIST hash function competition. However, it was rejected in the beginning of the competition since a second pre-image attack was found.

In cryptography, SWIFFT is a collection of provably secure hash functions. It is based on the concept of the fast Fourier transform (FFT). SWIFFT is not the first hash function based on FFT, but it sets itself apart by providing a mathematical proof of its security. It also uses the LLL basis reduction algorithm. It can be shown that finding collisions in SWIFFT is at least as difficult as finding short vectors in cyclic/ideal lattices in the worst case. By giving a security reduction to the worst-case scenario of a difficult mathematical problem, SWIFFT gives a much stronger security guarantee than most other cryptographic hash functions.

In cryptography, post-quantum cryptography refers to cryptographic algorithms that are thought to be secure against a cryptanalytic attack by a quantum computer. The problem with currently popular algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems can be easily solved on a sufficiently powerful quantum computer running Shor's algorithm.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example, cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

References

↑ Goodin, Dan (2012-12-10). "25-GPU cluster cracks every standard Windows password in <6 hours". Ars Technica . Retrieved 2020-11-23.
↑ http://eprint.iacr.org/2008/469.pdf ^{[ bare URL PDF ]}
↑ Petit, C.; Quisquater, J.-J.; Tillich, J.-P., "Hard and easy Components of Collision Search in the Zémor-Tillich hash function:new Attacks and Reduced Variants with Equivalent Security" (PDF), {{citation}}: Missing or empty |title= (help)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Goodin, Dan (2012-12-10). "25-GPU cluster cracks every standard Windows password in <6 hours". Ars Technica . Retrieved 2020-11-23.

[2] ttp://eprint.iacr.org/2008/469.pdf ^{[ bare URL PDF ]}

[3] Petit, C.; Quisquater, J.-J.; Tillich, J.-P., "Hard and easy Components of Collision Search in the Zémor-Tillich hash function:new Attacks and Reduced Variants with Equivalent Security" (PDF), {{citation}}: Missing or empty |title= (help)

[1]

[2]

[3]