2
$\begingroup$

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.

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

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.

|cite|improve this answer
$\endgroup$
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
-1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gilles Dec 30 '16 at 22:48

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.