mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-09-22, 05:41   #1
E_tron
 
E_tron's Avatar
 
Sep 2002
Austin, TX

23116 Posts
Default Can hashes like MD5 be used to rebuild data?

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.
E_tron is offline   Reply With Quote
Old 2005-09-22, 07:29   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-09-22, 07:37   #3
Jushi
 
Jushi's Avatar
 
Sep 2005
UGent

22×3×5 Posts
Default

Quote:
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.
Jushi is offline   Reply With Quote
Old 2005-09-23, 02:03   #4
ColdFury
 
ColdFury's Avatar
 
Aug 2002

5008 Posts
Default

No, unless our understanding of computational theory is very wrong.
ColdFury is offline   Reply With Quote
Old 2005-09-23, 09:33   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

1064810 Posts
Default

Quote:
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
xilman is offline   Reply With Quote
Old 2005-09-24, 23:42   #6
Paulie
 
Paulie's Avatar
 
Aug 2002

223 Posts
Default

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

Last fiddled with by Paulie on 2005-09-24 at 23:45
Paulie is offline   Reply With Quote
Old 2005-09-25, 01:38   #7
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26×5 Posts
Default

Quote:
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.
ColdFury is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Erroneous data ATH Data 8 2013-11-13 19:21
GPU TF vs DC/LL data bcp19 GPU to 72 0 2011-12-02 16:41
Manual rebuild of worktodo.txt Unregistered Information & Answers 2 2010-07-08 22:11
Data available? Prime95 LMH > 100M 10 2007-06-22 23:55
P3 data needed Prime95 Software 13 2003-10-02 04:10

All times are UTC. The time now is 21:08.

Mon Apr 19 21:08:31 UTC 2021 up 11 days, 15:49, 0 users, load averages: 4.58, 4.18, 3.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.