Hash Un-hashing
The basic goal of this challenge is to exploit the high probability of collision in the Java Hash function to create a list of plausible inputs that created an outputted hash. The program that can print the most results in one hour wins.
For example, hashing golf
produces the number 3178594
. Other 'words' you could hash to get the same number would be: hQNG
, hQMf
, hPlf
Details
The basic Java hash function is defined as:
function hash(text){
h = 0;
for(i : text) {
h = 31*h + toCharCode(i);
}
return h;
}
You can use an altered or more efficient variant of the hash function (such as using bitwise to replace multiplication) if it produces the same results.
If your language of choice does not use signed ints or have integer overflow, you must implement a wrap function in the hash to emulate integer overflow so that 2147483648 would overflow to -2147483648.
You can choose not to worry about inputs that wrap around multiple times, such as those with 6-7 characters or more. If you choose to include those, you have a better chance of winning.
Additional Requirements
Your code should have at least one input: the hash itself. An optional second input is the maximum number of letters to guess. For example,
guessHash(53134)
might produce a list of all input combinations up to the absolute maximum amount (see the next requirement), andguessHash(53134, 4)
will display all input combinations that contain 1-4 letters.As there are an infinite amount of results, the most letters that can be in a single result will be set at 256. If your program can manage to output all 256 letter results in a reasonable amount of time (see next requirement), you automatically win.
Your program should not run for more than an hour on any
non-specialized
computer you use.Non-specialized
means it can't run on a server system using 256 different cores or on a super-computer, it must be something that any regular consumer would/could buy. The shorter time period is for practicality, so that you don't have to use all your processing power for too long.All the results in your final list of inputs must produce the same hash as the inputted hash.
You are to implement your own search, brute-force, or any algorithm to produce the final list.
Using a native search method or search method from another library is not allowed (example: binary search library). Using
String.search(char)
orArray.find(value)
is okay if it is not a primary feature of your search algorithm (such as to spot duplicate results or find if a letter exists in given string).The final list of input values should use all readable ASCII characters (32 to 126).
Example
I went ahead and created a very inefficient version of this challenge to produce an example list! Each result I gave is separated by spaces, although you can print each result on a new line or any other readable method of organization.
i30( i3/G i2NG hQNG hQMf hPlf golf
You do not have to print results to a file, just record how many results you get.
Judging
The number to un-hash is: 69066349
I will pick the best answer based on which-ever code produces the most results. If you remember above where I said wrapping was optional, it'd be a good idea to include multiple wrappings if you want the most results in your final list.
If you have any questions or additional comments, feel free to ask.
Good Luck!
2**-64
of matching the given hash (to give a rough estimate), there are155**256/2**64
preimages. \$\endgroup\$