• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

FAQ | Search | Usergroups | Profile | Register | RSS | Posting Guidelines | Recent Posts

Reversing the MD5.

Users browsing this topic:0 Security Fans, 0 Stealth Security Fans
Registered Security Fans: None
Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

View previous topic :: View next topic  
Author Message
dominant
Just Arrived
Just Arrived


Joined: 26 Mar 2004
Posts: 0


Offline

PostPosted: Sun May 02, 2004 6:03 pm    Post subject: Reversing the MD5. Reply with quote

Does anyone know where could i find the implementation of MD5 hash function (in C if possible).

Has anyone ever tried to reverse this function and what is the difficulties to do that?
Back to top
View user's profile Send private message
Sgt_B
Trusted SF Member
Trusted SF Member


Joined: 28 Oct 2002
Posts: 16777215
Location: Chicago, IL US

Offline

PostPosted: Sun May 02, 2004 6:50 pm    Post subject: Reply with quote

This topic has been disucssed before here at SFDC. Use the SEARCH function before you post, as it could save you a lot of time.
Have a look at this thread:
http://www.security-forums.com/forum/viewtopic.php?t=11701

Pay heed to ShaolinTiger's post, as it points to a couple of other nice threads on the subject of MD5.
Back to top
View user's profile Send private message Visit poster's website
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Sat May 08, 2004 6:38 pm    Post subject: Reply with quote

hi,
there is an attack by Hans Dobbertin, about finding collisons in md5. Its not about reversing md5 though.

Regards,
Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Sat May 08, 2004 6:47 pm    Post subject: Wary. Reply with quote

datah wrote:
hi,
there is an attack by Hans Dobbertin, about finding collisons in md5. Its not about reversing md5 though.


Right, that of which I have mentioned here; the link, of which, contains a plethora of superb research and analysis references on hash functions themselves, and hash function-based primitives. A bulk of the interest in cryptanalyzing MD5 lies within its compression function, and is essentially the one aspect that leaves most of us cryptographers wary of even suggesting its utilization any longer, where security holds the most precedence.
Back to top
View user's profile Send private message Visit poster's website
dominant
Just Arrived
Just Arrived


Joined: 26 Mar 2004
Posts: 0


Offline

PostPosted: Sat May 08, 2004 7:20 pm    Post subject: Reply with quote

Well, has anyone ever tried to exploit that compression flaw of MD5.
It would be intresting to hear some reviews on how much it took!
Back to top
View user's profile Send private message
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Sat May 08, 2004 7:56 pm    Post subject: Certainly. Reply with quote

dominant wrote:
Well, has anyone ever tried to exploit that compression flaw of MD5.
It would be intresting to hear some reviews on how much it took!


Certainly. Consult the RSA Laboratories' bulletin from November 12, 1996, by Matt Robshaw, found here, in PDF format. As aforementioned, it contains numerous, highly-informative references to cryptanalyses of MD5, as well as MD2, MD4, and various other general hash function constructs. Among these references include analyses by renown cryptographic designers, such as Preneel, den Boer, Bosselaers, Dobbertin, Bellare, Rogaway, Rivest, Merkle, Wiener, and van Oorschot - just to name a hand-full. You might find it interesting that even in 1996, we could successfully produce collisions on the compression function of MD5, using extensions of past MD4 cryptanalysis, in around 10 hours on a PC. Also, there are so many other important mathematical situations to consider, such as the birthday paradox and meet-in-the-middle attacks, which are essential in understanding much of the design criteria for a secure hash function. I'd suggest researching any and every aspect of collision attack methodology, to get the full taste of just how critical any cryptanalytical attack of this nature, or resilience to such, is, when determining just how volatile the security of a hash function can be.
Back to top
View user's profile Send private message Visit poster's website
dominant
Just Arrived
Just Arrived


Joined: 26 Mar 2004
Posts: 0


Offline

PostPosted: Sat May 08, 2004 9:34 pm    Post subject: Reply with quote

Ok.
Concerning the meet-in-the-midle attack, i think that has nothing to do with the MD5 implementation and its flaw as well.
Back to top
View user's profile Send private message
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Sat May 08, 2004 11:00 pm    Post subject: Even if variationally. Reply with quote

dominant wrote:
Ok.
Concerning the meet-in-the-midle attack, i think that has nothing to do with the MD5 implementation and its flaw as well.


I didn't directly state that it did. However, indirectly, it's a notion that should definitely be taken into account.

