2
$\begingroup$

Is it mathematically possible to adapt a given hash function (f.e. SHA-1 or MD5) so it performs a known number of iterations at once?

Concrete example would be:

data = SHA1_10000(data)

instead of:

for (i = 0; i < 10000; i++) data = SHA1(data)

while resulting in the same output, but being 10000 times faster.

$\endgroup$
  • $\begingroup$ What you ask is not possible via modification to hash. However, you could be interested in Merkle tree (also known as hash tree), which is a way to use hash that (in some settings) allows gaining speed by enabling (amongst other things) parallel computation of blocks of input. $\endgroup$ – user4982 Jan 28 '18 at 15:29
6
$\begingroup$

If you would find something like this, it would probably even point to a weakness in the hash function.

Impossiblity in the random oracle model. Hash functions are often assumed to behave like random oracles (i.e., for every new query they return a uniformly random value, while answering consistently for repeated queries). For a random oracle, the output is not defined before querying the random oracle at the input - so in this model it should be relatively easy to argue that it is impossible to find what you are asking for.

$\endgroup$
2
$\begingroup$

In many instances, although we want computing a hash to be polynomial in time, we do not want it to be too fast since this will make it easier for an attacker to brute force finding a pre-image. Hashes are therefore constructed in a way to make the computation as serial as possible to slow them down, even using very parallel architectures like GPUs.

$\endgroup$
  • $\begingroup$ Indeed. We can't make the total computation require much less work than 10000 hashes (as stated in the other answer). And also, we can't make it much faster than 10000 times the duration of a single hash, no matter how much hardware we throw at it. $\endgroup$ – fgrieu Jan 28 '18 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.