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?
-
22If it's reversible it isn't a hash. – user10211 Jul 13 '14 at 16:46
-
5Reversible hash is referred to as encryption. This might be more suited for crypto SE – Eric Lagergren Jul 13 '14 at 16:46
-
1The context here, "security.stackexchange" is criptography... But, suppose that is not: the term "hash function" is not exclusive of cryptography, it is general, and "crytographic hash function" is only a special subclass of hash function... So this question seems more generic tham the answers and comments posted here. "reversible function" is an existential concept... "reversible hash function" is only a supposition about inverse function existence (as @EricLagergren commented). – Peter Krauss Dec 28 '18 at 17:09
-
The main answer here, about generic hash function, is the less voted, see @Rich's answer. – Peter Krauss Dec 28 '18 at 17:15
-
Read up on the difference between pseudorandom functions (PRFs) and pseudorandom permutations (PRPs). – forest Apr 5 '19 at 5:24
|
Show 1 more comments
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).
-
2I know OP already accepted the answer, but I interpreted the question as though OP was looking for a non-cryptographic hash function. – Tyler Crompton Apr 6 '16 at 5:56
-
1The context here, "security.stackexchange" is criptography... But, suppose that is not: the term "hash function" is not exclusive of cryptography, it is general, and "crytographic hash function" is only a special subclass of hash function. – Peter Krauss Dec 28 '18 at 17:13
-
not exactly a hash, as it would be of variable size, but simply run length encoding (or otherwise compressing the data eg zlib) and then xoring that against a known secret psuedo random value would in theory give a reversible hash. but it might not end up being much smaller than the original data – unsynchronized Jul 7 '20 at 0:31
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.
-
2This should be the accepted answer. Hashing loses information, as the hash always has the same number of bits of information - whereas your input may be of any length. If it doesn't lose information, then by definition it is not hashing. – perfectionist Sep 22 '15 at 10:38
-
It depends on your use case. Sure, if you have N > M, then there will be many N that hash to M. Say you use a trivial hash, such as a simple checksum of all the bytes in N (or slightly more elaborately, a CRC. For a password check, you can quickly find an N that hashes to M - it might not be the password the user entered, but it'll still log them in. For a signature, similarly. Given a known N, you can craft another one that also hashes to M, but has a significant value changed. – Rich Apr 11 '17 at 5:02
-
@Rich: That is correct, however a preimage attack and reversing the hash are not the same things. A preimage attack finds some plaintext, but not the original one (except by win-the-lottery random chance). The question is not about password safety or preimage attacks, but about reversing the hash i.e. restoring the original information, and this is simply not possible (unless N <= M). If it were possible, you could write a compression program that compresses a file of any size down to 4 bytes (well, that is possible, only the decompression part is... uh, a bit tricky). – Damon Apr 18 '17 at 14:15
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.
-
While reversible hash functions are largely outside the Information Security context (hence the main answers), they do exist: see stackoverflow.com/questions/4273466/reversible-hash-function – Real Oct 28 '19 at 0:21
Perhaps you're looking for something like PKI, where a string can be encrypted with a public key at one end, and unecrypted with a private key at the other. Not a hash obviously, but a way to encrypt/decrypt a string to pass a secret around.
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.
