1

I know it's not possible to reverse an MD5 hash back to its original value. But what about generating a set of random characters which would give the exact same value when hashed? Is that possible?

Egemenk
  • 307
  • 3
  • 9
  • Search reverse md5 in google. – huysentruitw Jul 31 '12 at 20:56
  • What exactly do you want to know? If there is more than one message fitting a hash, or if you can efficiently construct some message that fits a given hash? – CodesInChaos Jul 31 '12 at 21:07
  • You "know" wrong ;) It's possible; just difficult. – Billy ONeal Aug 01 '12 at 18:36
  • @BillyONeal I'm pretty sure that what I 'know' is right. Gigabytes of data can be digested to a 16 bytes hash. You may find out a short string when given a hash. But this doesn't mean that the process is reversible. – Egemenk Aug 04 '12 at 15:16
  • @Egemenk: If you can try all 2^128 possabilities, then you can brute force the hash. I never said it was *practical* but there's nothing that makes it *impossible*. (Just might take a few centuries) – Billy ONeal Aug 05 '12 at 01:06
  • @BillyONeal: 128 bits is the length of the hash, not the actual data. It's the output of the MD5 function, you can't try possibilities with the output. The output is a limited set (2^128 as you said) but the input is infinite. Please look at this thread: [link](http://stackoverflow.com/questions/330207/how-come-md5-hash-values-are-not-reversible) – Egemenk Aug 05 '12 at 08:11
  • @Egemenk: But I don't need to find the exact input to break your system, I only need to find one input that corresponds to that output; and that's a bounded set. When the size of the input gets larger you just end up adding duplicates to the output set. See [Birthday Paradox](http://en.wikipedia.org/wiki/Birthday_problem). – Billy ONeal Aug 05 '12 at 19:43
  • @BillyONeal: This is from my first post: 'I know it's not possible to reverse an MD5 hash back to its original value.' And you replied with: 'You "know" wrong ;) It's possible; just difficult.' So you said it's possible to reverse a hash to its original value. And now you are talking about 'breaking my system'? I think this is the time that you should admit that you were wrong. – Egemenk Aug 05 '12 at 20:07
  • @CodesInChaos Is this talking about overlapping? i.e someString gives the same hash as anotherSomeString? – SaidbakR Jul 25 '13 at 23:04

5 Answers5

4

Finding a message that matches a given MD5 hash can happen in three ways:

  1. You guess the original message. For passwords and other low entropy messages this is often relatively easy. That's why we use use key-stretching in such situations. For sufficiently complex messages, this becomes infeasible.
  2. You guess about 2^127 times and get a new message fitting that hash. This is currently infeasible.
  3. You exploit a pre-image attack against that specific hash function, obtained by cryptoanalyzing it. For MD5 there is one, with a workfactor of 2^123, but that's still infeasible.

There is no efficient attack on MD5's pre-image resistance at the moment.

There are efficient collision attacks against MD5, but they only allow an attacker to construct two different messages with the same hash. But it doesn't allow him to construct a message for a given hash.

CodesInChaos
  • 106,488
  • 23
  • 218
  • 262
  • Two things: 1) due to the birthday paradox, the chances of a random collision is actually approximately 2^64, not 2^128 for a 128-bit hash. 2) Wang and Yu (the people who found the same hash algorithm) published a paper on attacks against MD5 that can be carried out (in their words) in as little as 15 minutes; see merlot.usc.edu/csac-f06/papers/Wang05a.pdf. – Palladium Jul 31 '12 at 21:24
  • @Palladium Both of these apply to collisions, and not to pre-images. I know there are efficient collision attacks, and mentioned that it the last sentence. Finding a message matching a given hash is no collision, but a pre-image. So those attacks are not relevant here. – CodesInChaos Jul 31 '12 at 21:25
  • I had thought hashing basically as a function like f(x+z)=y. If we are given y=100 we can never know x and z. they can be 50 and 50 or 11.111 and 88.889 etc. but we can enter 20 and 80 to the function and get 100 without knowing the real x and z. I wanted to know if an approach like this is possible with MD5. – Egemenk Jul 31 '12 at 21:28
3

Yes it is possible to come up with a collision (since you map from a larger space to a smaller this is something that you can assume to happen eventually). Actually MD5 is already considered as "broken" in this respect.
From wiki:

However, it has since been shown that MD5 is not collision resistant;[3] as such, MD5 is not suitable for applications like SSL certificates or digital signatures that rely on this property. In 1996, a flaw was found with the design of MD5, and while it was not a clearly fatal weakness, cryptographers began recommending the use of other algorithms, such as SHA-1—which has since been found also to be vulnerable. In 2004, more serious flaws were discovered in MD5, making further use of the algorithm for security purposes questionable—specifically, a group of researchers described how to create a pair of files that share the same MD5 checksum.[4][5] Further advances were made in breaking MD5 in 2005, 2006, and 2007.[6] In December 2008, a group of researchers used this technique to fake SSL certificate validity,[7][8] and US-CERT now says that MD5 "should be considered cryptographically broken and unsuitable for further use."[9] and most U.S. government applications now require the SHA-2 family of hash functions.[10]

Cratylus
  • 52,998
  • 69
  • 209
  • 339
  • 1
    The OP doesn't want a collision, he wants a pre-image. – CodesInChaos Jul 31 '12 at 20:57
  • @CodesInChaos:I think he asks if a collision is possible.I don't understand that he wants some algorithm to generate the sequence – Cratylus Jul 31 '12 at 20:59
  • 1
    I think he has a given md5 hash, and wants some message that fits it. A collision attack does not offer this. – CodesInChaos Jul 31 '12 at 21:05
  • @CodesInChaos:I am not sure I follow you. If you have 2 messages that hash to the same value you have a collision.So my understanding is that he is trying to see if it is possible for an MD5 scheme that this occurs. Perhaps he also wants to know how to do it... – Cratylus Jul 31 '12 at 21:08
  • As I understand the OP he has a given md5 hash. And he want to know if given that hash it's possible to find a message that matches it. The answer is that this is possible in principle, but takes to much computation power to be done with our current knowledge. – CodesInChaos Jul 31 '12 at 21:11
2

In one sense, this is possible. If you have strings that are longer than the hash itself, then you will have collisions, so such a string will exist.

However, finding such a string would be equivalent to reversing the hash, as you would be finding a value that hashes to a particular hash, so it would not be any more feasible than reversing a hash any other way.

murgatroid99
  • 19,007
  • 10
  • 60
  • 95
2

For MD5 specifically? Yes.

Several years ago, an article was published on an exploit of the MD5 hash that allowed easy generation of data which, when hashed, gave a desired MD5 hash (well, what they actually discovered was an algorithm to find sets of data with the same hash, but you get how that can be used the other way around). You can read an overview of the principle here. No similar algorithm has been found for SHA-2, although that may change in the future.

Palladium
  • 3,723
  • 4
  • 15
  • 19
0

Yes, what you're talking about is called a collision. A collision in any hashing mechanism is when two different plaintexts create the same hash after being run through a hashing algorithm.

Mike T
  • 1