Reversing a hash function

Question

I have the following hash function, and I'm trying to get my way to reverse it, so that I can find the key from a hashed 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 it is clear.

I am aware that for one hashed value, there can be more than one key, but my intent is not to find them all, just one that satisfies the hash function suffices.

EDIT :

The string that the function accepts is formed only from digits 0 to 9 and the chars '*' and '#' hence the Unhash function must respect this criteria too.

Any ideas? Thank you.

Answer 1

This should reverse the operations:

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 to be the exact same string.

Answer 2

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

First 5 bits of those values are different, and 6th bit is always 1. This means that you can deduce your last character in a loop by taking current hash:

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

(if this doesn't work, I don't know who wrote it)

Now roll back hash,

hash = (hash - lastChar) / 33;

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

Answer 3

Brute force should work if uint is 32 bits. Try at least 2^32 strings and one of them is likely to hash to the same value. Should only take a few minutes on a modern pc.

You have 12 possible characters, and 12^9 is about 2^32, so if you try 9 character strings you're likely to find your target hash. I'll do 10 character strings just to be safe.

(simple recursive implementation in C++, don't know C# that well)

#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 call it with:

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

Answer 4

Hash functions are designed to be difficult or impossible to reverse, hence the name (visualize meat + potatoes being ground up)

Answer 5

I would start out by writing each step that result = ((result << 5) + result) + s[i]; does on a separate line. This will make solving a lot easier. Then all you have to do is the opposite of each line (in the opposite order too).