Can a 32-bit hash be made into a 64-bit hash by calling it twice with different seed?

Question

If I have a hash function that generates a 32 bit result with a good distribution (say murmur3):

var h32 = hash32(str, seed);  // returns a 32bit hex string (8 chars): '0123abcd'

it will still generate collisions with a probability of 50% when I have 77163 samples.

Can I create a 64 bit hash with equally good distribution by simply concatenating the result strings of two calls with different seed?

For example

h64 = hash32(str, seed1) + hash32(str, seed2);  // '0123abcd8d4f614a'

or by modifying the input slightly on the second call

h64 = hash32(str) + hash32(str + 'x');  // '0123abcd8d4f614a'

Or put it another way:

If hash32('foo') == hash32('bar'), can I assume that hash32('foo'+'x') == hash32('bar'+'x') is completely independent / unlikely?

UPDATE: thinking about it, this will probably not work if the hash algorithm works incrementally character-by-character, so this will not help either:

h64 = hash32(str) + hash32(str + str);

So I rather ask for a way to 'build a 64-bit hash if only a 32-bit hash function is available.'

UPDATE 2
I am aware that no one would use 32-bit in a crypto context. My question is about doubling the length, when I only have a method that returns a given length. And doing it in a way that improves collision behavior as one would expect from a native 64-bit method (or at least similar).
So this is a general question (replace '32' with any number if you like).
It has a real background though: I use JavaScript, which not easily supports 64-bit math and I already have a performant, small hash32() implementation using murmur 3.
The question would probably be better suited on StackOverflow, but the accepted answer hits the spot.

Answer 1

In terms of managing the collision probability

h64 = hash32(str) + hash32(str ^ hash32(str)); 

where + denotes concatenation and ^ denotes bitwise XOR would not be bad, since if hash32 is a good hash, its input and output should behave as if they are statistically independent.

There is no implication that the hash is strong for information security purposes, with this bitsize it is extremely weak.

Answer 2

What you're describing is essentially what Microsoft did with its LANMAN hash. They produced a long hash by concatenating two short hashes.

Once you know that this is the case, the two short hashes can be attacked separately.

The basic problem is that instead of increasing the difficulty of brute forcing by powers of the length of the long hash, you have merely doubled (at most) the difficulty of the short hash.

Actually it's less than doubled as fully enumerating hash1 will also produce hash2 if they both use the same algorithm.

Answer 3

You can use a function like shake-128 that can output a variable length hash. In this case, you can input a 32 bit hash as shake key, and output a 64 bit hash from the shake algorithm. This is a much better approach then hashing twice. You can use following code:

shake_key=hash32;                 //hash32 is the 32 bytes value that you want to to convert in 64 bit hash
shake128(0,shake_key,&shake_ctx); //shake key scheduling: take 32 bytes key
shake128(64,h64,&shake_ctx);      //shake hash calculation with output h64 of length 64 bytes

Answer 4

Based on the accepted answer I now use this code:

function hash64(str) {
    var h1 = hashMurmur32(str);  // returns 32 bit (as 8 byte hex string)
    return h1 + hashMurmur32(h1 + str);  // 64 bit (as 16 byte hex string)
}

NOTE: At least in my scenario it makes a huge difference if h1 is fed-back as suffix or prefix: h1 + hash32(str + h1) yields much worse results!

Even then, we should not assume that the collision probability is equivalent to a real 64-bit hash.
And of course do not use it in a crypto context.

Here's my test code and some results:

function testHash(n) {
  var d = {},
    c = [],
    t = Date.now();

  for (var i = 1; i <= n; i++) {
    var s = "aaa" + i + "bbbb" + (i + 1) + "ccc",
      h = MAKE_HASH(s);

    if (d[h]) {
      c.push(d[h] + "=" + s + " (" + h + ")");
    } else {
      d[h] = s;
    }
  }
  alert( "N=" + n + " took " + (Date.now() - t) + "ms, " + c.length + " collisions:\n" + JSON.stringify(c) );
}
testHash(1000000);

Results:

• Sample size: 1 million, HASH_FUNC: 32 bit FNV-1a => collisions: 236
• Sample size: 1 million, HASH_FUNC: 32 bit murmur3 => collisions: 100
• Sample size: 1 million, HASH_FUNC: 32 bit FNV-1a + hash(s + h1) => collisions: 236 (!)
• Sample size: 1 million, HASH_FUNC: 32 bit FNV-1a + hash(h1 + s) => collisions: 0
• Sample size: 1 million, HASH_FUNC: 32 bit murmur3 + hash(s + h1) => collisions: 82

• Sample size: 1 million, HASH_FUNC: 32 bit murmur3 + hash(h1 + s) => collisions: 0

• Sample size: 10 million, HASH_FUNC: 32 bit FNV-1a + hash(h1 + s) => collisions: 150

• Sample size: 10 million, HASH_FUNC: 32 bit murmur3 + hash(h1 + s) => collisions: 0
• Sample size: 15 million, HASH_FUNC: 32 bit murmur3 + hash(h1 + s) => collisions: 0