Dunno if this is old news, but:


Using their technique, an MD5 collision can be found in a matter or hours!!!


http://www.md5crk.com/
http://eprint.iacr.org/2004/199.pdf

...sounds pretty bad for systems using MD5 passwords?
Posted on 2004-09-08 08:17:59 by f0dder
Hi...

I've read the pdf from China...

If I well understood it is possible to find several messages being same MD5...

But knowing MD5 it is, see almost impossible to re-fund message...

Their method find two messages being same MD5 but this MD5 is not known...

But by knowing a Signed Hash it is almost impossible to forge a file keeping same Signed Hash...one must know the PrivateKey...

Therefore this article is not bad and only prove that one can find several message being same hash...

I think I well explained that...

Try to read my folder ---->http://pageperso.aol.fr/gerardchap/Cryptography.zip for forgry of Signature with ElGamal....it is very similar...

Now about MD5 password one can hold same reasoning...

Gerard...
-----------
Posted on 2004-09-09 13:27:22 by gerard
Of course you can't find original message from a MD5 digest - the original message could be megabytes large, and MD5 certainly isn't ;)

What makes this interesting, then? People using MD5 hashes as passwords. Who cares if you don't find the original password, if you find something causing a collission, you will still get in.
Posted on 2004-09-09 13:32:20 by f0dder
I think you didn't understand me...

One can find several messages being same hash...
that it is easy...

But their method only proves that...and doesn't permit to find a message which will work...

Knowing a message (great) it is impossible to find initial M message

( http://www.bibmath.net/crypto/moderne/md5.php3 )....such as M1 and M2 being same hash...

Gerard...
-----------
Posted on 2004-09-09 13:44:59 by gerard
I think you didn't understand me...

One can find several messages being same hash...
that it is easy...

But their method only proves that...and doesn't permit to find a message which will work...

Knowing a message (great) it is impossible to find initial M message

( http://www.bibmath.net/crypto/moderne/md5.php3 )....such as M1 and M2 being same hash...

Gerard...
-----------


I dont understand your point exactly, also this link you provided is on french.
But what we have here and what f0dder is trying to say is something that can be used in real world to breach the security.
Here is the example, AFAIK unix/linux stores passwords as MD5 hash in passwd file, so even if you acquire that passwd file you will be unable to get root password since MD5 does not have inverse function. Now with this new knowledge, one can just get MD5 hash of the root password, then find some string that will have same MD5 as the one from passwd file and he will be easily 0wn the b0x :-D
Ofcourse this is just simplified example, but taking into account widespread of unices/linux servers in the world, this can easily became headche for all of us.
Posted on 2004-09-09 16:20:31 by Mikky
hi,

collisions mean that is possible find 2 random strings that have the same md5sum... not that is possible find a string that give you a specific md5sum(as the one from a password)

ancev
Posted on 2004-09-09 18:19:19 by ancev
Thanks ancev you arrived to express what I wanted to tell...

The knowledge of a specific MD5 doesn't permit to find two values M giving a coliision...therefore, collision made are usefull for the moment...

The problem of security hold rather in length of Key (DDS ) ...

In our days a length of 512 bits is still secure....but in 15 years one must find keys with size of key of 1024 see 2048...



Gerard...
-----------
Posted on 2004-09-09 22:47:18 by gerard
The knowledge of a specific MD5 doesn't permit to find two values M giving a coliision...therefore, collision made are usefull for the moment...
What f0dder was saying is that it is not essential to actually know the hash, you can still run a brute force attack on the system that uses it and you have a greater chance of breaking the system because there is the possibility of a collision.
Posted on 2004-09-10 03:14:10 by sluggy
Hi...

First

Originally posted by f0dder:
Dunno if this is old news, but:


To answer to that----> Know that :
CALG_SSL3_SHAMD5 exists since a certain time try to see ---->
http://pageperso.aol.fr/gerardchap/Provider.zip

and to answer to--->

Originally posted by sluggy:
What f0dder was saying is that it is not essential to actually know the hash, you can still run a brute force attack on the system that uses it and you have a greater chance of breaking the system because there is the possibility of a collision.


I don't understand what you hear by brute force attack....Try to give me more clues...

Gerard...
-----------
Posted on 2004-09-10 03:30:45 by gerard
While I'm familiar with the idea of hashing and so forth, I'm not terribly familiar with the math behind it (and of course, their methods for finding collisions). Is it possible that a combination of MD5 and say, SHA, could be used in conjunction? For instance, suppose your password has MD5 hash '123' and SHA hash '456'. Does the problem of finding a collision between two hash functions make the problem less tractable?
Posted on 2004-09-10 05:02:56 by Miko
Hi...

I found what you mean by brute force attack ---> a attack in the wild...

It is a little true that a neophyte has more chance to break a code...

An expert has too much notion in head and has a lot of confidence in his knowledge and in this of others that he doesn't think to find a solution to use it but only to improve code...

Code made by an expert often uses a knowledge of high level and in this fact he saw almost all the possiblities except the more brutal one.... ...For example ATM can be stolen by force i.e. to arrach ATM from the wall and open it to take BankNote...(In France they do that....but now exists an ink to cover BankNote when carriage is opened with Force)...

Gerard...
-----------

*ATM: electronic cash machine...(Automated Teller Machine)
Posted on 2004-09-10 05:05:38 by gerard
The point f0dder is making is that a password authentication system operates thus:

pass_string = GetText("Enter your password:");
pass_hash = MD5(pass_string);

if (pass_hash == stored_hash)
permission_granted = true;


So in order to gain access to the system we need to grab the stored_hash value (this may or may not be a problem, depending on the system), and secondly find some string that creates a matching hash.
The point is that the string used to create the hash does not need to be the same as the original password, it just needs to create the same hash to gain access.

If MD5("ABC") == MD5("XYZ") == stored_hash,
then either "ABC" or "XYZ" are valid passwords!

If you find one that matches, who cares if it's the same one as the official user password?

Mirno
Posted on 2004-09-10 05:22:14 by Mirno
mirno,

when this happen, then the cipher is said broken

collisions dont allow you to find another string that matches md5sum X. it allow 2 strings have the same md5sum, but these strings must have some properties, not any arbitrary 2 strings

in others words, the md5sum you?re trying to match need come from a 'special' string.

as the chance of having a password string with these special properties to have collisions is very narrow, its not a big threath to security i think... its more of mathematical interess

ancev
Posted on 2004-09-10 17:53:48 by ancev
didn't the paper say that they same attack could be levied against SHA. I forget where it was but didn't it say 80,000 cpu hours or some sort.

Anyways what other hashing algorithsm are their that are suitable for usage?
Posted on 2004-09-11 13:40:18 by archphase
A little joke about hash...

All know Da Vinci ...his famous Mona Lisa ....

In the folder below you will find two paintings ...and will see that it is not easy to find two messages having same hash...


One painting is that of Da Vinci (1452-1519) the other-one from Octavio Ocampo (1943-????)

A little humour is sometimes weel-seen...

Gerard...
---------
Posted on 2004-09-11 13:40:24 by gerard