When designing a secure structure, for use as a hash function, this branch of collision attack methodology, closely related to birthday attacks, is an extremely real concern to base a design criterion on. Be it a generic look at a generic, traditional hash function, a hash-based block cipher, a block cipher-based hash function, or a hash-based MAC, there are many scenarios where this is an imminent threat, broadly speaking. The fact is, many hash functions are built, in part, to thwart these methodological attacks; so, it has something to do with it, even if variationally.
Back to top
View user's profile Send private message Visit poster's website
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Sun May 09, 2004 8:42 am    Post subject: Reply with quote

hi,

birthday attack is about finding two randomly chosen messages m1 and m2 and see if they hash to the same value.

meet in the middle is about encrypting the plain text with key1(all its combinations) at one end and decrypting the cipher text with key2(all its combinations) and see where there is a match. This is again about seeing in how many checks two texts will give the same match. in that sense meet in the middle attack is closely related to the birthday attack. We will get a faster search result,when we take two texts at random and se they match, where as checking the table sequentially for a match will take a longer time.

Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
dominant
Just Arrived
Just Arrived


Joined: 26 Mar 2004
Posts: 0


Offline

PostPosted: Sun May 09, 2004 2:09 pm    Post subject: Reply with quote

Alright,

In order to exploit the MD5 we should try 2^64 strings. 2 of them will give the same hash value. Has this practical means except its scientific means?
Back to top
View user's profile Send private message
data
Forum Fanatic
Forum Fanatic


Joined: 08 May 2004
Posts: 16777211
Location: India

Offline

PostPosted: Sun May 09, 2004 6:38 pm    Post subject: Reply with quote

hi,

yes,we can do practical attacks. Say that you have two texts m1 and m2 that hashes to the same value. You have written a random number generator+hashing utility that is used by your boss.
The boss, requests a random number from the utility,it gives him m1. He computes y=H(m1) and uses it as a digital signature and keeps the random number secret.

Now you can compute y=H(m2) and forge the boss's signature.

Regards,
Data.
Back to top
View user's profile Send private message Visit poster's website Yahoo Messenger
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Sun May 09, 2004 6:54 pm    Post subject: Definitely practical. Reply with quote

dominant wrote:
Alright,

In order to exploit the MD5 we should try 2^64 strings. 2 of them will give the same hash value. Has this practical means except its scientific means?


It is very practical, given a particular route. The more practical route is rendering two messages, m and m', that share the same hash output value, as opposed to finding an m that shares the same hash value as the given hash of m'. Roughly, the former (a collision attack) only takes 2^m/2 random message hashes, while the latter (essentially an exhaustive search) takes 2^m random message hashes, where "m" is bits of output. Such a birthday attack can operate in negligible time, in many cases. A bit about the importance of this can be read in, "Just How Secure ARE Those 128-bit Keys?"

Birthday attacks and meet-in-the-middle attacks are commonly housed under collision attack methodology, as a whole, and do share variationally similar characteristics. The latter is more flexible and commonplace, than the former, but they both have applicable properties, and essentially fall under similar genres. "Cousins", if you will.

To put that in perspective, nearly 9 years ago, a machine capable of performing one million hash operations per second would take approximately 600,000 years to complete, if you took the exhaustive search route. However, using the birthday attack approach, you could do this in a comfortable hour, with the same machine.


Last edited by JustinT on Thu Jun 17, 2004 12:17 am; edited 1 time in total
Back to top
View user's profile Send private message Visit poster's website
dominant
Just Arrived
Just Arrived


Joined: 26 Mar 2004
Posts: 0


Offline

PostPosted: Tue May 11, 2004 9:40 am    Post subject: Reply with quote

meet-in-the-middle attacks to obtain the prehashed secret number. or not?
Back to top
View user's profile Send private message
JustinT
Trusted SF Member
Trusted SF Member


Joined: 17 Apr 2003
Posts: 16777215
Location: Asheville, NC, US / Uberlāndia, MG, Brazil

Offline

PostPosted: Tue May 11, 2004 10:07 pm    Post subject: Just being general. Reply with quote

dominant wrote:
meet-in-the-middle attacks to obtain the prehashed secret number. or not?


I was referring to hash function design, and concatenation of hash functions with other primitives in a much more broad scheme, such as authentication via HMAC, or even the usage of block ciphers as hash functions and the usage of hash functions as block ciphers. The point is, meet-in-the-middle attacks do have relevance to hash function design and utilization, including how MD5 may be used; this isn't confined to just MD5, and how it operates as a standalone hash function. Think about the bigger picture. Through wider application, such as adaptation to real life, practical, efficient situations, some of the most influential cryptanalysis arises.
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   

Post new topic   Reply to topic   Printer-friendly version    Networking/Security Forums Index -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security All times are GMT + 2 Hours
Page 1 of 1


 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Community Area

Log in | Register