Can I obtain the hashing algorithm if I know both the input and the output?

Question

Suppose I have a string "Hello World". And I pass it through an unknown function which gives output as "6Xbhkfo520/78".

So, using several input and output pairs, can I determine the algorithm of the hashing function?

Answer 1

It is weird to assume a hash function is private. This contradicts Kerckhoffs's principle. If you are talking about keyed hash functions, then I think the answer is no in theory. They are typically used to construct message authentication codes like HMAC, of which the keys cannot be derived from several hash inputs/outputs.

Answer 2

You cannot directly determine what function is used. You can't even tell IF a hash function was used. Secure hash functions can be modeled as a random oracle. Input/output pairs of the form $(m, hash(m))$ are indistinguishable from pairs of the form $(m, \text{random-value})$.

---

Slight tangent: This is probably related to one reason why "challenge" questions, "what algorithm is this", and "crack this ciphertext" questions are banned from this website. If you want to prank someone then say to them "I challenge you to crack this cipher from ciphertext only." Then give them a fake ciphertext string chosen randomly. You can easily waste their time by asking them to solve a puzzle with no answer.

Additionally there exists an infinite number of potential (mathematical) functions consistent with one input/output pair. Even if you find one function that is consistent with any number of functions, you cannot be sure that it's the same function because there are infinitely many alternatives.

---

What you can do is come up with a hypothesis like "This hash function is MD5." (Or SHA-1. Or any other known algorithm.) Then test your hypothesis. If $hash(m) \neq \textit{MD5}(m)$ then you reject your hypothesis. Repeat for every candidate function you can think of.

When the given output does not match the computed output, you can conclusively say "The hash algorithm is not vanilla MD5." On the other hand if the two values are equal, then you cannot say for certain that your hypothesis is correct. For a secure hash with a long output you, as a person, may be confident that your hypothesis is correct. These functions wouldn't result with many (or any) false positives because there outputs are too large to allow matches to happen by chance. But as I noted before it cannot allow you to mathematically prove your hypothesis is correct (unless you rule out every other function in the universe of all possible functions) because of the infinite number of alternatives.

---

Second aside: Sebastián Mestre's suggestion to use machine learning is (very) wrong for the same reason. You could train a neural net that produces identical results for any given set of input/ouput pairs, but the operation the neural net does will be a function not necessarily or likely the original function. This is the "over-training" phenomenon. Or "over-fitting" a function. Furthermore neural net training does not work well for this type of thing. There is no gradient for pseudo-random discrete things. And if a hash algorithm could be succinctly represented by a neural net that would imply a very flawed cryptographic algorithm.

---

Back on the main topic: In practice you would need to further complicate the method of "For each hash algorithm test if it fits." There are lots of variations on algorithms that are possible.

As a heuristic for choosing potential hypotheses you can look at the output of the function. If it's 512 bits long then you should look at things like SHA-512, SHA3-512, Skein-512, Blake-512, Blake2b, ... You get the idea. It's probably not going to be MD5 or SHA-1 because they have less than 512 bits of output.

This can be complicated though. If you have 256 bits of output, then maybe you have a SHA-256, SHA3-256, SHA-512 truncated to 256 bits, SHA-512/256 (which is different from both SHA-256 and truncated SHA-512), truncated SHA3-512, two MD5 outputs concatenated together, etc.

So far I have ignored text encoding of hash function output. That is, for the sake of simplicity, I treated the output string as the raw output of some hash function (a binary string) not an ASCII string like "6Xbhkfo520/78".

If you have a 64 byte output and every single byte is an ASCII character 0-9 or A-F, then maybe you should assume you are looking at a hexadecimal encoding of a 32 byte value, not a 64 byte binary string that happened to fit this description by chance.

You should try different encoding methods. Counting the number of unique characters in the output is another good heuristic, this time for guessing encoding methods. Look for other distinguishing characteristics of encoding methods, like separator characters or padding characters. (A string ending in two equal signs is likely a variation of base64. Which one though would be less certain. There are many base64 and base32 "alphabets" to choose from so you'll want to try the most common ones.)

You should notice that this is essentially a brute force method. (Except unlike password cracking or brute forcing a key for a known algorithm you're testing known input/output pairs against many possible hash functions and encoding algorithms.

This is backwards compared to Kerckhoffs's principle. (A cryptosystem should be secure even if everything about the system, except secret keys, is public knowledge.) Attempts to defend yourself using some obfuscation method you have come up with is usually referred to as "security through obscurity". "Security" through obscurity is not good security but it might make someone's work a bit more difficult. This problem, for example.

There are lots of ways one could obfuscate hash outputs or the hash algorithm used. Uncommon text encodings, character substitution, character transposition, double hashing, encrypting input before hashing, encrypting output of the hash function. If you want bad ideas then look at "clever" password hashing solutions people come up with. (Like in the PHP documentation comments section, assuming they haven't cleaned that up.)

If you're trying to make it difficult for outsiders to compute your hash function, then there are better alternatives to using secret algorithms. You can use a public (secure) algorithm with a secret key. HMAC, for example. This has the benefit of being easier to implement securely. And it doesn't require every person who could possibly want to hack you being much much less "clever" than you.

Although HMAC is only one algorithm (which utilizes a hash function of your choice), you can think of every instance of HMAC with a distinct key as a separate hash function, even when every instance uses the same hash algorithm. (HMAC has a quirk in that there are equivalent keys, but it's not a security issue with randomly generated keys.)

Other methods of turning one hash function into a family of hash functions include salting, personalization strings, and non-standard IVs.

Salting usually refers to a value that is not required to be kept secret. Non-standard IVs may make a secure algorithm insecure. Personalization strings are pretty much the same as salts.

Since brute forcing many different hash functions, encodings, and additional input is probably the best method of determining a hash function, then using a secret key with enough entropy will make it impossible to "obtain" the function without hacking the system protecting the key. For this post I assume obtain means you have full knowledge of how to compute identical input/output pairs for any input.

Important: Passwords should be hashed with an algorithm like Argon2 or bcrypt using an unpredictable and globally unique salt. It's possible to hide the salt and output of these functions by encrypting both with a secret key protected by a HSM. This actually provides a greater degree of security than you could get with only a salted password-stretching hash algorithm. It is not security-through-obscurity because it only requires correctly implemented algorithms and protection of key material.