3

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.

7
  • We're obviously not talking about cryptographic hashes here, how is this security-related? May 9, 2019 at 21:19
  • I am not an expert, but would think that 'good distribution' is a synonym for 'cryptografic' here? Also: a cryptographic 32-bit hash suffers from the same problem of high collision probability. Which forum would you suggest instead?
    – mar10
    May 9, 2019 at 21:59
  • 1
    This looks like a general programming question, suitable for good ole' Stack Overflow. I'd also remark that analyzing this, prima facie, would seem to require (a) knowledge about the design of the candidate hash functions, and (b) assumptions about the likely inputs to it (e.g., random inputs from some probability distribution). May 10, 2019 at 0:49
  • @mar10 A nominally-cryptographic hash function with a 32-bit digest would never have been accepted as secure even decades ago; that's simply far too small a digest to be useful for much of anything (security-wise) since the invention of the transistor. Also, no, the characteristics of a cryptographic hash function do require what I think you mean by "good distribution", but that is definitely not sufficient. A PRNG using Mersenne Twister and seeded with the input will have a very nice output distribution, but wouldn't be at all secure.
    – CBHacking
    May 10, 2019 at 1:09
  • @mar10 "good distribution" is one thing that cryptographic hashes must have, but cryptographic hashes must deal with many other concerns to prevent an attacker from intentionally crafting data and/or hashes which break your algorithm. Good distribution is indeed more up Stack Overflow's alley.
    – Cort Ammon
    May 10, 2019 at 2:06

4 Answers 4

4

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.

4
  • If hash32 was a good hash, it wouldn't have a 32-bit digest. Making any assumptions about the quality of the hash, given the little we know about it, seems entirely unwarranted.
    – CBHacking
    May 10, 2019 at 1:04
  • I see your point but I use good as "uniformly distributed" in the space of 32 bit strings, not with respect to brute force complexity, as suggested by OP. There is no implication that the hash is strong for information security purposes.
    – kodlu
    May 10, 2019 at 1:45
  • @kodlu since JS does not support XOR on strings: I guess that h64 = hash32(str) + hash32(str + hash32(str)); would work as well?
    – mar10
    May 10, 2019 at 7:13
  • 1
    @mar10 Yes. As long as the hash is good, it doesn't matter if it's hashing a ^ b or a || b.
    – forest
    May 10, 2019 at 7:55
4

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.

1

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
1

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
1
  • Have you tested 32 bit murmur3 (hi-bits) + 32 bit FNV-1a (low-bits)? I believe it will perform better regarding the number of collisions Sep 15, 2021 at 0:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .