# How do you find the preimage of a hash?

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).

• There are many conversion questions between primate problems but I did not find this one, interestingly. – kodlu Sep 22 '17 at 3:42