The simple way to iterate a hash function $H(H(m))$ only makes brute force preimage finding slower, but leaves collision attacks as fast since a collision in the inner hash function is a collision in the overall function.

Is there an iterative algorithm that also slows down brute force collision attacks? Without expanding the output size?

I am looking for something that reduces to the standard properties of the hash function, rather than only working for an ideal hash or a random oracle.

The use case is that a short hash is used, e.g. 128 bits with 64-bit collision resistance. Collision finding attacks should be slowed down sufficiently to be infeasible, e.g. to $2^{100}$ hash function calls.

  • $\begingroup$ Iterating $H_{i+1}=H(m||H_i)$ might work or perhaps $H_{i+1}=H(m||i||H_i)$ is better. $\endgroup$ Sep 17 '15 at 9:37
  • $\begingroup$ @CodesInChaos, both of those seem weak with a Merkle–Damgård hash and probably most other kinds of finite-state hashes that process the message in blocks from left to right. A collision in the first block carries through all iterations. $\endgroup$
    – otus
    Sep 17 '15 at 9:42
  • 1
    $\begingroup$ Yes, that construction assumed an ideal hash. In practice it should work with many wide pipe constructions. That'd be useful in situations where you can use wide hashes internally, but the output size is limited for some reason. $H(i,H_i,m)$ should avoid that issue, though I'm still not sure if it's secure for MD hashes. $\endgroup$ Sep 17 '15 at 9:47
  • $\begingroup$ If this is a practical problem, I'd rather iterate a bijective function or increase the number of rounds in the underlying primitive. $\endgroup$ Sep 17 '15 at 9:50
  • 1
    $\begingroup$ For Merkle-Damgard $h_i = H(pad(h_{i-1})||M)$ could work where pad adds zeros to make the input a complete input block. In this case you rather rely on some pseudorandomness properties of $H$ modelled as a family (similar to HMAC). The output of the last iteration pseudorandomly selects a new function from the family... But no proof for this. $\endgroup$
    – mephisto
    Sep 17 '15 at 10:04

As others have pointed out in the comments, using the message in the hash iteration can dissolve collisions in the inner hash again. Additionally, the round number can also be used, in case you have collisions over different rounds. But concatentation is just one possible way to combine these values as input.

If your assumption is just a general hash function, you should have a function $f$, and then set:

  • $h_1 = H(m)$
  • $h_{i+1} = H(f(h_i,m,i))$

Concatenation might be one possibility for $f$, but it could be problematic in Merkle-Damgard constructions. You could also use a hash function for $f$, but that wouldn't adress this problem. Alternatively, you could use an MAC instead, where you use the hash of the previous round and $i$ to derive the key, and you can choose from the various MAC algorithms. Alternatively, you could also use a block cipher directly as $f$, just like the MAC algorithms (well, some MACs are based on block ciphers). But you will have to keep in mind, that $m$ itself might be a lot longer. A more general way might be the assumption of a PRF.

On a similar note: Alternatively, you could use a CSPRNG based on a hash function, seed it with the message, and then iterate just "far enough", that it matches your wanted number of iterations, and use that as output.

For your consideration of 128 bit, I would say CMAC/OMAC with AES could be used, e.g.$f:= CMAC_{h_i}(m||i)$

  • $\begingroup$ A lot of good ideas, but is there a proof for any of them? I'll probably accept this either way, since I ended up going a completely different use in the original use case. $\endgroup$
    – otus
    Oct 7 '16 at 14:57
  • $\begingroup$ Unfortunately, I don't think you can prove this in general, if we have to consider cryptanalysis of the hash function, e.g. a prefix collision attacks. In order to get a working proof for any common cryptographic hash function, $f$ would have to be a random oracle or something similar (not sure if a PRF would work, if you consider changing input for the key). $\endgroup$
    – tylo
    Oct 10 '16 at 11:46
  • $\begingroup$ Yeah, I'm starting to think that's true. $\endgroup$
    – otus
    Oct 10 '16 at 13:38

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.