patternMinor
Given a string, is it possible to determine which hashing algorithm has produced it, if any?
Viewed 0 times
anygivenproducedalgorithmpossiblehasdeterminewhichstringhashing
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#68070, answer score: 3
Revisions (0)
No revisions yet.