View previous topic :: View next topic |
Author |
Message |
dominant Just Arrived
Joined: 26 Mar 2004 Posts: 0
|
Posted: Sun May 02, 2004 6:03 pm Post subject: Reversing the MD5. |
|
|
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 |
|
|
Sgt_B Trusted SF Member
Joined: 28 Oct 2002 Posts: 16777215 Location: Chicago, IL US
|
Posted: Sun May 02, 2004 6:50 pm Post subject: |
|
|
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 |
|
|
data Forum Fanatic
Joined: 08 May 2004 Posts: 16777211 Location: India
|
Posted: Sat May 08, 2004 6:38 pm Post subject: |
|
|
hi,
there is an attack by Hans Dobbertin, about finding collisons in md5. Its not about reversing md5 though.
Regards,
Data.
|
|
Back to top |
|
|
JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlāndia, MG, Brazil
|
Posted: Sat May 08, 2004 6:47 pm Post subject: Wary. |
|
|
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 |
|
|
dominant Just Arrived
Joined: 26 Mar 2004 Posts: 0
|
Posted: Sat May 08, 2004 7:20 pm Post subject: |
|
|
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 |
|
|
JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlāndia, MG, Brazil
|
Posted: Sat May 08, 2004 7:56 pm Post subject: Certainly. |
|
|
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 |
|
|
dominant Just Arrived
Joined: 26 Mar 2004 Posts: 0
|
Posted: Sat May 08, 2004 9:34 pm Post subject: |
|
|
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 |
|
|
JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlāndia, MG, Brazil
|
Posted: Sat May 08, 2004 11:00 pm Post subject: Even if variationally. |
|
|
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 |
|
|
data Forum Fanatic
Joined: 08 May 2004 Posts: 16777211 Location: India
|
Posted: Sun May 09, 2004 8:42 am Post subject: |
|
|
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 |
|
|
dominant Just Arrived
Joined: 26 Mar 2004 Posts: 0
|
Posted: Sun May 09, 2004 2:09 pm Post subject: |
|
|
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 |
|
|
data Forum Fanatic
Joined: 08 May 2004 Posts: 16777211 Location: India
|
Posted: Sun May 09, 2004 6:38 pm Post subject: |
|
|
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 |
|
|
JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlāndia, MG, Brazil
|
Posted: Sun May 09, 2004 6:54 pm Post subject: Definitely practical. |
|
|
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 |
|
|
dominant Just Arrived
Joined: 26 Mar 2004 Posts: 0
|
Posted: Tue May 11, 2004 9:40 am Post subject: |
|
|
meet-in-the-middle attacks to obtain the prehashed secret number. or not?
|
|
Back to top |
|
|
JustinT Trusted SF Member
Joined: 17 Apr 2003 Posts: 16777215 Location: Asheville, NC, US / Uberlāndia, MG, Brazil
|
Posted: Tue May 11, 2004 10:07 pm Post subject: Just being general. |
|
|
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 |
|
|
|