Can hashes like MD5 be used to rebuild data?

[E_tron]

Hashes like MD5 can tell you whether a file is bad or not, right?

I've got to wonder, can a hash be used to "guess" what data a file should contain? For example, I retrieve a hash of a data file and allow a computer to rebuild (by trial and error) a matching data file.

[akruppa]

Hashing algorithms are specifically designed to be hard to invert. If the modified data is relatively small (a 32 bit word, say) and you know the likely location of it, you might try an exhaustive search.

Alex

[Jushi]

Originally Posted by E_tron

Hashes like MD5 can tell you whether a file is bad or not, right?

I've got to wonder, can a hash be used to "guess" what data a file should contain? For example, I retrieve a hash of a data file and allow a computer to rebuild (by trial and error) a matching data file.

No, and for more than one reason: The MD5 hash (and others) have been specially made to make sure what you're asking is computationally impossible. It would simply take too much time to find by "trial and error" a file with a given hash. It this were possible, then MD5 would be considered cracked.

Digital signatures rely on this: you don't really sign a message, you sign a hash of the message. So, if I get a signed message from you, the only thing I know is that you signed a message with this particular hash. Of course if the hash matches the message, I assume you signed that message. But there are recent attacks against MD5 which make MD5 not suitable anymore for this.

Going back to your question, let's suppose that one could generate a file with a given hash. Then how would you know it's the correct file? An MD5 hash is 128bits long, so lots of files have the same hash. Even if you only look at 20-byte files, you expect about 4 billion files with any given hash.

[ColdFury]

No, unless our understanding of computational theory is very wrong.

[xilman]

Originally Posted by ColdFury

No, unless our understanding of computational theory is very wrong.

Careful. Under certain circumstances, the answer is "yes". Alex has already stated this but perhaps his example wasn't understood. Here is another version.

Suppose we have a one megabyte file and, further, we know that precisely one bit has been changed but we do not know which one. Suppose, further, we do know the MD5 hash of the correct data. We can recreate the original data for the cost of 2^23 MD5 computations.

The algorithm is very simple: flip each bit in turn (there are 2^23 of them in a megabyte) and compute the MD5 hash of the that data. With overwhelmingly high probability (roughly 2^105 to 1) all the hashes will be different and precisely one of them will match the correct MD5 hash. The data with that hash will be the correct version we are looking for.


Paul

[Paulie]

Slightly off topic, but:

MD5 is broken. SHA is broken.

The same hash for different plaintexts. :

http://www.schneier.com/cgi-bin/sear...ken&Realm=blog

[ColdFury]

Originally Posted by Paulie

Slightly off topic, but:

MD5 is broken. SHA is broken.

The same hash for different plaintexts. :

http://www.schneier.com/cgi-bin/sear...ken&Realm=blog

SHA-1 is broken, SHA-256 and the rest are not currently. Cryptologists have been telling people not to use MD5 for quite some time.