1
$\begingroup$

A hash function takes an input, performs a set of complex operations and then produces an output. For my purposes the output from the function will always be the same for any given input.

I remember reading long, long ago that neural networks can in theory (assuming infinitely large network) reproduce any algorithm - therefore it stands to reason that a theoretical neural network could replicate a hash function. That all being said, I did a search for such a neural network (just with Google) and I couldn't find anything quite as pure as I've described (possibly because hashing inputs has seen some popularity).

If we limit our scope to looking at cryptographic hashes only and assume we can train using input/output pairs is it reasonable to train a network for this?

$\endgroup$
6
  • $\begingroup$ There are lots of hashing functions, created for different purposes. Do you have a purpose in mind for your neural network hashing algorithm, or a specific type of hash that you would like to replicate? Is there any end goal or reason why you would want a neural network to emulate a hash? $\endgroup$ Jul 12 '21 at 21:34
  • $\begingroup$ @NeilSlater I don't have e a specific hash in mind, but something like sha3 is what I'm looking at right now. My end goal is really just seeing if it's possible/how good it could get/how complex a hash it could handle. $\endgroup$ Jul 12 '21 at 21:51
  • $\begingroup$ sha3 is a cryptographic hash, along with md5, sha1, sha2, bcrypt, blake and others. When you say "hash" are you specifically thinking of those kinds of hashing algorithm, and how they are used? BTW, you have tagged the question hashing-trick but that does not seem related to what you are asking. $\endgroup$ Jul 13 '21 at 7:03
  • $\begingroup$ I am specifically thinking of cryptographic hashes, but more because they're the only hashes I have used in the past. I wasn't sure what hashing-trick was and it seemed like it could be related (I'm on the andriod app and I couldn't work out how to check the tags description) $\endgroup$ Jul 13 '21 at 8:06
  • 1
    $\begingroup$ OK, given your current knoweldge, are you willing to focus the question primarily on cryptographic hashes and trying to learn the functions directly from input/output pairs? This would help someone construct an answer, without needing to worry about all possible hash types etc $\endgroup$ Jul 13 '21 at 8:16
1
$\begingroup$

I remember reading long, long ago that neural networks can in theory (assuming infinitely large network) reproduce any algorithm - therefore it stands to reason that a theoretical neural network could replicate a hash function.

This is the universal approximation theorem and it does apply to learning hash functions.

However, the theorem says nothing about generalisation, and that is a major problem when learning any pseudo-random functions.

Any hash function which has the following properties:

  • Output is hard or impossible to reverse back to any original input,

  • output is highly sensitive to input, such that a single bit changing in the input will (pseudo-randomly) change all bits in the output.

will be impossible to approximate and generalise using statistical techniques. Cryptographic hashing algorithms have these as a design goal, and attempt to meet the ideal of a random oracle.

If you could train a neural network to generalise better than 50% accuracy (bit for bit, and measured over a suitably large test data set to establish significance) on unseen inputs, that would be an indication that the hash was broken for cryptographic use. The chances are that you would not be able to achieve this even for known broken hashes such as MD5.

If we limit our scope to looking at cryptographic hashes only and assume we can train using input/output pairs is it reasonable to train a network for this?

You are very unlikely to create any useful reusable model doing this. It may still be a worthwhile learning exercise for practicing machine learning, with the main benefit being it is very easy to put together training and test datasets. Your expectation of not being able to find anything could be used as a test of statistical knowledge, and for bug hunting. Your first suspicion if you get positive results would be to check your code and assumptions. However, there are other learning scenarios where you have a higher expectation of making a useful model, and those are IMO going to be more rewarding.

$\endgroup$
4
  • $\begingroup$ Thanks for the answer. I've begun training on an algorithm that's a modified version of sha256 (it has more steps after you use sha256). I've converted the output from hex to int (so 64 ints) and started training. Interestingly at present I've getting a mean absolute error below 4 (it's 3.95 but still training and still falling). I assumed it would hit 4 and stop (since 4 would be the average absolute error if the number can be 0 - 15 inclusive and the NN goes to the mean value). I'll check back after a few more hours of training if anything changes. Any ideas why I'm getting such a low loss? $\endgroup$ Jul 13 '21 at 14:21
  • $\begingroup$ As a note I'm training on 100,000 values $\endgroup$ Jul 13 '21 at 14:22
  • 2
    $\begingroup$ If this is training loss than there is no surprise, the network can memorise the input-output pairs. Calculate the loss value on a test set. $\endgroup$ Jul 13 '21 at 14:27
  • 1
    $\begingroup$ @user6916458 As per my answer if you get unexpected values, the first thing you should check is your code for bugs and incorrect assumptions. Molnár may be on to something - are you looking at training loss? That can go to zero (provided NN has enough weights to learn for all the inputs), and the NN will have learned to map your inputs to the given outputs. It will "hash" the data from the training set accurately. However, give it some unseen inputs and you should find that it has not learned anything about the hash function in general. $\endgroup$ Jul 13 '21 at 15:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.