# Given a string, is it possible to determine which hashing algorithm has produced it, if any?

Given a string, is it possible to determine which hashing algorithm has produced it, if any?

For example, the MD5 hash of "string" is b45cffe084dd3d20d928bee85e7b0f21.

Is it possible to determine whether the above hash is:

1) Indeed a genuine hash in some hashing algorithm, as opposed to a string of characters that is not a hash produced by one of some set of algorithms

2) a definite hash of a specific hashing algorithm?

Possible methods:

1) For hashes susceptible to rainbow-table attacks, it would be viable to search for the hash in such a rainbow table for various algorithms, to find a match; if a match is found, we know which algorithm produced it.

• A sorting algorithm produced the output [1, 2, 3, 4, 5]. Is it possible to determine which sorting algorithm produced it if any? – quicksort Dec 30 '16 at 18:12
• @quicksort I wonder what made you think of sorting algorithms..? :-D – David Richerby Dec 30 '16 at 18:43
• @DavidRicherby I'm sorry, I couldn't resist :D – quicksort Dec 30 '16 at 18:48

You will first need to define what you mean by a hashing algorithm. For example, my favorite hashing algorithm is simple: check whether the input is "string", and if so, output "b45cffe084dd3d20d928bee85e7b0f21", otherwise output "error".

In the simplest case, you have one algorithm $A$, and string $w$ and you are wondering, is there an input $x$ (and maybe a seed $s$) such that $A(x,s)=w$? You can try brute force, but if you have the source code, is there something more clever that you can do? If not, then your algorithm is a one-way function. Whether one-way functions exist is an open question. We know that if one-way functions exist, then $P\ne NP$, and therefore if $P=NP$, one-way functions do not exist, but that still leaves three possibilities.

No it is not possible to determine that is produced by a hashing algo, or which one that produced it -- at least not from a single sample.

Good hashing algo will produce a uniform set of values across the entire range of possible values -- where modern algo produces values from 128 to 512 bit in width, but if we take it back to a simpler example that may be easier to understand and suppose that you hashing algo only produced values between 1 and 10, then for it to be a good algo it should produce any of the values 1 to 10 with equal likelihood.

If you were just given one value "7" you would not know if it was generated by the hashing algo, or by some other means -- there is simply not sufficient evidence.

Different hashing algo's may however have different weaknesses, so say our simple algo had a flaw that would make it more likely to produce the value 7 than the value 5, and supposed we had a million values that was generated by some hashing algo unknown to us but had the same distribution of fewer 5 and more 7's we could say that it would be likely to be generated by that hashing algo, but not certain.

As for your suggestion of Rainbow tables -- rainbow are easy to foil -- add salt or do multiple iterations of hashing -- something as simple as just sticking the letter 'a' in front of the input of 'string' gives a md5 of b9a15c6d632a44e7eb75d000e1dba40b which according to google does not appear in any public rainbow tables, so with a bit ingenuity of adding random salt and it would be hard to determine that the value is a md5 even with a rainbow table.

Any good hashing algorithm will be able to produce any possible output of the right format so, for example, to test if a string is a valid MD5 hash, it should be enough just to check that it's a string of 32 hex digits.

• While it's thought to be likely that common cryptographic hashes are surjective, they are not known to be so, and it is likely that a surjectivity proof would also provide an effective method to calculate preimages, i.e. a proven-surjective hash is likely not a good cryptographic hash. – Gilles 'SO- stop being evil' Dec 30 '16 at 22:48