1
$\begingroup$

If I know that MD5 input is limited to a character set. can I find any information on the input based on the output?

example:

input consists of 16 character from list of [1,2,3,4,5].

question:

based on the md5 output is there any way to find out information about the input? I.e. which character was at the beginning or that the input mostly consists of a particular character?

$\endgroup$
0
$\begingroup$

Let's begin with what is MD5;

  • MD5 has a 128-bit digest size, 512-bit block size Merkle–Damgård construction based hash function created by Ronald Rivest in 1992.

    From a secure hash function we want, 128-bit pre-image and secondary pre-image resistance, and 64-bit collision resistance. MD5 collision resistance is broken, and finding collision can be done in minutes.

    There is an attack on the pre-image resistance of MD5 that has $2^{123.4}$-cost however, due to the memory cost, you would not go in this way instead you will run full brute force or better build the parallel machine.

Pre-image attacks

  • Today's largest known collective computer power is the bitcoin miners that can reach $\approx 2^{92}$ SHA2d calculations per year. This means that even they need 35-years to find one.

  • The current best practical attack on the pre-images is when there are multiple targets ( we can always have if one still uses MD5 without salts, etc.). Build the parallel brute force machine and use Oechslin's rainbow table;

    for $t$ targets built $t^2$ parallel machine with $p$ success probability for finding the first target, you need $2^{128}p/t$ area*time cost. This is much better than the brute force of a single target. See more here.

  • There is also Grover's unstructured quantum search algorithm to be considered that reduces the search time into the square root of it. If built, then (ignoring running cost) the search time will be around $2^{64}$.

It can also be parallelized; however, building $k^2$ machine will provide $k$ speed-up.

based on the md5 output is there any way to find out information about input? like which character was in the beginning or input mostly consists of which character?

No, what you are describing is actually destructive to pre-image resistance.

If you can find the first character (byte) then the pre-image resistance is fall to $c \cdot 2^{120}$ where the $c$ is the cost of determining the first character. The next question will be what is preventing the attacker to determine the next byte, then next? Hash functions are designed to have an avalanche effect that it changing one-bit of the input should have affect all the output bits randomly, i.e. all of the output bits flip with 50%.

If you can figure out the character space by looking at the hash ( let assume that there is an oracle that tells us this), like 5 numbers, then the pre-image search is crippled if you look into 128-bit information, $5^{16} \approx 2^{38}$. This doesn't mean that the pre-image has to be found in this 128-bit space. Still, we can look at the string length 32 and the search time will be $2^{76}$-time

Or, actually, you are asking something like that;

  • If the input space is low as 16 characters from $[1,2,3,4,5]$ then this is the short input space problem on the hash functions. Since the calculation of the hash is free, one can easily search these values. $2^{38}$ search space can be easily reached by today's ordinary CPUs.

    To mitigate this you can use a keyed hash function like $\operatorname{HMAC-MD5}(k,m)$. As long as the key is kept secret, then you are fine. Note that, if there is no restriction to use MD4, prefer $\operatorname{HMAC-SHA-256}(k,m)$

actual problem is I have a SHA-256 string as input(64 characters and hex) and I want to show MD5 of this input to my users and it's important that they can't find any information based on the MD5 output. I want to know if its a short input space or not

A hex is 4 bits that you will have $4^{64}$ input space to search; that is $2^{128}$-bit. This is too high for a single target. However;

  • If the $t$ users can come together and can build the parallel machine using the rainbow tables then they can find the first target on $2^{128}p/t$ area*time cost. So, you can tune your number with this information.
$\endgroup$
2
  • $\begingroup$ actual problem is I have a SHA-256 string as input(64 characters and hex) and I want to show MD5 of this input to my users and its important that they cant find any information based on the MD5 output. I want to know if there is a possibility of them finding anything about the SHA-256 input $\endgroup$ – Mojtaba Jan 19 at 18:51
  • $\begingroup$ @Mojtaba you should have definitely mentioned that on the Q. Updated the answer. $\endgroup$ – kelalaka Jan 19 at 19: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.