How come MD5 hash values are not reversible?

Question

Hey everyone,

One concept I've always wondered about is the use of cryptographic hash functions and values. I understand that these functions can generate a hash value that is unique and virtually impossible to reverse, but here's what I've always wondered:

If on my server, in PHP I produce: md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

When you run that same string through an MD5 function, you get the same result on your PHP installation. A process is being used to produce some value, from some starting value.

Doesn't this mean that there is some way to deconstruct what is happening and reverse the hash value?

What is it about these functions that makes the resulting strings impossible to retrace?

Cheers,

Answer 1

The input material can be an infinite length, where the output is always 128 bits long. This means that an infinite number of input strings will generate the same output.

If you pick a random number and divide it by 2 but only write down the remainder, you'll get either a 0 or 1 -- even or odd, respectively. Is it possible to take that 0 or 1 and get the original number?

Answer 2

Cody Brocious's answer is the right one. Strictly speaking, you cannot "invert" a hash function because many strings are mapped to the same hash. Notice, however, that either finding one string that gets mapped to a given hash, or finding two strings that get mapped to the same hash (i.e. a collision), would be major breakthroughs for a cryptanalyst. The great difficulty of both these problems is the reason why good hash functions are useful in cryptography.

Answer 3

MD5 does not create a unique hash value; the goal of MD5 is to quickly produce a value that changes significantly based on a minor change to the source.

E.g.,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(Obviously that's not actual MD5 encryption)

Most hashes (if not all) are also non-unique; rather, they're unique enough, so a collision is highly improbable, but still possible.

Answer 4

But this is where rainbow tables come into play. Basically it is just a large amount of values hashed separetely and then the result is saved to disk. Then the reversing bit is "just" to do a lookup in a very large table.

Obviously this is only feasible for a subset of all possible input values but if you know the bounds of the input value it might be possible to compute it.

Answer 5

A hash collision is much more likely than you would think. Take a look at the birthday paradox to get a greater understanding of why that is.

Answer 6

by definition Hash(cryptographic Hash) function :should not be invertible;should not have collisions(least possible).

regd your question : it is one way hash. input (irrespective of length) will generate a fixed size output.(it will be padded based on algo(512 bit boundary for MD5) ). The information is compressed(lost) and practically not possible to generate from reverse transforms.

additional info on MD5: it is vulnerable to collisions. gone through this article recently, http://www.win.tue.nl/hashclash/Nostradamus/

opens source code for crypto hash implementations(MD5 and SHA) can be found at Mozilla code. (freebl library).

Answer 7

If hash functions such as MD5 were reversible then it would have been a watershed event in the history of data compression algorithms! Its easy to see that if MD5 were reversible then arbitrary chunks of data of arbitrary size could be represented by a mere 128 bits without any loss of information. Thus you would be able to reconstruct the original message from a 128 bit number regardless of the size of the original message.

Answer 8

As the number of possible input files is larger than the number of 128-bit outputs, it's impossible to uniquely assign an MD5 hash to each possible.

Cryptographic hash functions are used for checking data integrity or digital signatures (the hash being signed for efficiency). Changing the original document should therefore mean the original hash doesn't match the altered document.

These criteria are sometimes used:

1. Preimage resistance: for a given hash function and given hash, it should be difficult to find an input that has the given hash for that function.
2. Second preimage resistance: for a given hash function and input, it should be difficult to find a second, different, input with the same hash.
3. Collision resistance: for a given has function, it should be difficult to find two different inputs with the same hash.

These criterial are chosen to make it difficult to find a document that matches a given hash, otherwise it would be possible to forge documents by replacing the original with one that matched by hash. (Even if the replacement is gibberish, the mere replacement of the original may cause disruption.)

Number 3 implies number 2.

As for MD5 in particular, it has been shown to be flawed: http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf">How to break MD5 and other hash functions

Answer 9

As most have already said MD5 was designed for variable length data streams to be hashed to a fixed length chunk of data, so a single hash is shared by many input data streams.

However if you ever did need to find out the original data from the checksum, for example if you have the hash of a password and need to find out the original password, it's often quicker to just google (or whatever searcher you prefer) the hash for the answer than to brute force it. I have successfully found out a few passwords using this method.

Answer 10

A good way to think of a hash algorithm is to think of resizing an image in Photoshop... say you have a image that is 5000x5000 pixels and you then resize it to just 32x32. What you have is still a representation of the original image but it is much much smaller and has effectively "thrown away" certain parts of the image data to make it fit in the smaller size. So if you were to resize that 32x32 image back up to 5000x5000 all you'd get is a blurry mess. However because a 32x32 image is not that large it would be theoretically conceivable that another image could be downsized to produce the exact same pixels!

That's just an analogy but it helps understand what a hash is doing.

Answer 11

I'm probably wrong here, but surely during md5 encryption, a certain number of options would give the same single bit result, if you saved which option was used for that satge then surely reversal is possible?

For example

If i turn all 5's into either a 3 or a 2 then

55555 --> 32232

So if i haave another number saying which option each of those is: 12212

then with 12212 and 32232 i can get the result 55555

Sorry if that doesn't make any sense

Answer 12

Now a days MD5 hashes or any other hashes for that matter are pre computed for all possible strings and stored for easy access. Though in theory MD5 is not reversible but using such databases you may find out which text resulted in a particular hash value.

For example try the following hash code at http://gdataonline.com/seekhash.php to find out what text i used to compute the hash

aea23489ce3aa9b6406ebb28e0cda430

Answer 13

If string ABC is hashed by some HASH function ,Are the result every time same ?

HASH(ABC) =string A

again

HASH?(ABC) = string B

string A = string B ???