31

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?

forest
  • 64,616
  • 20
  • 206
  • 257
Saturn
  • 563
  • 1
  • 5
  • 10
  • 1
    You'd need to specify the kind of neural network. There are many kinds. Right now, there is no NN design known which is capable of cracking a modern cryptographic hash algorithm faster than brute force. It is possible that, in the future, a NN will be capable of breaking a hash algorithm, but we are _very_ far away from that. Barring major breakthroughs in mathematics that fundamentally change the cryptographic landscape, it would require machine learning on par with human learning in capability. – forest Jan 09 '19 at 07:14

6 Answers6

40

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.

tylerl
  • 82,225
  • 25
  • 148
  • 226
  • 2
    "If such a correlation were possible, the hash would be considered "broken" and a new algorithm would take its place." This is not quite true. If such a correlation were *known*, the hash would be considered broken. It's conceivable that a correlation exits, but we haven't found it yet. Just because a neural network hasn't found an unknown pattern in a hash yet, doen't mean one couldn't find a pattern in the future. Although, due to the way neural networks are trained, it still seems unlikely. – Vaelus Feb 03 '19 at 05:38
  • @Vaelus I'm using "possible" to mean "a thing that someone can do" rather than the more expansive "a thing which could in theory happen". But sure, you could say "known" or "found" or whatever instead of "possible", but I think it's clear already from the context. I don't think the average reader is confused by the phrasing. – tylerl Feb 04 '19 at 05:36
  • If we're talking about anything being possible with enough resources and enough time, is there any data that suggests attacking the hashing algo itself might yield better results than brute forcing a specific hash of a high entropy input? – David Houde Jun 29 '19 at 13:25
16

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.

micimize
  • 261
  • 2
  • 2
11

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 (~ 2256) than there are atoms on the planet earth (~2166) - 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 2256, 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 1027 nanoseconds, which is about 290 ns. So assuming each training iteration takes 1 ns, you would need 2166 ages of the universe to train your neural net.

The point here is that SHA256 has 2256 possible outputs, and 2256 is a really really really big number.

Mike Ounsworth
  • 57,707
  • 21
  • 150
  • 207
  • 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). – Saturn Aug 29 '16 at 18:13
  • The time from the Big Bang is about 13.5 Gy, but yeah your conclusion doesn't change! – Ziofil Jul 22 '17 at 22:49
  • _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._ It depends on the kind of neural net. I'm pretty sure some dude named Coppersmith owns one with only 86 billion neurons and it seems to be perfectly able to break a few cryptosystems. Of course, we don't (yet) know how to design an _artificial_ NN to provide the same benefits that our own biological one gives us, but the fact that 86 billion neurons was sufficient at least gives us an upper bound for an artificial NN. – forest Jul 03 '19 at 06:53
5

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

Mark I.O.
  • 51
  • 1
  • 2
  • Surjective functions don't necessarily map more than one element of the domain to the the same element in the codomain. Consider f(x) = x. What you might want to say is that the codomain of hash functions usually has less elements than the domain, so some elements of the domain nessesarily map onto the same element of the codomain. This is called the pigeonhole principle. – Vaelus Feb 03 '19 at 05:32
4

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.

Steffen Ullrich
  • 184,332
  • 29
  • 363
  • 424
3

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 learn to invert cryptographic primitives.

Meir Maor
  • 1,652
  • 1
  • 9
  • 12