How is one way hashing possible?

Question

I was wondering, how is one way hashing possible? how can you encode a string in only one direction and not the other? If you reverse the algorithm, can't you decode something like md5? Before, to me, the only way that is possible is to have it generate a random answer instead of using an algorithm. But it hashes the same way every time. Please explain this to me.

Answer 1

If you "reverse" the algorithm, you cannot get the original string back, because there are more possible strings than possible hash codes.

Think of an algorithm that has a result 64-bit integers. There are 2^64 = (2^8)^8 = 256^8 possible such numbers.

But that means, that if there are more then 256^8 possible strings, then there must be two strings that hash to the same value (this is called the pigeonhole principle). Since there are more strings at length 9 (256^9 such strings), the fact that you can get a hash value, does not guarantee you can "go back".

Answer 2

For one thing the MD5 digest is (usually) much shorter than the message, so many messages could have generated the same digest. On the other hand any tiny change to the message will produce a completely different digest. So it is quick to say if a digest corresponds to and given message, but there is no reverse algorithm that turns a digest into plausible messages.

Answer 3

In the case of hashing, as others have pointed out, the irreversibility comes simply from the fact that billions and billions of inputs all hash to the same output, so it can't be reversed even in principle.

But your question seems to imply that you want to know how it is possible to have a deterministic yet irreversible transformation process even in the 1-to-1 case, which is indeed possible. Standard block encryption, for example. A plaintext is transformed from one set of bits into an equally-sized different set of bits (cyphertext). This is totally reversible, but doing both the encryption and decryption requires extra information--a "key" value that is shared by the sender and recipient, but no one else. Thus, the transform is irreversible only because the key is secret--if the attacker gets the key, he gets the message too.

Public key encryption is another whole ball of wax. In this case the "trapdoor" comes from the fact that certain operations, while reversible in principle, are much harder to do in one direction than another. For example, if you have two very large prime numbers, you can multiply them in milliseconds; but if you are given only the product, it will take centuries to discover the prime factors. So if you know both factors, you can calculate two separate "keys" based on them in such a way that one is the inverse of the other. If you only give one key to the sender, he can't calculate the other without knowing the factors, but he can encrypt a message with the key you give him that only you can decrypt. That makes it safer--you could give him the key by simply publishing it on your web page, and as long as you keep your inverse private key secret to yourself, no one can decrypt the message.

Answer 4

It's not that reversal is impossible, it's just impractical.

Hashing removes information from the input: there are infinitely many strings but only a finite number of hashes. Many hashes correspond to an infinite number of strings, so a 1 to 1 reversal is generally impossible. But this doesn't mean you can't produce a set of matching inputs.

If you try to reverse a hashing algorithm like md5 you'll soon find that each step of the algorithm more than one intermediate value corresponds to the output produced by that step, or that it's impossible to produce the output so you took a wrong turn at some point and have to backtrack. Checking each combination will take a very long time.