Is there a hash function whose security can be extended by length?

Question

Some old hash functions have been proven to be unsafe. This is mainly due to two reasons:

1. The computation power of machines are increasing.

2. People have discovered algorithmic flaws in those hash functions.

Strictly speaking, these two reasons have very different implications. The first may be remedied by extending the length of the block sizes, the number of rounds, or other variables used in the algorithm. But the second reveals intrinsic flaws in the algorithm design.

Hash functions are usually based on simpler cryptographic primitives, and there should be provable reductions from the security of the hash function itself to that of the underlying primitives. Thus I'm wondering whether there exists a hash function whose algorithm design is provably secure (given that the underlying primitives are secure), and its overall security only depends on the length of variables. Such an algorithm can be easily extended to cope with increasing computation power without much effort.

Is there such an extendable algorithm? If so, what is it? And why do people keep inventing new algorithms instead of extending this algorithm? If not, why?

Answer 1

Note: this answer assumes that this is about secure hash applications, not password-hashing which is a different set of algorithms with other properties.

---

There are a few assumptions in your question that may not be fully applicable:

Some old hash functions have been proven to be unsafe. This is mainly due to two reasons:

1. The computation power of machines are increasing.
2. People have discovered algorithmic flaws in those hash functions.

We're still struggling with finding a collision in SHA-1 even though it is considered broken in the theoretical sense. The hash output size of MD5 is not considered large enough for most applications, but it would still be quite a problem to find a pre-image or even a collision using brute force.

SHA-2 and SHA-3 output sizes are out of reach - and will be out of reach - for the foreseeable future, even though the security provided by SHA-224 is below 128 bits (which many believe is about the minimum security you should strive for nowadays).

The amount of computing power required for collision attacks increases exponentially (doubles for each two bits added to the output size). So the amount of computing power does not really threaten the security of secure hashes with large output size.

---

Hash functions are usually based on simpler cryptographic primitives, and there should be provable reductions from the security of the hash function itself to that of the underlying primitives. Thus I'm wondering whether there exists a hash function whose algorithm design is provably secure (given that the underlying primitives are secure), and its overall security only depends on the length of variables. Such an algorithm can be easily extended to cope with increasing computation power without much effort.

Is there such an extendible algorithm? If so, what is it?

Most of the hash constructions are build up the way you've described. Merkle-Damgärd is used for SHA-2 while SHA-3 uses a sponge construction (using the function $f$ as underlying primitive).

The underlying primitives can usually not be extended to any length / size of the internal state by simply altering a variable. The functions use constants and algorithms for specific word sizes. What is possible is to create multiple versions of the underlying primitives for different sizes of the internal state and output size. This is exactly what has happened for SHA-2 and SHA-3 (Keccak).

It is however unnecessary to go beyond 256 bits of security. Either the underlying primitive / hash construction is broken or the construction stays secure for forever.

And why do people keep inventing new algorithms instead of extending this algorithm?

Because we have doubts on the underlying primitive and the construction itself. Even a secure block that we consider secure (we cannot prove that either) may not be secure for use in a secure hash function. Furthermore there may be specific properties of the construction that become problematic even if the hash is still formally secure. SHA-2 is vulnerable to length extension for instance, while SHA-3 is not.

And don't underestimate the curiosity and drive of individual researchers. There does not need to be any theoretical reason for new hash functions to be published.

Answer 2

I would agree with Maarten that the reasons behind your question appears to be misplaced.

However, there is at least one example of such a hash function known; the VSH-DL hash function, which is based on a variant of the discrete log problem.

Answer 3

Modern password hash functions (PBKDF2, bcrypt, scrypt, Argon2), all have a cost parameter. The higher the cost parameter, the slower the function runs, or the more memory it uses. This can be used to keep up with increasing computation power.

Even with the cost parameter, new developments sometimes call for new algorithms. For example, PBKDF2 has a cost parameter that increases the number of computations. However, it is still easily parallelizable and can be easily computed on GPU's or specialized hardware. In contract, scrypt uses a lot of memory which makes implementation on other hardware more expensive. Argon2 has both computation time and memory cost parameters.