6
$\begingroup$

If we start with a set of possible input values, and apply the md5 algorithm to all elements of this set and then filter out the unique results (a.k.a. filter out collision), we are left with a smaller set. Consider this small piece of pseudo code:

Set<String> inputs = ALL_UNIQUE_INPUTS;
while (inputs.length > 1) {
    Set<String> newInputs;
    foreach (String input : inputs) {
        newInputs.add(md5(input));
    }
    inputs = newInputs;
}

I believe that most iterations of the while loop will decrease the size of inputs, untill it reaches 1. Is this true?

Furthermore, can we somehow determine how many iterations this would take for a given input space?

Note: I am aware that you should not attempt to increase the computational complexity of password hashing in this manner, but use salts, reapply those and other neat tricks to make the process more computationally complex whilst not increasing the chance of collisions.

$\endgroup$

migrated from programmers.stackexchange.com Aug 10 '16 at 16:26

This question came from our site for professionals, academics, and students working within the systems development life cycle.

8
$\begingroup$

After about $2^{n/2}=2^{64}$ iterations an input will enter a cycle (of length approximately $2^{n/2}=2^{64}$). If inputs didn't collide by the time they enter a cycle, they never will.

If you have more than about $2^{n/4}=2^{32}$ inputs, you'll get collisions after $2^{n/2}=2^{64}$ iterations, as per birthday-problem. But of course you won't have the patience to wait that long.

$\endgroup$
  • $\begingroup$ The $2^{32}$ in the second paragraph in the current answer is at least short on justification. On the first iteration, odds of collisions are about $2^{-65}$. I believe these odds slightly decrease with the number of iterations, and I have the feeling that for $2^{32}$ inputs and $2^{64}$ iterations, odds that there has been a collision are significantly less than 50%, perhaps vanishingly small. I feel that it is more likely that some cycles have converged, but to different phases, thus have not collided, and will never. $\endgroup$ – fgrieu Jan 9 '17 at 13:36
  • $\begingroup$ @fgrieu I didn't work out the small constant factors. But the rough numbers should be correct. The typical cycle size is $2^{64}$ and there are only a small number of very hairy cycles. So I approximate that there are $2^{64}$ possible phases, with each input input getting a phase at random. So once you have about $2^{32}$ inputs, you get colliding phases, per birthday problem. $\endgroup$ – CodesInChaos Jan 9 '17 at 14:16
  • $\begingroup$ I'm OK that there are about $2^{64}$ points in a typical cycle; and that each input gets a random phase on its cycle; and thus that we are near the collision threshold if most of the $2^{32}$ starting points share the same cycle. But why would that later condition hold? [fixed] $\endgroup$ – fgrieu Jan 9 '17 at 15:49
  • 2
    $\begingroup$ @fgrieu Because almost all of the the space is covered by very few cycles and the forest of hairs leading into them. $\endgroup$ – CodesInChaos Jan 9 '17 at 15:53
  • $\begingroup$ @fgrieu Quick and dirty code to confirm my prediction that you get collision after about $2^{n/4}$ inputs. $\endgroup$ – CodesInChaos Jan 9 '17 at 17:04
3
$\begingroup$

This question was adressed here quite a few times, just differently phrased, for example in Cycles in SHA256.

Another awnser here had the following statement:

Hashes have a fixed size output. After one round, all your new inputs will be equally sized, being the size of the hash output. An ideal hash function operating on such inputs will be bijective and you will constantly just be rearranging your inputs with none of them ever colliding.

Ideal hash function in this sense is quite similar to the definition of a perfect hash function. However, this just does not fit with cryptographic hash functions, where the "ideal" version is a random oracle or a truly random function (with the specified domain), where collisions can happen.

Exactly this question was already adressed here:

But to come back to the question: Cryptographic hashes are designed to be as close to random functions as possible. In an answer to the first linked question, fgrieu drew a really nice visualization here.

A few of the key points of what to expect:

  • The graph is probably disconnected
  • The graph contains cycles of different leangth
  • It might contain fixed points (cycles of length 1)
  • It also contains nodes, which lead to a cycle but are not part of it.

So to answer the initial questions:

I believe that most iterations of the while loop will decrease the size of inputs, untill it reaches 1. Is this true?

No, it can decreate the size of the set. But with a cryptographic hash it is unlikely. The set size only decreases in case of a collision, which is really unlikely (and surely not "most iterations").

