How to unhash sha256? Alternatives to brute force?

Question

I know it's almost impossible to do, SHA256 is a one-way function that can't be easily reversed, just like there are operations that have no reverse, take: $f(x) = x+5$ , it's easy to see that if you want to revert that you just take the output and subtract 5, you'll get the original input, the reverse would then be $f(y) = y-5$ For $f(x) = 7, there's nothing you can do about it, no matter what X is, you always get 7, you can easily input any X, get the output, and get 7, but to gt the original input, there are infinite possibilities.

Similarly, sha256 can't be unhashed because of this, mod operator has no inverse, for example, yet, there are ways around that, what I mean is, 22%7 is 1, 7 ? 1 = 22, no operator for that, but I can take a set of numbers that when moded with 7, x%7 = 1, this is still infinite, but this infinite is smaller than all N numbers.

So, would it be possible to try to unhash a sha256 making a list of "candidates" or finding some rules about the seed that leads to that hash?

When I was thinking about this, I found this really interesting research on Github

https://github.com/trevphil/preimage-attacks

I'm a newcomer in this world, but now I feel very interested in ways to unhash a sha256 other than brute-forcing which is not unhashing, is just hashing everything until a match. What other ways are known that are not brute-forcing? Is really that the only approach there is?

Answer 1

The short answer, the GitHub project has a long way to see that it is almost impossible to do. 4-round attacking has nothing compared to 64 rounds of SHA-256. And the note of the author tells this too;

As a disclaimer: I do not claim that any of these methods break the security of the full 64-round SHA-256 hash function. It's probably still infeasible. Prove me wrong :)

The best know pre-image attacks with the attack types for SHA-256 in academics are

Year	Round	Cost	Attak Type	The Work
2009	43	$2^{254.9}$	Meet-in-the-middle	Preimages for step-reduced SHA-2
2010	42	$2^{248.4}$	Meet-in-the-middle	Advanced Meet-in-the-Middle Preimage Attacks:First Results on Full Tiger, and Improved Results on MD4 and SHA-2
2011	45	$2^{255.5}$	Biclique	Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 family

As you can see, the works still require lots of classical computing power that is beyond all of us and not full round. A real attack will require a complexity around at most $2^{112}$ to be achieved some governmental agencies ( It is still high if you consider that all of the collective power of the Bitcoin miners reached $2^{93}$ hashes in a year). We don't see such an attack in the near future.

Grover's Search (Quantum attacks) can be used to find pre-images on hash functions, well it has quadratic speed up if we omit the cost of setup and running of the possible future machines, it will still require $2^{128}$ time to attack. Still not reachable.

If there is no breakthrough in attacking the Merkle-Damgard based hash functions, SHA-256 is one of them, they will be secure for a long time.

And, remember, the NIST has come from a long experience with the SHA series. SHA-0 (broken), SHA-1 has broken with collision resistance not pre-images^*, and the SHA-2 series is going to stand for a long time due to the internal design and the output size.

Actually, the first successful attack to be executed on a Cryptographic hash function should be the collision attack. In the collision attack, the attackers are free to choose to collide any two messages. This provides more flexibility to the attackers. The generic cost of collision attack on SHA-256 is already $2^{128}$ thanks to the birthday paradox (attack). As time has shown, MD5 and SHA-1 are no more collision-resistant but they still have their pre-image resistances.

---

_{^* No major cryptographic hash function has failed on the pre-images resistance, even the MD5}

Answer 2

The problem is that as you stack operations on top of each other, the characterization of the possible input values becomes more and more complicated. Eventually it becomes so complicated that you may as well just use brute force.

Cryptographic primitives are designed to frustrate this sort of analysis by alternating operations that aren't mathematically well behaved in combination, like carryful modular addition/multiplication and carryless xor/rotate, and by using a large number of rounds.

This kind of analysis is feasible for some non-cryptographic hashes. For example, there's a simple characterization of all documents that have a certain CRC. It's also feasible for reduced-round versions of cryptographic hashes, as seen on that page you linked.