How can I make a good hash function without unsigned integers?

624 views Asked by At

I'm looking for a simple hash function that doesn't rely on integer overflow, and doesn't rely on unsigned integers.

The problem is that I have to create the hash function in blueprint from Unreal Engine (only has signed 32 bit integer, with undefined overflow behavior) and in PHP5, with a version that uses 64 bit signed integers.

So when I use the 'common' simple hash functions, they don't give the same result on both platforms because they all rely on bit-overflowing behavior of unsigned integers.

The only thing that is really important is that is has good 'randomness'. Does anyone know something simple that would accomplish this?

It's meant for a very basic signing symstem for sending messages to a server. Doesn't need to be top security... it's for storing high scores of a simple game on a server. The idea is that I would generate several hash-integers from the message (using different 'start numbers') and append them to make a hash-signature ). I just need to make sure that if people sniff the network messages send to the server that they cannot easily send faked messages. They would need to provide the correct hash-signature with their message, which they shouldn't be able to do unless they know the hash function being used. Ofcourse if they reverse engineer the game they can still 'hack' it, but I wouldn't know how to counter that... I have no access to existing hash functions in the unreal engine blueprint system.

1

There are 1 answers

0
Jeremy Friesner On BEST ANSWER

The first thing I would try would be to simulate the behavior of unsigned integers using signed integers, by explicitly applying the modulo operator whenever the accumulated hash-value gets large enough that it might risk overflowing.

Example code in C (apologies for the poor hash function, but the same technique should be applicable to any hash function, at least in principle):

#include <stdio.h>
#include <string.h>

int hashFunction(const char * buf, int numBytes)
{
   const int multiplier      = 33;
   const int maxAllowedValue = 2147483648-256;  // assuming 32-bit ints here
   const int maxPreMultValue = maxAllowedValue/multiplier;

   int hash = 536870912;  // arbitrary starting number
   for (int i=0; i<numBytes; i++)
   {
      hash = hash % maxPreMultValue;    // make sure hash cannot overflow in the next operation!
      hash = (hash*multiplier)+buf[i];
   }
   return hash;
}

int main(int argc, char ** argv)
{
   while(1)
   {
      printf("Enter a string to hash:\n");
      char buf[1024]; fgets(buf, sizeof(buf), stdin);
      printf("Hash code for that string is:  %i\n", hashFunction(buf, strlen(buf)));
   }
}