Considering the second part of the question: That could happen, but it is unlikely. If we remember the graph of the random function, then the original set have to be

  • in the same connected subgraph.
  • Have a fixed point instead of a cycle; or alternatively there have to be collisions, so that there is only one element in the cycle.

Furthermore, can we somehow determine how many iterations this would take for a given input space?

Well, for practical purposes with MD5: Much, much too long. The cycles can have any length within the graph, and you have to save all previous steps to actually notice that you are in a cycle. With a graph of $2^{128}$ nodes, you would have to estimate the number of nodes in cycles, and then estimate how many values you need to store to be able to determine that you are in a cycle. It is quite likely, you need close to $2^{128}$ steps anyway.

$\endgroup$
  • $\begingroup$ An interesting aspect of the question, not addressed elsewhere that I could find, is that at each iteration the old hashes are forgotten. The problem is thus not if the cycles converge; rather, it is if two cycles that converge will do so with the same phase, such that there will be a collision. That's non-trivial. $\endgroup$ – fgrieu Jan 9 '17 at 13:30
1
$\begingroup$

Your set of inputs will not necessarily reach a single input, and for any well designed cryptographic hash function, it won't.

Hashes have a fixed size output. After one round, all your new inputs will be equally sized, being the size of the hash output. An ideal hash function operating on such inputs will be bijective and you will constantly just be rearranging your inputs with none of them ever colliding.

Evaluating the difference between an ideal hash function and the actual md5 algorithm in this scenario is many PhD's worth of research.

$\endgroup$
  • 4
    $\begingroup$ "An ideal hash function operating on such inputs will be bijective" A hash is no permutation. $\endgroup$ – CodesInChaos Aug 7 '16 at 9:32
  • 1
    $\begingroup$ A hash mapping 128 bit values to 128 bit hash values should be a permutation. Since there are exactly as many possible inputs and outputs, no two inputs should be hashed to the same output. $\endgroup$ – gnasher729 Aug 8 '16 at 8:24
  • 1
    $\begingroup$ @whatsisname Consider an input of 2^128+1 values mapped to 2^128 possible outputs. There exists at least one collision, per pidgeonhole principle. Now remove one of the inputs. Unless it's part of a single colliding pair (unlikely, unless you chose it specifically), the reduced input set will still contain a collision. ---- If the hash function is ideal, the number of inputs mapping to each output is Poisson distributed with an expectancy value of 1. $\endgroup$ – CodesInChaos Aug 8 '16 at 18:27
  • 1
    $\begingroup$ @whatsisname Consider the 2^128 outputs. Then you sequentially map each input to an output. The first input won't cause a collision. The second one lands on an already used output with probability 1/2^128. The third with probability 2/2^128 etc. By the time you reached 2^64 inputs the cumulative probability of a collision has reached about 50%. By the time you're done, a collision is virtually certain. Even if you just consider the last input. If you had no collision so far, it only has a 1 in 2^128 chance of landing on the sole unoccupied output. $\endgroup$ – CodesInChaos Aug 8 '16 at 18:59
  • 6
    $\begingroup$ @whatsisname For a cryptographer, an ideal hash is as close to a random oracle as possible, and not a perfect hash over the 128 bit strings. $\endgroup$ – CodesInChaos Aug 8 '16 at 20:07
1
$\begingroup$

I believe that most iterations of the while loop will decrease the size of inputs, untill it reaches 1. Is this true?

No, not for input that has no pre-computed collisions.

Finding collisions is supposed to be a hard problem for secure hash functions. For SHA-1 none have been published yet at the time of writing, and that's a hash function that is considered pretty weak.

Furthermore, can we somehow determine how many iterations this would take for a given input space?

The chance of an accidental collision over a short input space is very low. The chance of finding a single one is high for a set of $2^{64}$ and probably still significant for $2^{32}$ elements.

In other words, you'll wait forever. Again, for input that has not pre-computed collisions.

Note: I am aware that you should not attempt to increase the computational complexity of password hashing in this manner, but use salts, reapply those and other neat tricks to make the process more computationally complex whilst not increasing the chance of collisions.

I don't know about the other neat tricks, but for MD5 it's easy to find collisions because MD5 is broken. Anybody could create a set of distinct inputs in such a way that the while loop would immediately terminate (once it gets past that, it will probably never end).

Better use a secure hash such as one of the SHA-2 or SHA-3 variants.

$\endgroup$

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.