Hash Function Reversal

Question

I have the following hash function, and I'm trying to change it so that I can find the key from the hash value.

uint Hash(string s) { uint result = 0; for (int i = 0; i < s.Length; i++) { result = ((result << 5) + result) + s[i]; } return result; } 

The code is in C #, but I assume this is understandable.

I know that for one hashed value there can be more than one key, but my intention is not to find all of them, only one satisfying the hash function is enough.

EDIT:

The string that the function accepts is formed only from digits from 0 to 9, and the characters "*" and "#", therefore, the Unhash function must also take this criterion into account.

Any ideas? Thanks.

Answer 1

Brute force should work if uint is 32 bits. Try at least 2 ^ 32 lines, and one of them will most likely have a hash value with the same value. It only takes a few minutes on a modern PC.

You have 12 possible characters, and 12 ^ 9 is about 2 ^ 32, so if you try 9 characters, you will most likely find your target hash. I will do 10 characters to be safe.

(simple recursive implementation in C ++, I don't know C #, which is good)

 #define NUM_VALID_CHARS 12 #define STRING_LENGTH 10 const char valid_chars[NUM_VALID_CHARS] = {'0', ..., '#' ,'*'}; void unhash(uint hash_value, char *string, int nchars) { if (nchars == STRING_LENGTH) { string[STRING_LENGTH] = 0; if (Hash(string) == hash_value) { printf("%s\n", string); } } else { for (int i = 0; i < NUM_VALID_CHARS; i++) { string[nchars] = valid_chars[i]; unhash(hash_value, string, nchars + 1); } } } 

Then name it with

 char string[STRING_LENGTH + 1]; unhash(hash_value, string, 0); 

Answer 2

This should cancel the operation:

 string Unhash(uint hash) { List<char> s = new List<char>(); while (hash != 0) { s.Add((char)(hash % 33)); hash /= 33; } s.Reverse(); return new string(s.ToArray()); } 

This should return a string that gives the same hash as the original string, but it is very unlikely that it would be the same string.

Answer 3

Characters 0-9, *, # have ASCII values ​​48-57,42,35 or binary: 00110000 ... 00111001, 00101010, 00100011

The first 5 bits of these values ​​are different, and the 6th bit is always 1. This means that you can output your last character in a loop using the current hash:

 uint lastChar = hash & 0x1F - ((hash >> 5) - 1) & 0x1F + 0x20; 

(if this does not work, I do not know who wrote it)

Now roll back

 hash = (hash - lastChar) / 33; 

and repeat the loop until the hash is zero. I don't have C #, but I'm 70% sure that this should only work with minor changes.

Answer 4

Hash functions are designed to be difficult or impossible to cancel, hence the name (visualize meat + potatoes, chopped)

Answer 5

I would start writing every step that result = ((result << 5) + result) + s[i]; does on a separate line. This will simplify the solution. Then all you have to do is the opposite of each line (in the opposite order).