Is there any reversible hash function?
The hash function like SHA and MD5 are not reversible. I would like to know if there exist some reversible hash functions?
Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.Sign up to join this community
The definition of a cryptographic hash function includes resistance to preimages: given h(x), it should be infeasible to recover x. A hash function being "reversible" is the exact opposite of that property. Therefore, you can have no more a "reversible hash function" than you can have a fish allergic to water.
Possibly you might want a hash function which, for most people, is a cryptographic hash function with all its property, but which also includes some sort of trapdoor which allow reversing it if you know some specific secret. This sort of things might exist but requires mathematics, like asymmetric cryptography. I am not aware of such a construction right now, but one might possibly jury-rig something based on a RSA modulus, or maybe an elliptic curve with coordinates taken modulo a RSA modulus (I don't have a precise design in mind, but I have the intuition that it can be done that way).
Even a non-cryptographic hash can usually not be reversed (that is irrespective of other special properties of cryptographic hashes, such as collision/preimage resistance). The reason why it usually isn't possible is that you simply do not have enough information.
A hash function (generally) turns
N bits of input into
M bits of output, where
M is a small constant and most of the time
N > M is true. Of course
N does not need to be larger than
M, it is perfectly possible to generate e.g. a SHA hash from a single byte, but usually the hashed message is longer (often much longer) than the hash value.
That means no more and no less than that in order to reverse the hash and restore the original message, you would have to use divination magic to fill in the missing information. There are 2N-M solutions, and every single of them is as correct as every other.
So, if you hash, for example, a 36-byte string with SHA and try to reverse this, there are 2128 solutions, all of which are equally correct.
If the input is known to have certain well-known properties (such as starting with a well-known sequence, like
From:, or a particularly low entropy), you may be able to rule out most solutions and eventually find a plausible plaintext, maybe even the correct one -- but this is nowhere near trivial, and you can never prove that you have the correct one, unless you already knew it before or you have another way of verification.
Some hash algorithms, like CRCs (as I noted above) are reversible. See this paper for an approach to do this. (CRCs are fast to compute and ideal to protect data from corruption where there is no security requirement).
The design of cryptographically secure hashes aims to ensure that there is no such shortcut and that finding a hash match requires a full search of the keyspace.
You might look at Knuth's Multiplicative Hash, which generates a reversible, random-esque mapping between integers within the hash table's bounds.
For example, Optimus implements Knuth's algorithm in PHP for the sake of obfuscating sequential IDs. However, do not use this algorithm for security purposes.
You can read in detail in his book, Art of Computer Programming, Vol. 3 especially from page 513.
ELI5: What is a hash?
Imagine you have trouble putting things on your cupboard, so you create a system that defines what drawer you will put everything depending on the barcode. You have 7 drawers, so you scan the barcode on your phone and it tells you where you put it, 1 to 7.
Imagine now you get your 30-item grocery list, after storing everything, and what to know what is on drawer 3, without opening the drawer. What you do? You run over every item on your list, put on your program, and write down all items that it tells is on drawer 3. Easy.
Now imagine your list have something between, lets say, 1030 to 109000 items, and your cupboard have 2160 items. Without opening the drawers, how can you know what it on each drawer? You do a bruteforce attack: testing time and time again every single code until you got one that fits the drawer 3. That's what people say is reversing a hash, even if a hash cannot ever be reversed. You can only execute it again until you get the same result.
A hash function, by definition, cannot ever be reversed. If you can, it's not a hash. It is encoding or encryption.