# Combining Random Hashes - avoiding collisions and ensuring randomness

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);
}

• 1) It's almost always better to choose a single good hash rather than combining multiple hashes. 2) Use a modern crypto hash. 3) With 64 bit hashes, you only get 32 bits of collision resistance. So in the cryptographic sense, you don't get any practical collision resistance. Even pre-image resistance is rather low at 64 bits. – CodesInChaos Jun 26 '14 at 16:11
• 4) You say the hash should be very fast. Can you give any numbers? 5) All your inputs have exactly 64 bits. Did I understand that correctly? 6) Do you actually need a hash? Perhaps a keyed permutation (i.e. a 64 bit block cipher) is more appropriate? Permutations have no collisions by definition. – CodesInChaos Jun 26 '14 at 16:16
• You should write a bit more about the problem you want to solve. What your inputs are, what the outputs should be. What you want to guarantee etc. Your answer is mostly about the problems you encountered with your approach. I suspect that the best solution throws most of that approach away, replacing it by a single standard crypto function. – CodesInChaos Jun 26 '14 at 16:20
• @CodesInChaos yes, a better function in the first place is prob a better bet, hence the suggestion of Blowfish etc. But what concerns me is the speed of these with so many rounds. – disruptive Jun 26 '14 at 16:34
• @Navonod, which are you more concerned about, speed or security? – mikeazo Jun 26 '14 at 16:43

• 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.

• Thanks for the suggestion. I'm in the process of having a look at the output quality. I'm trying a 64 bit number as the word and the key as a concatenation of 4 32 bit integers. – disruptive Jun 30 '14 at 14:45
• @Navonod SipHash has been designed with a uniformly random key in mind, so you're not using it as intended. But since your requirements are much weaker than what it's designed to offer, that might still be okay for you. – CodesInChaos Jun 30 '14 at 16:24
• Is there any merit to prehashing the key - i.e. maybe with a simple hash before? I.e. the whole concatenated string. I guess I was expecting the key to be shuffled more but as you say it might be assumed not. – disruptive Jul 1 '14 at 13:53