reverse engineering an MD5 algorithym??

hi. i am designing a "forgot password" page and i got to the point where i need to reverse engineer the password entered by the user. the current passwords are stored as MD5 hashes in an XML user file. I did some net reading and every link (that i found) seems to say that you can't reliably reverse engineer the MD5 hash???? is that true? how do i take the current encrypted passwords in the XML file and return the original entry to the user?? i am designing in VB.NET. links or code would be much appreciated.

thanks in advance....

You can't. An MD5 hash is a numerical representation of, in your case, a string. It is conceptually similar to a checksum. A checksum might be implemented by adding the ASCII values of all of the characters of a string. For example, the string "blah" would have a checksum of 407 (decimal) using this algorithm. While there are likely to be other strings that would also have the checksum of 407 (the string "lahb" would) you cannot say with any degree of confidence which string created the checksum.

The MD5 algorithm is far more complicated than I described but the concepts are the same. You can't take the numerical representation of the checksum of the string and go backwards.

In most systems like you have a "forgot password" feature is implemented by generating a random string, saving that string as the password, and somehow informing the user of their new password - email is a common way.

You would use whats known as "rainbow tables" if you wanted to do this especialy in any usefull amount of time (opposed to a real time brute force), and even so with these there are a probability factor involved (usualy over 99% though, this is due to whats known as "collisions"). If I was you I would just use the old e-mail a new password script.

hey, thanks for your replies juniper and stdunbar. I can't believe that you can't reverse engineer the algorithym but, what you said makes sense stdunbar. I took both of your advice and designed a method that reissues a temporary password.

Thanks again.

It's kinda like a one to many relationship in a database? One checksum can have multiple string counterparts but one string only has one hash? So a checksum would be concieveably fairly easy to crack because every checksum only has a certain number of posiblities to evaluate to the checksum. That's where MDx came in.

There is no "conceptual feasibility" that any two messages can have the same 128-bit MD5 sum. Here there is padding (adding bit until the message is 64-bits away from being a multiple of 512-bit. This is just the start. If you want to read more check out this RFC 1321 - MD5 message-digest algorithm rcf document/memo. It explains, in detail, what is done to a message to create the 128-bit MD5 hash.

There was an MD4 but it was droped for MD5 and other reasons...just read the rfc if you're still interested in it.

This is known as a "collision" and Actualy that was proven wrong by the same people that cracked SHA-1 which is even more secure then MD5 (SHA1 is 160bit). "raindow tables" are a compiled list of hashes from words (basicly they are like a dictionary of hashes for a given combination of charecters) I believe a 14 character password table would be 10GB in size, with these you can break an MD5 password in less then an hour.

"On 17 August 2004, collisions for MD5 were announced by Xiaoyun Wang, Dengguo Fen, Xuejia Lai and Hongbo Yu [1]. Their attack was reported to take only one hour on an IBM P690 cluster."

To stay on topic:


If you can reverse engineer your security system programatically, why would you trust this security system at all?

I knew that MD5 was comprimised hence the quotations.
I found a little info on MD5 and SHA-1. Ever since reading this thread I'm obesed with it.

I'm trying to find the current "best" hasing algorithm, for future reference. So far I found that the use of MD5 should be replaced with WhirlPool, SHA-1 or RIPEMD-160. I found that there are several other SHA algorithms, like SHA-0(predating SHA-1) SHA-380, SHA-512 and others. However, because of discoveries on similar-to-SHA-1 algorithms, it will be phased out by 2010(by the US Gov't) for SHA-2, whcih I can't find any info on other than it might be one of SHA-240, SHA-380, SHA-512, or whatever, maybe SHA-2 is still incomplete.

Further discoveries lead me to find that SHA-2 is a collection of the three previosuy mentioned algorithms: SHA-256, SHA-384 and SHA-512. I found this information on the CPAN site .

I'm guessing that the use of one of these newer SHA family algorithms would be a good choice, I'm not entirely sure though.

Not that I need it for anything I'm just really interested, if you know of any resources where I can fine more information on cryptography that would be great. I'm scouring google now.

Found one, but I'm just starting to read it.
http://world.std.com/~franl/crypto.html

might want to read some of these PDFs

http://packetstormsecurity.nl/papers/cryptography/

or read here

http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html

The SHA has just recently hit the hashing scene, it's most likely best best alternative to md-5, but it's still in development. Like most new things, it's not exactly a good hash to use to store need-to-keep info IMHO for the time being.

"recently" - 1993
"in development" - Why do you think so? There is SHA0, 1, 2 and 256, and all of them are complete AFAIK.
"not exactly a good hash ... IMHO" - I don't think too many people share your oppinion. What are your objections to SHA if I may ask?

M.

Actually There is SHA 0 SHA 1 and a group of four(SHA 224, SHA 256, SHA 384, and SHA 512) collectivly known as SHA 2. As far as I can find SHA 2 is the best hashing algorithm.

Wikipedia - SHA family