Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
Just take the first 64 bits of SHA-256 output. It's as good as 64 bit hashes get. –  CodesInChaos Mar 10 at 23:11
2  
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. –  CodesInChaos Mar 10 at 23:13
2  
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? –  poncho Mar 11 at 1:02
1  
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? –  fgrieu Mar 11 at 8:03
1  
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. –  user4982 Mar 11 at 18:04

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Ultra-helpful. No, this doesn't cut it. –  Don Doerner Mar 11 at 22:32
    
Thank you very much. I'll develop an alternate technique to solve the problem. –  Don Doerner Mar 11 at 22:42
2  
+1. The birthday bound is a harsh mistress. –  Ilmari Karonen Mar 13 at 16:46
    
@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. –  tylo Mar 24 at 16:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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