2
$\begingroup$

I have learned that SHA-1 and MD5 are one way hash functions, which means that it is not possible to obtain the original value by performing the reverse calculation.

There however some online websites that 'decrypt' the hash function to the original value. I tried decrypting in the Linux command line but it seems that the input can only be hashed using sha1sum command.

I'm just curious if the reverse calculation is possible or not.

$\endgroup$
  • 1
    $\begingroup$ You cannot decrypt a hash, you can however potentially find other pieces of information that would have that same hash; these are collisions. Just because you find some piece of information that hashes to your original hash, does not (necessarily) mean it is the original value. $\endgroup$ – Kritner Jun 10 '18 at 12:58
7
$\begingroup$

MD5, SHA-1, SHA-256, etc. are one-way functions: given the hash of an input, nobody knows how to find the input better than by guessing, and the best cryptographers in the world have tried.

But guessing is always a possibility. You just try a lot of inputs until you find one with the desired hash value. If the input is a member of a small set, for example if you know it's a dictionary word, this can be done very quickly. On the other hand, if the input includes enough unknown bits, it's unfeasible. For example, if the input includes 128 random bits, then it would take a billion PCs about the age of the universe¹ to get a decent chance of finding the right input.

The websites you found don't “decrypt” anything. What they do is, they calculated a lot of hash values and stored them in a database. When you ask them to reverse a hash, they look it up in the database. This only works if the hash is one that they have in the database.

¹ Say 2³⁰ calculations per second per computer, times 2³⁰ computers. The age of the universe is about 2⁶⁰ seconds, giving you a 2⁻⁸ chance of success.

$\endgroup$
1
$\begingroup$

No, they cannot be decrypted. These functions are not reversible. There is no deterministic algorithm that evaluates the original value for the specific hash.

However, if you use a cryptographically secure hash password hashing then you can may still find out what the original value was. These functions were designed to produce hash codes for big volumes of data / files. That is why they were designed to be very fast. It is relative easy to calculate MD5 and SHA1 hashes over a big number of inputs and use that to create a reverse lookup table.

There are many web sites that do it for free. Just one example is here: http://md5decrypt.net/en/. Enter there d0763edaa9d9bd2a9516280e9044d885 and press "Decrypt".


If the reason of your question is the question What algorithm should I use for password hashing?, look up for "password stretching". Depending on what platform you are using consider bcrypt, scrypt, argon2.

$\endgroup$
  • $\begingroup$ Also for password hashing PBKDF2 is an acceptable choice (per NIST). Furtherer there is a cost or work factor and that needs to be chosen to require a minimum amount of CPU time, generally around 100ms. $\endgroup$ – zaph Jun 10 '18 at 10:48
  • $\begingroup$ Cooperation of NIST with NSA made NIST not trustworthy. It is not that any decision of NIST is bad. They are all professional decisions. But without any independent researches their recommendations are questionable. One of more or less independent competitions was PHC 2015: password-hashing.net. $\endgroup$ – mentallurg Jun 10 '18 at 11:40
1
$\begingroup$

To add to Gilles and mentallurg answers: Hash functions can not be decrypted also in sense that there are infinitively (or nearly infinitively) many inputs that give the same output (since the size of input is arbitrary or nearly arbitrary and length of output is fixed), so you'll never know which one is the "right" one.

$\endgroup$
  • $\begingroup$ If I know that the message is relatively small or has a certain structure (e.g. consists solely of readable text, has a specific format or values) then it would be rather easy to verify correctness. It's a good observation, but it doesn't directly answer the question. $\endgroup$ – Maarten - reinstate Monica Jun 12 '18 at 13:37
  • 2
    $\begingroup$ Note that actually most hash functions specify an upper bound on the input length, so it's not actually infinite. $\endgroup$ – SEJPM Jun 12 '18 at 13:38
  • $\begingroup$ @SEJPM, quick look through standards shows that MD5 (RFC 1321) doesn't specify any upper bound on message length, while SHA-1 and SHA-2 family of algorithms do. Edited the answer. $\endgroup$ – Strigo Jun 12 '18 at 21:41
  • $\begingroup$ @MaartenBodewes in practice you are right (most often when we speak about password hashing). But strictly speaking even for short inputs with certain structure there can be several inputs that gives the same output. $\endgroup$ – Strigo Jun 12 '18 at 21:49
0
$\begingroup$

A different way to see the problem would be through the communication point of view.

If you were able to revert any hash, then you could hash a 1GB file resulting if a 128 bit hash for SHA1 for instance. Then it could mean that you could send the hash through a channel and revert it at the other side. That would be almost unlimited transference of data through a channel and unlimited compression.

That would be a violation to the Shannon's theorem which states that there is limit to the amount of data could be transferred in a channel. This theorem is also applied to compression and it limits the maximum compression ratio that can be achieved. Beyond that limit, is not possible to transfer or compress more data.

$\endgroup$
  • $\begingroup$ I like this approach. However, this answer doesn't do anything to explain the principle for relatively small messages. $\endgroup$ – Maarten - reinstate Monica Jun 12 '18 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.