I need a 64-bit cryptographic hash for 96 bits of data

Question

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.

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?