# Can rainbow tables find the preimage of a hash? [closed]

Given a hash value, how are you supposed to find its preimage? What steps can I take to solve find the preimage of a hash such as this 2d202cb6a781edf6ac01d14e1dd6367497db90ba9e8ad721fd17239228a213f9 (SHA256)

The only way to find the preimage of a hash value is to guess. There is no better way than trying all possible inputs by brute force until you find a match. This property is a design goal for cryptographic hash functions (preimage resistance).

A rainbow table doesn't help finding preimages, as such. Rather, it's a tool that helps you reuse somebody else's brute force work. If a rainbow table contains 1 trillion entries, then you can use it to find the preimage of any of those 1 trillion hash values in a short time. But the maker of this table had to make the 1 trillion hash computations. The reason rainbow tables are (occasionally) useful is that once the table has been built (a high one-time cost), you can make as many queries as you want (very low cost per query). It is useful if you have reason to believe that the preimage is among the 1 trillion in the table — if the preimage isn't one of these then all the rainbow table will tell you is that it definitely isn't one of these. See Crunge's answer on Security Stack Exchange for a very nice explanation of how rainbow tables work.

In practice looking up a hash value on Google is a low-effort way to find some simple preimages. When that doesn't work, it tends to suggests that tying to invert the hash won't be the easiest method of solving your problem.

Looking for the hash value in your question turns up a partial copy of a homework assignment which mentions “You should use the tools provided in the file, but are not limited to them.” Said file was not included in that copy of the assignment, but it should be in yours. What you need to do to solve the assignment is, presumably, to figure out how the provided tools work.

Rainbow tables are not magic and will not help you find a preimage to an arbitrary SHA256 hashcode. Unless you can significantly limit the space the original plain text was drawn from. For instance if the original text is a password from of limited entropy rainbow tables may be of assistance.

A simplistic intro: Rainbow tables are a form of time-memory-tradeoff https://en.wikipedia.org/wiki/Time/memory/data_tradeoff_attack Someone spends an effort on the order of brute forcing a single hash, but rather than make it a one time effort they store the results of their work. If they had enough memory to store all their hash invocations you could sort them by hash output and have a quick inverse lookup to invert any hash covered by the table.

However typically our compute capacity greatly out-ways our storage capacity(or transfer capacity). So we want to summarize the information. Time memory tradeoffs allow us to store less than a full lookup and still find pre-images for a large portion of the hash outputs. The more memory you have to store the faster (time) you can mount an attack against a given hash value.

More accurately we have a time-memory-data tradeoff, because a table doesn't provides full coverage of all possible hash values we can also adjust the likelyhood a given hash will be invertable with our setup, or conversely the number of attempts we have (how much data of hash outputs we have to try to invert at least one). The data trade off can be very significant when attacking stream ciphers.

If we want to invert one of $D$ hash values taken from a space of size $N$, we have enough storage to keep $M$ input&output pairs then for $D >> 1$ we get the following tradeoff. let $t=N/(M*D)$ the time to invert a single hash value with probability $1/D$ using a single rainbow table is $t^2/2$ .

If all you want is to use ready made rainbow tables take a look at http://project-rainbowcrack.com/ or https://crackstation.net/