Is it possible to decrypt MD5 hashes?

Someone told me that he has seen software systems that:

1. retrieve MD5 encrypted passwords from other systems;
2. decrypt the encrypted passwords and
3. store the passwords in the database of the system using the systems own algorithm.

Is that possible? I thought that it wasn't possible / feasible to decrypt MD5 hashes.

I know there are MD5 dictionaries, but is there an actual decryption algorithm?

Solution 1:

No. MD5 is not encryption (though it may be used as part of some encryption algorithms), it is a one way hash function. Much of the original data is actually "lost" as part of the transformation.

Think about this: An MD5 is always 128 bits long. That means that there are 2¹²⁸ possible MD5 hashes. That is a reasonably large number, and yet it is most definitely finite. And yet, there are an infinite number of possible inputs to a given hash function (and most of them contain more than 128 bits, or a measly 16 bytes). So there are actually an infinite number of possibilities for data that would hash to the same value. The thing that makes hashes interesting is that it is incredibly difficult to find two pieces of data that hash to the same value, and the chances of it happening by accident are almost 0.

A simple example for a (very insecure) hash function (and this illustrates the general idea of it being one-way) would be to take all of the bits of a piece of data, and treat it as a large number. Next, perform integer division using some large (probably prime) number n and take the remainder (see: Modulus). You will be left with some number between 0 and n. If you were to perform the same calculation again (any time, on any computer, anywhere), using the exact same string, it will come up with the same value. And yet, there is no way to find out what the original value was, since there are an infinite number of numbers that have that exact remainder, when divided by n.

That said, MD5 has been found to have some weaknesses, such that with some complex mathematics, it may be possible to find a collision without trying out 2¹²⁸ possible input strings. And the fact that most passwords are short, and people often use common values (like "password" or "secret") means that in some cases, you can make a reasonably good guess at someone's password by Googling for the hash or using a Rainbow table. That is one reason why you should always "salt" hashed passwords, so that two identical values, when hashed, will not hash to the same value.

Once a piece of data has been run through a hash function, there is no going back.

Solution 2:

You can't - in theory. The whole point of a hash is that it's one way only. This means that if someone manages to get the list of hashes, they still can't get your password. Additionally it means that even if someone uses the same password on multiple sites (yes, we all know we shouldn't, but...) anyone with access to the database of site A won't be able to use the user's password on site B.

The fact that MD5 is a hash also means it loses information. For any given MD5 hash, if you allow passwords of arbitrary length there could be multiple passwords which produce the same hash. For a good hash it would be computationally infeasible to find them beyond a pretty trivial maximum length, but it means there's no guarantee that if you find a password which has the target hash, it's definitely the original password. It's astronomically unlikely that you'd see two ASCII-only, reasonable-length passwords that have the same MD5 hash, but it's not impossible.

MD5 is a bad hash to use for passwords:

• It's fast, which means if you have a "target" hash, it's cheap to try lots of passwords and see whether you can find one which hashes to that target. Salting doesn't help with that scenario, but it helps to make it more expensive to try to find a password matching any one of multiple hashes using different salts.
• I believe it has known flaws which make it easier to find collisions, although finding collisions within printable text (rather than arbitrary binary data) would at least be harder.

I'm not a security expert, so won't make a concrete recommendation beyond "Don't roll your own authentication system." Find one from a reputable supplier, and use that. Both the design and implementation of security systems is a tricky business.

Solution 3:

Technically, it's 'possible', but under very strict conditions (rainbow tables, brute forcing based on the very small possibility that a user's password is in that hash database).

But that doesn't mean it's

• Viable
  or
• Secure

You don't want to 'reverse' an MD5 hash. Using the methods outlined below, you'll never need to. 'Reversing' MD5 is actually considered malicious - a few websites offer the ability to 'crack' and bruteforce MD5 hashes - but all they are are massive databases containing dictionary words, previously submitted passwords and other words. There is a very small chance that it will have the MD5 hash you need reversed. And if you've salted the MD5 hash - this won't work either! :)

The way logins with MD5 hashing should work is:

During Registration:
User creates password -> Password is hashed using MD5 -> Hash stored in database

During Login:
User enters username and password -> (Username checked) Password is hashed using MD5 -> Hash is compared with stored hash in database

When 'Lost Password' is needed:

2 options:

• User sent a random password to log in, then is bugged to change it on first login.
  

or

• User is sent a link to change their password (with extra checking if you have a security question/etc) and then the new password is hashed and replaced with old password in database

Solution 4:

Not directly. Because of the pigeonhole principle, there is (likely) more than one value that hashes to any given MD5 output. As such, you can't reverse it with certainty. Moreover, MD5 is made to make it difficult to find any such reversed hash (however there have been attacks that produce collisions - that is, produce two values that hash to the same result, but you can't control what the resulting MD5 value will be).

However, if you restrict the search space to, for example, common passwords with length under N, you might no longer have the irreversibility property (because the number of MD5 outputs is much greater than the number of strings in the domain of interest). Then you can use a rainbow table or similar to reverse hashes.

Solution 5:

Not possible, at least not in a reasonable amount of time.

The way this is often handled is a password "reset". That is, you give them a new (random) password and send them that in an email.