How many computations does it take to figure out the input if you know the function and you know its output to another known function?

Question

I have no background in cryptography so excuse me if this question is a little basic or poorly defined. I'm trying to build a circuit using microcontrollers that implements a hash function of some arbitrary number that a user inputs. I want to make it such that the person is able to select from a small list of hash functions the circuit is able to accommodate, for example SHA-2, MD5, etc.

What I'm wondering is how "easy" it would be to figure out what someone's input was if they knew exactly what hash algorithms they used and they knew the outputs, where by "easy" I mean how would the number of computations it would take to figure out the input scale up with the bits of the input? Linearly? Exponentially? Is there some general equation or guideline to figure out the maximum number of computations it would take (based on the number of inputs) that doesn't depend on the hash functions themselves, or would it always? I'm assuming that with infinite computations it would be possible, but correct me if I'm wrong.

For the above question I was assuming that you didn't know the number of bits of the input, but if you DID know the number of bits of the input, would that make computing it any "easier" in the same sense?

And lastly, if you also assumed that you knew that the bits were preceded by leading zeros when the number of bits of the input was smaller than the number of bits that the hash function can accommodate, would this change anything?

Please let me know if there are any details I'm missing and I'll try to reformulate. Thanks!

Answer 1

Assume your hash function does not exhibit a pre-image attack, that is, we are talking about a generic hash function here which doesn't have structural weaknesses when it comes to inverting it.

Let $F:\{0,1\}^*\to\{0,1\}^n$ be said hash function with an $n$-bit output. For example $n=128$ for MD5 and $n=256$ for SHA-256. Furthermore let $\mathcal M$ represent the (partial) knowledge you have over the input as a random variable and let $d$ be the output you are given.

Now you need about $$\min\{2^{H(\mathcal M)},2^n\}$$ evaluations of the hash function to find an $m$ such that $F(m)=d$. Note that you can't trivially identify whether the $m$ you have found is the same that was originally used to produce $d$ (after all the only property we demanded of $d$ is satisfied now). The most you can do is to check that $\Pr[\mathcal M=m]\neq 0$, that is you use your pre-acquired knoweldge to verify that the found $m$ is actually possible.

What I didn't cover yet is what $H(\cdot)$ in the above expression means. It denotes information-theoretic entropy. Basically it is the logarithm of the amount of uncertainity of the random variable and thus takes likeliness of the individual possible values into consideration as well.

So finally why is the above expression correct? Well, you expect to find a match of the hash function's output after $2^n$ evaluations because the probability of every single output bit matching the corresponding bit in $d$ is $\frac12$ and multiply this $n$-times because all bits need to match. Now for the other term, if you know a lot about $m$ you can exploit this structure and only have to try all things out you are uncertain about.

Now the two example properties you mentioned can easily be fit into the above framework: You now know that $\mathcal M$'s "output" is at most $m$ bits long and thus $H(\mathcal M)\leq m$. Now if you don't know this, you can still probably make some reasonable estimates for an upper bound and in a practical, full-on-guess attack you would approach from shortest-to-longest anyways probably. Now for the other property, it rules out a lot of different possible inputs, namely $2^l$ where $l$ is the amout of leading zeroes, because you know that the first $l$-bits are going to be $l$, they are fully determined now, so you effectively just divided your entropy by $l$.

Answer 2

What you are describing here is attacking a password. The very definition of a cryptographic hashing function includes resistance to preimages. If you are given hash(x), it should be impossible to recover x. So not a lot of the information you state here will help you recover the preimage.

However, what you are touching on is brute forcing attacks. In that case you would take preimage X and perform hash(X) to determine if hash(X)==ExpectedHash. You do this for every possible combination that X could be until they are in fact equal. Then you do this for each hash.

As for how many computations would be required. That is a function of entropy. For example, the required information:

• how many bits are required [min-max]
• what is the maximum possible combination on each byte
• is there any known space

and yes this problem would rise exponentially. say I have a password that can only consist of 0 or 1. That means I have 2 possible combinations for any position of my password. However adding an additional character to the password means that there are 4 possible combinations now, 00, 01, 10, 11. For each additional character I add adds more combinations in the form of 2^n. For very large bit counts this problem becomes extreme (which is kind of the point really). The end result of computations would be:

• [# of computations per hash function of one preimage and compare]*[2^n]=[# of computations required]

Where n is the length of the password. This problem is even worse if you don't know the length of the password.

Some things you can do:

If you know certain things about the preimage you can reduce the number of calculations required. In your example you mentioned per-appending 0s. Well it might help, but only if it means you always know the length of the preimage. In that case it helps and in no other way (you cant say for sure how many 0's are in the image, and where they are). All you have done is said "there is no less number of bits than this, and no more" reducing the problem to a certain number of bits per preimage. Otherwise you would also have to try each combination from [0] all the way to [111111111...n]. The only thing you could do is say, I know that there are this many bits in the preimage. so only 2^n combinations. Now start from 0 and pre-append 0s from the last bit to the first. This would be the best method for this. But still require at maximum the number of computations listed earlier. Since you don't know if any 0s at all were pre-appended.

So to sum it up, Yes it can help, but in reality only in reducing the problem to one exponent. I don't think you can get lower than that without something really clever. Hope this helps!