Reversing a string hash function

user_4207100 0
Viewed 898

I have the following function that hashes a string:

public static uint hashString(string myString)
{
     uint hash = 0;

     foreach (char c in myString)
     {
         hash *= 0x1F;
         hash += c;
     }

     return hash;
}

So if I want to hash hello it will produce 99162322.

Is it possible to write a reverse function that takes in a number and spits out the string (given that the string result is unknown)?

reverse hash c#
2 Answers

Since you don't use cryptographic hash, your implementation is easy to reverse (i.e. return some string which has the given hash value)

Code:

public static uint hashString(string myString) {
  //DONE: validate public methods' parameters
  if (null == myString)
    return 0;

  uint hash = 0;

  //DONE: hash function must never throw exceptions
  unchecked {
    foreach (char c in myString) {
      hash *= 0x1F;
      hash += c;
    }
  }

  return hash;
}

private static string HashReverse(uint value) {
  StringBuilder sb = new StringBuilder();

  for (; value > 0; value /= 31) 
    sb.Append((char)(value % 31));

  return string.Concat(sb.ToString().Reverse());
}

Demo: (given a hash we produce a string and compute hash from it to check)

uint[] tests = new uint[] {
  99162322,
  123,
  456
};

// Since the string can contain control characters, let's provide its Dump
string Dump(string value) => string.Join(" ", value.Select(c =>((int) c).ToString("x4")));

string report = string.Join(Environment.NewLine, tests
  .Select(test => new { 
    test,
    reversed = HashReverse(test)
  })
  .Select(item => $"{item.test,9} :: {Dump(item.reversed),-30} :: {hashString(item.reversed),9}"));

Console.WriteLine(report);

Outcome:

 99162322 :: 0003 000e 000b 0012 0012 0012  ::  99162322
      123 :: 0003 001e                      ::       123
      456 :: 000e 0016                      ::       456

Please, note, that many a string produce the same hash value (say, "hello" and mine "\u0003\u000e\u000b\u0012\u0012\u0012")

user_23194070

No.

One of the fundamental points of hashing is that it's irreversible.

There are many string that will produce the has 99162322, so while it might be possible to find all of them (given a maximum string length), but there would be no way to determine which one was 'correct'.

user_26675280
Related