Luigi Auriemma

usually you can recover/crack MD5 hash with rainbow tables, bruteforce or with wordlists, but i found something intresting in google.
http://technocrat.net/d/2006/3/21/1500 ..this page.
..i read it that and searched for some extra in google...but still not clear whats this about.
is it really possible to recover ANY MD5 hash in almost no time ?

I think that article is just referring to md5 collisions (which are known about) not actually cracking or reversing hashes to their original form.

So if the hash to gain access to my secret account is 5d41402abc4b2a76b9719d911017c592, you could find an alternate string of text that also has the same MD5 (because of collisions) and gain access to my secret account without ever knowing my original password (which for that MD5 is the word hello). That is the problem MD5 has.

But there is no known way to reverse md5 hashes to their original form. The only way to unmask them would be with brute force, wordlists, rainbow tables, etc. as you mentioned (of course then it's just cracking, not unmasking).

A good website I use from time to time to see if I can figure out a hash is http://gdataonline.com/. Over 168 million hashes and counting :P

to khmer: ..its not about cracking them. I have cracking rate of 80-90%. thats avarage i usually get. Im just in middle of the 20000 hash cracking .. and i have 85% so far...i haven't used brute-force and some of my rainbow tables yet. I wanted to know if its possible to reverse ANY md5 hash in no time.

to SomaFM: ..that explains a lot actually. so basically what you are saying is : one MD5 hash can be generated using 2 different strings ?
that must contain some special symbols ? .. otherwise they would conflict ?
BUT....does it even matter which string i use if both makes out one MD5 hash ?
example - if strings ''hello'' and ''goodbye'' has SAME MD5 sum ..and you have ''hello as password in forum and i enter ''goodbye'' then I should get access to your account ?!

isnt there some kind of known formula that is used to calculate md5 sums ? maybe exploring that will give some idea (im sure that a lot of ppl have already done that) ..im still curious :)

-------------------------------------------------------------------------------------
edited/updated: here's something you would like to know maybe ?!
if site has 170 million hashes...then rainbow tables has like 1000 billions ...in it.
-------------------------------------------------------------------------------------
Rainbowtable:
charset - abcdefghijklmnoprqstuvwxyz0123456789 (loweralpha-numeric)
lenght - 1-8 chars.
size - 36gb (36 tables)
-------------------------------------------------------------------------------------
Wordlist:
charset - abcdefghijklmnoprqstuvwxyz0123456789 (loweralpha-numeric)
lenght - 1-8 chars.
size - 26947.1gb (one list), its almost 27tb ..its MASSIVE!!!
-------------------------------------------------------------------------------------
since md5 hashes are WAY longer (32chars) than 1-8 wordlist...then they would take like 10 times more space than wordlist.

"one MD5 hash can be generated using 2 different strings ?"

due to the hashing nature of the algorithm it's true the opposite: 2 strings can have the same MD5 hash.

This is not a mistery since as we know a 128 bit number cannot contain all the possible combination of bytes of the world, but the real point is: when the collisions start to happen?

The following is one implementation of the MD5 algorithm:

http://xyssl.org/code/source/md5/md5.c

hmmm...i was thinking that ..
how many strings can have same md5 sum then ?
can it be that like 10 strings has same md5 sum ?
32 characters is maximum lenght of string that can be converted into md5 hash right ? ..then its logical that many of strings has same md5 sum. just never tought about it before :S

Actually, strings longer than 32 characters can be converted to MD5, as there is no limit imposed on the hashing algorithm. So I think that would mean there could be an infinite number of collisions, as you could just keep extending the string length/complexity and changing characters until a collision is encountered. It would take a lot of time and processing power, but it could be done.

However, you would be limited by the amount of memory in the machine that is calculating the hash, because it would have to run the entire string through the hashing algorithm in memory.

Interesting thing happened with the popular PHPBB forum package the other day. They used to store password hashes in the database as pure MD5. But in release candidate 6 of phpbbv3, they have implemented a new hashing algorithm that appears much more secure. I haven't checked exactly how they do it now, but in a forum I administrate that runs phpbbv3, my password hash now contains symbols and non hexadecimal characters (unlike MD5 which only uses hexadecimal characters).. so it appears much more secure than MD5.

about this speed and memory thing ... using passpro or cain .. i can make md5 hash instantly .. even if ill put in like 32 chars...never tried longer ones.
i was just testing some cracking methods..so i needed to convert 32 char string into MD5 hash...and it did it instantly.

yes i know that phpbb uses md5 :)
hmm .. i gonna check at this very moment, but im SURE that my phpbb 3 RC5 uses normal MD5 hashes...some forums ..phpnuke i think .. uses salted md5 hashes..still easy to crack.
..and yes my phpbb 3 version RC5 uses normal MD5 hashes. ..i gonna try to crack my own hash to make sure that its md5.


One more thing about same md5 sums...
basically its possible that some 50 characters long string has same MD5 sum with some 4 characters long string ?!

You probably won't see huge issues or delays in today's machines with short strings like you're using. But when you start dealing with md5 hashes for file sizes that are MB or even GB in size, you will start to see some delays when running them through the hash algorithm.

As for phpbb, they did use plain md5 up until RC5, but once you goto RC6+ there is a new hashing method. You can see how it works in the /includes/functions.php file.

And yes I would say that it's possible for a string 50 chars long to have the same md5 hash as one with 4 characters. I wouldn't know of any, or an easy way to test, but I wouldn't doubt the possibility.

An MD5 hash can hold 256^16 possible combinations. A 50 character string has 256^50 possible combinations. This means there will be 256^(50-16), or 7.58855 * 10^81, 50 character strings that hash to the same value as any 4 character string.

Hash functions aren't magic, they can't generate unique hashes regardless of the input size. What they are designed for is to make it impractical to find collisions, i.e. you should theoretically have to check 2^128 different strings to find a single MD5 collision. Because it is possible to find collisions by checking fewer than 2^128 strings, MD5 is considered broken.

about phpbb3 .. now i have RC7 and gonna check it again ...download db and check.
so calculating like 500 character string into md5 wont take over second ?
..its just a scary tought that my 16 character password (max in hotmail) in hotmail can have same md5 sum with some 3 or 4 chars long string lol.

exactly how many million or billion combinations can md5 hash hold ?

The MD5 hash is 128 bits wide, so 2^128 or 340,282,366,920,938,463,463,374,607,431,770,000,000 different keys.

While there are many 16 character strings that have the same hash value as a 4 character string, the chance of choosing one at random is extremely low. There are 4,294,967,296 hashes for 4 character strings compared to 340,282,366,920,938,463,463,374,607,431,770,000,000 for 16 character strings, so the chance that a random 16 character string has the same hash as ANY 4 character string is 1 in 79,228,162,514,264,337,593,543,950,336. Even if you limit the characters to alphanumeric/symbols (26*2 for letters + 10*2 for numbers/symbols = 72 characters), the chances only fall to 1 in 19,408,409,961,765,342,806,016.

http://www.winimage.com/misc/readfile_test.htm has some speed tests for CRC32/MD5. Hashes like MD5 and SHA are relatively slow compared to straightforward algorithms like CRC32, but can still process a lot of data (up to 340mb/sec on an AMD64 3000+).

yeah it is really small chance that my 16 char. string has same md5 sum with some 1-4 char string, but still possible. hehe.
anyways im still thinking about easier way to find collisions. im pretty sure its possible.