What is a preimage and how do you find a preimage of a hash?


In both mathematics and cryptography, given a function $H$ from set $A$ to set $B$, and an element $b$ in $B$, a preimage of $b$ by $H$ is any $a$ in $A$ such that $H(a)=b$.

In cryptography, a public function $H$ from set $A$ to finite set $B$ is:

  • First-preimage-resistant when for a given random $b$ in $B$, it is hard to exhibit a preimage of $b$, that is, $a$ in $A$ with $H(a)=b$.
  • Second-preimage-resistant when for a given random $a_0$ in $A$, it is hard to exhibit another preimage of $b=H(a_0)$, that is, $a$ in $A$ with $a\ne a_0$ and $H(a)=H(a_0)$.

A preimage can in principle be found by trying various values of $a$ in $A$ (other that $a_0$ for second-preimage), and computing $H(a)$ until it matches $b$ (the given $b$ for first-preimage, or $b=H(a_0)$ computed from the given $a_0$ for second-preimage). Depending on the definition of $H$, there can be better methods.

A common design goal of practical cryptographic hash functions is that the expected effort to find a preimage (of either kind) is not much less than $|B|/2$ times the effort for computing $H(a)$ once, where the notation $|B|$ designates the number of elements in the set $B$. When $B$ is the set of exactly $n$-bit bitstrings $\{0,1\}^n$ (as is common for cryptographic hashes) the quantity $|B|/2$ becomes $2^{n-1}$.


Since $f$ (hash function) is hard to invert, all you can do is try random inputs until you succeed.

If the hash function output is $n$ bits long, and the hash is strong (well approximated by a random function) your probability of success is only about $$\frac{q}{2^n}$$ after $q$ trials given output $y_0$ and checking whether $f(X_t)=y_0$ for random inputs $$X_1,\ldots, X_t,\ldots,X_q.$$

In the worst case you may need $q>2^n$ to succeed with probability one assuming $y_0$ is an actual output of the hash function since other outputs along the way will typically collide. Most likely $q\approx n 2^n$ will be needed which is the expected cover time for a balls and bins process (coupon collector).

  • $\begingroup$ There are many conversion questions between primate problems but I did not find this one, interestingly. $\endgroup$ – kodlu Sep 22 '17 at 3:42
  • $\begingroup$ $\frac{q}{2^n}$ after $q$ trials seems wrong. These are independent events. $\endgroup$ – DurandA Nov 24 '20 at 14:28
  • $\begingroup$ I think the correct probability is $1-(1-\frac{1}{2^n})^q$. $\endgroup$ – DurandA Nov 24 '20 at 14:58

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.