2
$\begingroup$

Is there such thing as "hash reset sequence" that brings hash to the same known state?

A hash function has a state. In MD5 and others vulnerable to the length extension attack, the attack works by continuing computation from existing hash.

So, the question here is - when I continue computing hash, is it possible that there is a sequence of data that will start moving the hash function output into some known corridor with known results? Similar to http://numericana.com/answer/magic.htm#1089 and other magic tricks.

$\endgroup$
3
  • $\begingroup$ You can google "hash reset sequence" and see that the only hits it gets are for your question so you could have figured out yourself it doesn't exist. $\endgroup$ Nov 17, 2015 at 15:08
  • $\begingroup$ @NeilSmithline okay, so there is no sequence of data that will start moving the hash function output into some known corridor with known results? Similar to numericana.com/answer/magic.htm#1089 and other number tricks. $\endgroup$
    – techtonik
    Nov 17, 2015 at 15:15
  • $\begingroup$ I don't think so but am not sure. That's why I didn't answer the question. The answer below says no. This is something that you should be able to test with a simple script or something. $\endgroup$ Nov 17, 2015 at 15:18

1 Answer 1

3
$\begingroup$

Answering the most general interpretation first, yes, it is possible for some piece of data to take the state to some known state. This is because the compression function that moves from one state to the next necessarily has collisions, because its inputs are larger than outputs. For most states you would expect a single block of data to be enough to take you to any state.

However, such a one-block sequence would not apply universally, it would take from one particular state to the desired state. Finding such a sequence for a particular predetermined (current, desired) pair would amount to a preimage attack on the compression function, which we cannot do in the case of MD5. Best attacks take close to the $2^{128}$ time that brute force does.

If you wanted a sequence that took you from any state to a known state, you would need even more computation. Such a sequence might exist, but it could be long: e.g. if with each block you could halve the possible states you would need $2^{127}$ blocks. A brute force approach would be completely infeasible even in comparison to the earlier attack. Even using the sequence could be infeasible.

Finally, the full state of MD5 is not just the current state vector that the compression function affects. There is also the total length processed (modulo $2^{64}$), which is used when finalizing the value. So you could not use a single "reset sequence" as a literal reset, because it would not take two different-length prefixes to the same full state. (If you had an "universal reset sequence" you could first pad the inputs to the same length, but you would still need to know the lengths.)

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.