I have a situation in which I need to combine a 32-bit datum, G, and a 64-bit datum, I, to produce a 64-bit datum. No two tuples with the same I value will have the same G value, and vice versa. Collision resistance must be very high (data corruption will result if not).

Technically, I don't need encryption, but most decently collision-resistant hash functions happen to come from the field. Some questions:

I have considered using a cryptographic hash such as SHA-256 and either slicing (i.e., subset of bits) or folding (XOR'ing subsets of bits).

  • Question 1: is this a reasonable approach (i.e., can anyone recommend something simpler with comparable collision resistance)?

  • Question 2: slice or fold? Folding might help with issues of non-uniform distribution in the subsets, but does it weaken the result? I think not, but I am not certain…

Thank you!

To the responders… Thank You!

@ChaosInCodes: right – collisions are very problematic, maybe fatal. This is why I am also soliciting any other ideas about how to do this (i.e., without the use of cryptographic hashes). The I datum, in particular is sparse (being a composition of a bunch of other, smaller data, including a little slice of G). I am continuing to work on whether I can recompose (G,I) pairs as a 64-bit datum without using hashes… Pointers to information on the probability of collisions (given uniformly distributed, random inputs - which I don't really have), that would be helpful.

@poncho: I mean unlikely.

@RichieFrame: thanks, I'll check into these. As mentioned, I really don't need a cryptographic checksum, just a very good hashing technique.

@fgrieu: OK, the problem I am trying to solve is to represent a filesystem's inode's generation and inode number as a unique 64-bit datum. The values of I are not unique (by which I mean that at any point in time, an inode points to unique data, but the file system reuses inodes over time); the values of G are also not unique (by which I mean that there are many inodes deployed during a given generation). The pair (G,I) is guaranteed to be unique, but its too big!

I expect ~billion pairs, and this approach is only workable if the probability of collision is sufficiently low that I will likely retire before the first one occurs. ;-}

The tone of these responses lead me to believe that perhaps a cryptographic hash is insufficient to the need, i.e., may have too high a probability of collision given the input data. I have some background in data de-duplication, so my head went there, but perhaps it isn't the right approach.

  • 2
    $\begingroup$ But you can't really get "very high" collision resistance with a 64 bit hash. For example if you have 4 billion entries, collisions become likely, but you can't neglect them with only a few million entries. $\endgroup$ Commented Mar 10, 2014 at 23:13
  • 2
    $\begingroup$ What do you mean by 'collision resistant'? Do you mean that it is computationally difficult for find two (I, G), (I', G') pairs that hash to the same value? Or, does it mean that it is unlikely for two elements in your data set to hash to the same value? $\endgroup$
    – poncho
    Commented Mar 11, 2014 at 1:02
  • 1
    $\begingroup$ Sounds like this might be a case for a non-cryptographic, hash table-type hash, e.g. SipHash (which is actually more cryptographically-inclined than most). They're a bazillion times faster, mostly resist accidental collisions (but not malicious attacks), and it's not like you can get real security out of 64 bits anyway. $\endgroup$ Commented Mar 11, 2014 at 3:15
  • 1
    $\begingroup$ Do you need that the result be computable without a secret? What property must the result have beyond the stated low odds of collision? How many tuples will there be? Is each G unique? Each I? Is it possible to exhibit some less-than-64-bit sub-field of G || I (or some function of that with a small destination set) that is unique? $\endgroup$
    – fgrieu
    Commented Mar 11, 2014 at 8:03
  • 1
    $\begingroup$ With expectation that billions of pairs need to be supported, 64 bit hash appears risky (it is completely possible that collision predicted by birthday paradox happens), thus I would recommend that no matter what hash is used, the system is prepared for hash conflicts. The system could e.g. generate new datum G or I and recalculate hash, if conflict happens. $\endgroup$
    – user4982
    Commented Mar 11, 2014 at 18:04

1 Answer 1


If all that's known about (G,I) is stated in the question, using a hash of the concatenation of G and I, truncated to 64 bits, is a reasonable option (and I see no better one). However the risk that there is at least one collision grows fast with the number $n$ of (G,I). On the (reasonable) assumption that this hash behaves as a random function, this probability of (at least) a collision is $$p=1-(2^{64})!/(2^{64}-n)!/2^{64\cdot n}\approx1-e^{-n\cdot(n-1)/2^{65}}\approx n\cdot(n-1)/2^{65}$$ The approximation on the right is good when $n$ is less than about $2^{30}\approx10^9$. For $n=10^9$, we get $p\approx2.7\%$. Is that acceptable? You decide.

Late addition: an attacker able to influence (G,I) could do so in a way such as to cause collisions. Against this, instead of a hash, we could use a Message Authentication Code with a secret key; problem becomes, how can a file system hide the key from attackers and still achieve media interoperability?

  • 1
    $\begingroup$ Ultra-helpful. No, this doesn't cut it. $\endgroup$ Commented Mar 11, 2014 at 22:32
  • $\begingroup$ Thank you very much. I'll develop an alternate technique to solve the problem. $\endgroup$ Commented Mar 11, 2014 at 22:42
  • 1
    $\begingroup$ @Ilmari awesome comment. But concerning the question: the birthday problem will hit in this scenario with any kind of hash function, not just cryptographic ones. The best approach is probably to use some kind of hash table with chaining. $\endgroup$
    – tylo
    Commented Mar 24, 2014 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.