6
$\begingroup$

I am researching on Hashing Algorithms and would like to know if we take individual bits of MD5, say we take first 8 bits or any random 8 bits of MD5 then what is the randomness probability of having same 8-bits (at exactly the same position) in any two different MD5 hashes ?

I´ve read somewhere that MD5 being good PRF has uniform randomness in each individual bit. Is this statement true? Also, is there any reference for this?

| improve this question | |
$\endgroup$
  • 1
    $\begingroup$ depends on the input. Is it allowed to be chosen by an attacker? $\endgroup$ – SEJPM♦ Jul 10 '15 at 19:41
  • $\begingroup$ Lets say attacker can choose the input but what if we add 128-bit random text to the input before MD5 hash is done. (which means even if attacker chooses the input the input to MD5 will be different in each case) How does that affect the randomness of each bit of MD5 ? $\endgroup$ – rijndael Jul 10 '15 at 19:50
  • 3
    $\begingroup$ Please tell me you are not using MD5 in a real system. $\endgroup$ – mikeazo Jul 10 '15 at 19:51
  • $\begingroup$ No its just a research interest. $\endgroup$ – rijndael Jul 10 '15 at 19:53
  • $\begingroup$ So if an attacker sends you $A$ and $B$, you'll return him $H(A||R_1)$ and $H(B||R_2)$ with the R's being random strings? I think one can apply MD5 collision attacks against this... (not 100% sure though...) $\endgroup$ – SEJPM♦ Jul 10 '15 at 19:56
5
$\begingroup$

MD5 was designed with the goal that any change in the input uniformly affects all the bits of the output. It's not perfect, but it's pretty good. If you're choosing the input "randomly enough" (e.g., by appending random bits before hashing) then your question approaches this one:

Given two randomly generated 8-bit strings, what is the probability that they match?

This is $\frac{1}{2^{8}}$.

References:

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer and link. I have a query that should we consider bit difference you have mentioned is based upon the binary data right ? Like either it can be 0 or 1 and hence for 8 bits it can be 1/2^8 $\endgroup$ – rijndael Jul 12 '15 at 1:24
  • $\begingroup$ Yes, that's right - a bit is binary by definition. MD5 takes an input of arbitrary length - any number of bits - and produces 128 bits of output. Typically this output is displayed as a string of 32 hex digits. $\endgroup$ – rphv Jul 12 '15 at 20:43
  • $\begingroup$ MD5 output is uniformly random in each case of MD5 ? I mean for any random input given to the MD5, the hash generated is uniformly random ? (the probability of output collision is equal in each case) Thank you. $\endgroup$ – rijndael Jul 12 '15 at 22:09
  • $\begingroup$ Yes, that's correct. Given random inputs, the output of MD5 is statistically uniformly random. MD5 is "broken" not because the distribution of its outputs is skewed, but because careful cryptanalysis showed that it's possible to create inputs that yield specific outputs. However, these "special" inputs are few and far between when compared to the space of all possible inputs, so they don't really affect the statistical properties of MD5's output. $\endgroup$ – rphv Jul 13 '15 at 1:39
  • $\begingroup$ Thanks for the answer. Is there any reference which says MD5 output is uniformly random ? $\endgroup$ – rijndael Jul 13 '15 at 18:03

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.