Combining Random Hashes - avoiding collisions and ensuring randomness

Question

I have a series of integers which I want to convert to random integer (64 bit). The idea here is to produce random numbers very quickly. The issues that good quality random numbers are required with a low collision rate to ensure low correlation between entities. A series of integers are input and a number of desired samples are required that are a random as possible.

The hash?

The random hash is taken from Numerical recipes book and is fast as it used just bit shifts and XORs. This should be very fast. The inputs are a 64 bit integer and output is a 64 bit integer. Some of the numbers can work on 32 bit, so this might be an advantage later on in ensuring there is no overflow.

How to combine hashes?

I understand about using XORs in terms of maximizing entropy and ensuring the combination doesn't exceed 64 bits. However the issue is that if I have series of nested loops over integers then with 2 loops I may get the following

A = 0, B = 1 and then I have A= 1, B = 0 and these will be equivalent so I get a collision i.e.

(Hash(A=0) XOR hash(B=1)) = (Hash(A=1) XOR hash(B=0))

One way around this might be to do the following:

Hash(A) + k*Hash(B) where k = [int], say = 5

What worries me here is that if I have to use a 64 bit representation for i and j, then I am likely at some-point to reach over flow as I might get j near the MaxInt and multiplying by k is going to result in exceeding MaxInt. However if I assume that j is 32 bit, if k is low then I am careful about removing a deductable from i, the MaxInt issue can be avoided. Also I shall have to watch that the sum of i and j doesn't exceed the Max int. I can see using pure XOR's would be useful but it is troubling because of the collision rate.

Using another algorithm here with an increased key length (block cipher) maybe the way forward as we can increase the key length with something like Blowfish to handle many 64 bit integers concatenated to form a key. What worries me with Blowfish is slow with regard to handling the key and this needs to be super quick.

Are there any recommendations out there for a better way to handle this problem?

In summary,

Have inputs:

A: 64 bits
B: 32 bits
C: 32 bits
D: 32 bits
E: 32 bits

The output should be an integer/double that is has the fewest repeats/collisions as described above. The output is not being used for anything other than generation of random numbers, but important that those random numbers are not correlated for the input.

The hash currently being tested is:

inline Ullong int64(Ullong u) 
{

  Ullong v = u * 3935559000370003845LL + 2691343689449507681LL;
  v ^= v >> 21; v ^= v << 37; v ^= v >> 4;
  v *= 4768777513237032717LL;
  v ^= v << 20; v ^= v >> 41; v ^= v << 5;
  return v;
}
inline Uint int32(Ullong u)
{ 
  return (Uint)(int64(u) & 0xffffffff); 
}
Returns hash of u as a double-precision floating value between 0. and 1.
{ 
  return 5.42101086242752217E-20 * int64(u); 
}

Answer 1

• I'd treat your input as one 192 bit input instead of thinking about 5 separate inputs.
• If you don't need security, you can always reduce the number of rounds of cryptographic primitives. If you merely need statistically random output, 20% of the usual number of rounds should be fine with many hashes.

A few suggestions:

• SipHash has good performance for short inputs. It's pretty easy to implement as well.

  The default version of SipHash has 2 rounds for each 64 bits of the input and 4 rounds of finalization, called SipHash-2-4. Sacrificing security you could reduce that to SipHash-1-2 or even SipHash-1-1.

  I expect a cost of 200 CPU cycles using SipHash-2-4 on your 192 bit input on a modern 64 bit CPU and 100 cycles with SipHash-1-2.

  A round of SipHash:

  v0 += v1; v1 = ROTL(v1, 13); v1 ^= v0; v0 = ROTL(v0, 32);
  v2 += v3; v3 = ROTL(v3, 16); v3 ^= v2;
  v0 += v3; v3 = ROTL(v3, 21); v3 ^= v0;
  v2 += v1; v1 = ROTL(v1, 17); v1 ^= v2; v2 = ROTL(v2, 32);
  

  SipHash treats the input as a sequence 64 bit words. You can use A, BC, DE as the three inputs. SipHash as specified applies some padding at the end, which increases the effective input size.

  Since you have constant length inputs, you can simply leave out the padding, so the input is only 3 words instead of 4.

• Rijndael-256 truncated to 64 bits. This should have great performance when used with AES-NI, but implementing it yourself will be hard.

• MD5

  While it's not secure against deliberate collisions, accidental collisions are as rare as one can expect. But it will be a bit slower than the alternatives.

• A variant of Skein256

  Skein is fast on 64 bit CPUs. Use the variant based on Threefish256, not the variant that uses Theefish512 and merely truncates since, the smaller block size doubles performance for short messages. Remove the finalization compression, it's only necessary for some security properties you don't need.

  Then you can proceed to reduce the number of rounds to the smallest value that's still random enough for your purposes.

Personally I'd go with round reduced SipHash.