Can a neural network crack hashing algorithms?

Question

I've been reading a bit about neural networks, and their ability to approximate many complex functions.

Wouldn't a neural network be capable of cracking a hashing algorithm like SHA256?

For example, say we want to train our network to crack strings of 8 characters that were hashed. We could go through all the permutations and train the network since we know the inputs and expected outputs. Would the network technically be able to crack a relatively good amount of SHA256 hashes that map back to 8-character strings? Has this been done previously?

Answer 1

No.

Neural networks are pattern matchers. They're very good pattern matchers, but pattern matchers just the same. No more advanced than the biological brains they are intended to mimic. More thorough, more tireless, but not more sophisticated.

The patterns have to be there to be found. There has to be a bias in the data to tease out. But cryptographic hashes are explicitly and extremely carefully designed to eliminate any bias in the output. No one bit is more likely than any other, no one output is more likely to correlate to any given input. If such a correlation were found, the hash would be considered "broken" and a new algorithm would take its place.

Flaws in hash functions have been found before, but never with the aid of a neural network. Instead it's been with the careful application of certain mathematical principles.

Answer 2

From a different angle:
You could reduce it to the open problem "does there exist an efficient algorithm for integer factorization". If such an algorithm exists, a NN could discover it via guided proof search, and that could be used to undermine all of security.

Answer 3

UPDATE given your comment:

I know that it would be computationally unfeasible. I just wanted to know if it would be theoretically possible (it seems not according to tylerl)

Yes, given infinite time and infinite energy, a neural net could crack SHA256. BUT (and I think this is the point @tylerl is making) because hash functions have no discernible patterns, a neural net would not be able to do any better than the naive brute-force of building a lookup table by computing the hash of every possible string. Such a lookup table would have more entries (~ 2²⁵⁶) than there are atoms on the planet earth (~2¹⁶⁶) - so at least with our current level of technology it's "impossible" to hold such a table in memory or store it on any disk. Similarly, for your neural net to perform noticeably better than a dice-roll, the number of neurons you would need would probably also exceed the number of atoms on the planet.

So yes, it is computationally infeasible, but still theoretically possible. In fact it's true of cryptography in general that it's always possible to brute-force something in theory, but we say "good enough" when we can prove that doing so will require more time than the lifetime of the universe and more energy than contained in the sun.

---

I think the counter-argument is in response to:

We could through all the permutations and train the network since we know the inputs and expected outputs.

1) Is this fundamentally different than a lookup table?

2) SHA256 has an output space of 2²⁵⁶, and an input space that's essentially infinite. For reference, the time since the big bang is estimated to be 5 billion years, which is about 1.577 x 10²⁷ nanoseconds, which is about 2⁹⁰ ns. So assuming each training iteration takes 1 ns, you would need 2¹⁶⁶ ages of the universe to train your neural net.

The point here is that SHA256 has 2²⁵⁶ possible outputs, and 2²⁵⁶ is a really really really big number.

Answer 4

"Can a Neural Network become the 'inverse function' of a hash function?" Maybe. There is no mathematical proof that any given hash function, be it SHA or any other, lacks patterns between Domain and Image. As other answerers have pointed out, hash functions are explicitly designed such that there are no known preserved qualities. If there is some sort of pattern, then theoretically a neural network could find it, but I'm sure it's been tried before and SHA still exists, so we can assume that they were unsuccessful. I might mention that you would have to prove this 'lack of pattern' for each and every hash function individually.

I put 'inverse function' in quotation marks because hash functions need to be surjective (however surjectivity usually isn't formally proven) and as such can have two numbers being mapped to the same number, hence there is no true inverse. However the inverse function need not be a true function, in the sense that it can return a Set of numbers or a function that describes a set of numbers. The brute-force inverse function of a hash function would simply return the Domain (e.g. the natural numbers), and a more sophisticated inverse function would return a real subset of the Domain.

This would actually be interesting to train a neural net on: The NN returns a function as output. The function has some density within the Image one could approximate, the lower the density, the higher the reward. Now to train the NN you would input f(x) and check if x <- { g(c) | c <- |N} while g is the function the NN returns as output.

Answer 5

Neural network or any other machine learning algorithms are not magic, even if it might look like this. At the end these methods are just a bunch of equations (i.e. math) to map input to output and the learning is adjusting the parameters for this equations so that the result reflects the training data as best as possible. This way it tries to learn the inherent structure of the data in the hope that this structure is the same for most of the other possible inputs too. Or in summary: its just math.

If such an inherent structure would exist which allows for comparably easy mapping from the hashed value to the original value or even if this would only result in greatly reducing the search space to make brute force possible then this hash would not be considered a cryptographic strong hash. And since you don't need to use a neural network or similar to investigate such issues I'm pretty sure that this is done and that neural networks do not impose any new dangers.

Answer 6

No, Neural networks fundamentally use gradient decent optimization. Neural networks are an interesting family of functions and in practice we manage to optimize over them rather well despite not being a convex problem.

For any such optimization technique to work we need some minimal amount of smoothness, we need a notion of almost correct. We don't have this with cryptographic hash functions. We expect a single bit flip to flip half of the outputs, In most places we have small changes leading to small changes, not so in cryptography. This is why neural networks can not learn to invert cryptographic primitives.