• RSS
  • Twitter
  • FaceBook

Security Forums

Log in

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

Improved Collision Attack on 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
JustinT
Trusted SF Member
Trusted SF Member


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

Offline

PostPosted: Sun Nov 20, 2005 10:46 am    Post subject: Improved Collision Attack on MD5. Reply with quote

From my recent attempt at a weblog:

http://www.justintroutman.org/blog/ wrote:

I was skimming through the newer papers on IACR's ePrint archive, and noticed a recent contribution which proposes an improved collision attack on MD5, by Sasaki, Naito, Kunihiro, and Ohta, from the University of Electro-Communications, in Japan. Their technique is probabilistic, and works with a probability of 1/2; the complexity is around $2^{30}$. You can find the paper, and abstract, here.
Back to top
View user's profile Send private message Visit poster's website
mjuarez
Just Arrived
Just Arrived


Joined: 15 Jun 2004
Posts: 0


Offline

PostPosted: Wed Nov 23, 2005 3:08 am    Post subject: Is it useful to even ponder about MD5 any longer? Reply with quote

I was just wondering, with all the press getting excited recently over additional MD5 vulnerabilities... why are people still even thinking about it? IMHO, it's like talking about new vulnerabilities being discovered in the original DES algorithm. It hardly matters any more, at least theoretically, as the crypto community has been saying, for quite some time now, that MD5 should not be used anymore (not that they listen, in any case).

Could it be possible that most of the people out there (press included), still have no idea about better hashing algorithms than MD5?

Just wondering,

Marcos
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: Sun Nov 27, 2005 12:22 am    Post subject: Here's hoping my point surfaces amongst this verbosity! Reply with quote

mjuarez wrote:
I was just wondering, with all the press getting excited recently over additional MD5 vulnerabilities... why are people still even thinking about it? IMHO, it's like talking about new vulnerabilities being discovered in the original DES algorithm. It hardly matters any more, at least theoretically, as the crypto community has been saying, for quite some time now, that MD5 should not be used anymore (not that they listen, in any case).

Could it be possible that most of the people out there (press included), still have no idea about better hashing algorithms than MD5?


Well, it's certainly true that quite a bit of press is generated amongst the community of those who have a very incomplete, superficial understanding of cryptography. They associate only without house-hold name primitives, such as DES, AES, and MD5, and when it comes to covering a story on cryptanalysis, it's not always done so properly, or hyped up in ways that it shouldn't be. However, there is an element of benefit in continuing to analyze these primitives, even after the cryptographic community has long suggested migration from them. It's not just because of legacy applications where they'll still be used, but because of the structure they represent.

Consider that the MD4 family - MD5 and SHA-1 included - which are source-heavy, heterogenous Unbalanced Feistel Networks, which basically use a block cipher to form a compression functions, in the Davies-Meyer construction. Up until this point, the majority of conventional hash functions have been built on the same (or similar) recycled principles, and most all of them were subjected to the cryptanalysis of Wang et al. (My thoughts are summed up, here, which includes my thought that it's vital to look into something new - a fresh paradigm for designing secure hash function primitives (i.e., using an SPN in the Miyaguchi-Preneel scheme, based on the wide trail strategy, perhaps.)

By continuing with analysis of such a "popular" primitive, we can potentially gain a better understanding about the security of hash functions that are built this way, and if there are any efficient "tweaks" for altering existing designs to offer more security. This applies in similar regards, to the Feistel structure of DES or the SPN structure of AES, and their respective design principles, which have been borrowed by many primitives, as well. Sometimes, when there's a primitive that cryptanalysts are most interested in (i.e., DES, AES, et cetera), we learn a lot about other structures that are based on those primitives. There have been cases (even recent ones) where cryptanalysis of DES, AES, and MD5 have led to applying the same cryptanalysis to other primitives that borrow components from their design strategies.

Cryptanalysis - especially of hash functions - shouldn't be about whether or not a primitive is secure enough to even consider implementing; in the case of a primitive such as MD5, on which many designs have been based off of (MD4, as well), cryptanalysis should be about understanding the structure of our conventional hash functions, what can be done to tweak the existing structure (i.e., pre-processing, interleaving, et cetera) and the trade-offs involved in doing so (i.e., security versus efficiency), and what new directions we should look towards. It comes down to the fact that we simply need to know more about hash functions, and continuing to cryptanalyze the most widely deployed and analyzed functions we already have, we help ourselves.

Now that MD5 and SHA-1 (along with the stigma associated with anything with a prefix of "SHA") have been targeted, a bulk of the general Joe and Jane User class has nothing else to associate with. Not cryptanalyzing it [MD5] won't stop the uninformed from making uninformed decisions on which primitives to use and which not to use. In many cases, they make far worse cryptographic mistakes. The more cryptanalysis that is performed, the better prepared we'll be, come time that we consider a new standard hash function; this will, hopefully, give the aforementioned layman's class something secure to associate with. In the meanwhile, it seems plausible to conclude that if cryptanalyzing helps us arrive at some sense of what it will take to design more secure hash functions, then it's far from being redundant.

And too, although you have quite a few uninformed consumers roaming about, you also have a plethora of incompetent vendors peddling insecure products to those consumers. The Internet is saturated with misinformation, and that's not a problem that cryptography is designed to solve. So, what may seem like plain incompetence on behalf of those looking for solution, may really be due to being misled by those supplying a solution. Enough resources are available to educate folks on how to go about making conservative choices, so let's hope they migrate to SHA-256, perhaps, as an interim solution, in the meanwhile. So, you could say that continuing with cryptanalyzing such hash functions does more for progressing our knowledge of how to design secure ones, than not continuing does to reduce the cluelessness of the general population. In this matter, I'm more concerned with the former, because it's a cryptographic problem; the latter isn't.
Back to top
View user's profile Send private message Visit poster's website
MattA
Trusted SF Member
Trusted SF Member


Joined: 13 Jun 2003
Posts: 16777193
Location: Eastbourne + London

Offline

PostPosted: Mon Nov 28, 2005 4:12 pm    Post subject: Reply with quote

I'm not sure if this or is not the code you're talking about for finding the collisions, but you might just find it interesting.

http://www.stachliu.com.nyud.net:8090/md5coll.c
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: Sun Dec 04, 2005 11:58 pm    Post subject: Actually. Reply with quote

MattA wrote:
I'm not sure if this or is not the code you're talking about for finding the collisions, but you might just find it interesting.

http://www.stachliu.com.nyud.net:8090/md5coll.c


Actually, that source code seemingly implements the attack from Wang, et al., while the improved collision attack I mention in the first post of this thread is due to the work of Sasaki, et al. In fact, I came across the Slashdot article which discusses the source code, around the same time I started this thread. I just didn't post a link to it, and thought of starting a new thread for it. I found myself caught up with other things, so thanks for posting it. Dwonis mentioned it to, in this thread, where we reference most all of the significant papers which discuss hash function collision attacks, for anyone interested in reading more about that. Cheers, Matt.
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