3

Let's imagine that we have a particularly bad hashing algorithm that, given any input, will output 1 of only 100 possible hashes.

Now lets imagine that 2 of these possible hashes, when hashed again, produce the same output, all other inputs are evenly distributed and no there are no loops* (e.g. a->b->a is not possible).

I think this means that if we keep hashing enough times, eventually we would end up with only 1 possible output.

This means that, for this particularly bad hashing algorithm, hashing a hash is a bad move if you want to avoid collisions.

Q: How many iterations would it take with common algorithms for this to be a concern? Or is there some feature of a good algorithm that means this is not an issue, even after an infinite number of iterations?

* regarding loops, I mean no loops that don't include the colliding bucket i.e. if c->x and d->x then although a->b->a is not possible, a->c->x->a might be.

N.B. This question is about accidental collisions, not forced ones.

4
  • If it is not collision resistant then the composition is also not resistant, however for a proper answer whether it ends up in the 1 possible output or not, we need the real definition. One can easily define one that ends up in two hash values, odd ones get hash value one and even ones get hash value two. What is the origin of this question? Why do you need such a hash function while you can use SHA-256, SHA3, BLAKE2...
    – kelalaka
    Commented Nov 23, 2021 at 15:49
  • Note that, your first sentence is not exactly clear. Does the hash function can output only 100 values or for any input there are only possible 100 values or your hash function is constant?
    – kelalaka
    Commented Nov 23, 2021 at 16:18
  • Please see the linked example
    – DJL
    Commented Nov 24, 2021 at 7:47
  • 1
    For real hashes, it is already studied 1, 2...
    – kelalaka
    Commented Nov 24, 2021 at 18:06

1 Answer 1

1

Using multiple rounds of hashing effectively increases the odds of a collision.

But not by much.

Let's say your hash function has X possible outputs, with equal probability:

  • The chance of getting a collision after 1 round is 1/X.
  • The chance of getting a collision after N rounds is lower than N/X.

Since modern algorithms have a very large X, way larger than whatever N could possibly be in our universe, N/X is basically 0.

This means that the impact is basically non-existant, unless your input or your hash function has been designed to trigger collisions.

2
  • I think you've assumed here that the distribution is 100% even. While good algorithms may get close to this, I would be very surprised if any actually acheives it. How does that affect the maths?
    – DJL
    Commented Nov 23, 2021 at 14:33
  • 1
    @DJL: as long as the distribution is quite reasonable, it's still secure. If an output is M times more probable than any other random one, then the collision odds basically becomes (M * N / X). X is still very very large, and it's still very unlikely that M * N is anywhere close to it. Commented Nov 23, 2021 at 14:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .