0
$\begingroup$

I read about hash function and I know that there can be some $x$ values which lead to the same $y$ ($x$ is the parameter of the hash function, $y$ is the result).

Is there a way, given a $y$ and a hash function to find some $x$ value which related to this $y$?

For example, if $hash_1(x_1)=y_1$, $hash_1(x_2)=y_1$, then given a $y_1$ and a hash function called $hash_1$, I will get $x_1$ (or $x_2$).

In other words, are there some sort of reversible hash function?

$\endgroup$
  • $\begingroup$ The short answer is "no". If two different $x$'s hash to the same $y$ there's no way to recover $x$. If the hash function were injective then in principle you could unhash, but the calculation might not be practical. $\endgroup$ – Ethan Bolker Apr 7 '17 at 23:52
  • $\begingroup$ If you hash $x$ as $h(x)=x^2$ you can recover $x$ just finding $\sqrt x$. Of course this hash is almost always useless. $\endgroup$ – Marcelo Fornet Apr 7 '17 at 23:54
  • $\begingroup$ Well, you can clearly create hash functions that are invertible on their ranges, but what is the point? $\endgroup$ – copper.hat Apr 7 '17 at 23:54
  • 1
    $\begingroup$ The way I read it, the requirement is only to get some $x$ that hashes to $y$. The hash function does not need to be injective for this to be possible. $\endgroup$ – Robert Israel Apr 7 '17 at 23:54
  • $\begingroup$ I would guess you would need to add more info. to get useful responses. For example, if the domain is finite you can do it by computation, however that may take a long time (for example, if you are hashing fixed size JPEGS or BDDs). $\endgroup$ – copper.hat Apr 7 '17 at 23:58
1
$\begingroup$

If (as is almost always the case in computing applications) the domain of the hash function is a finite set, or at least some finite subdomain is known that will produce all possible $y$ values, it is in principle possible to find an $x$ by a brute-force search. Of course that may not be feasible in practice if the domain is large. Whether more efficient methods exist will depend on the particular hash function.

For cryptographic applications, one wants a hash function that is easy to compute but difficult to reverse: a one-way hash function.

$\endgroup$
  • $\begingroup$ It is for appling in big data structure, so it should be easy to turn from the image to its domain. The domain is finite but big. Is not there any reversible keyed hash function for this reason? $\endgroup$ – Adi Ml Apr 8 '17 at 0:14
  • $\begingroup$ If the codomain of the hash function is smaller then the domain of then it will be irreversible. $\endgroup$ – Q the Platypus Jul 5 '18 at 1:10
  • $\begingroup$ @QthePlatypus That would be true if you wanted to reverse the hash function in the sense of finding $x$ given $hash(x)$. But the goal here is more modest: given $hash(x)=y$, find some $x'$ (not necessarily $x$) such that $hash(x')=y$. $\endgroup$ – Robert Israel Jul 5 '18 at 2:19
0
$\begingroup$

It depends on what is meant by a hash function. Sometimes we want to map a fixed size domain into itself in a way that has long cycles but is invertible. For instance, $p = 2^{256} - 189$ is prime, and its multiplicative inverse mod $2^{256}$ is $q = $

$79645352385455584153778984397510201168915862468430017593277703285866173826411$

Multiplying by $p$ mod 256 is for some purposes an acceptable hash of 256 bit strings; multiplying by $q$ inverts this hash.

$\endgroup$

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.