Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

I'm looking for a way to make a 16bit ID out of approx 100 bits of data. The solution should be easy to implement, or should already be implemented in c++, should be quick to evaluate, and most importantly the values of the ID should be uniformly distributed, which is to say that one value should not have a higher chance to be taken than another.

share|improve this question

closed as off topic by Rook, Ninefingers, Rory Alsop Jun 19 '12 at 19:09

Questions on Information Security Stack Exchange are expected to relate to Information security within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

    
possible duplicate of efficient 16 bit checksum –  Rook Jun 19 '12 at 8:18
    
No it's not. I asked the two questions, they're different. In here, I want a ID, not a checksum. And the data length is not the same, in one case it's a hundred bits, in another it's up to tens of thousands. –  bob Jun 19 '12 at 8:25
1  
Hi bob - the way this, and your associated question, are written don't seem very on-topic here, where we aim to look for the most appropriate security solution/process etc for a security professional. Implementation of a piece of code should probably be in SO. Can you clarify the question - we can then see if it should be migrated in order to get answers useful for you. –  Rory Alsop Jun 19 '12 at 10:27

1 Answer 1

up vote 3 down vote accepted

As mentioned in the question Rook linked, 16bits is very very weak, reducing 100bits to 16 leads to ~6 possible collisions per hash.

Are you sure you need a hash for that ? 16bits is enough to be stored in an integer and could simply be incremented if you just need a way to identify an object (limited to 65536).

If nevertheless you want to use an hash function, you could try to use something very simple such as Pearson hashing that will produce a 8bit hash.

h := 0
for each c in C loop
  index := h xor c
  h := T[index]
end loop
return h

I quote Wikipedia, the advantages of this function are :

  • It is extremely simple.
  • It executes quickly on resource-limited processors.
  • There is no simple class of inputs for which collisions (identical outputs) are especially likely.
  • Given a small, privileged set of inputs (e.g., reserved words for a compiler), the permutation table can be adjusted so that those inputs yield distinct hash values, producing what is called a perfect hash function.

The adaptation to 16bits shouldn't be too hard. For example, this page gives an example of adaptation but I think the author forget to change the size of the table to 65535, the code would be :

static unsigned short T[] = {
    // The values 0..65535 shuffled into random order.
};

static inline unsigned hashOf(unsigned h,const char* s) {
    for (int c = *s++; c; c = *s++) {
        h = T[h ^ (65535 & c)];
    }
    return h;
}
share|improve this answer
    
Yes I'm sure I need that, and incrementing an int is not enough because I need two hashes of the same value, produced at different times, to produce the same result. Thanks for your answer. Where can I find or how to generate the table used in the algorithm ? –  bob Jun 19 '12 at 11:26
    
Here ( github.com/dpree/pearson-hashing/blob/… ) you have an example of ruby code with a permutation table that also implement de 16bits hashing. The generation of perfect lookup table seems to be a common problem, you should find other examples on internet. Maybe also useful info : xlinux.nist.gov/dads/HTML/pearsonshash.html –  Martin Trigaux Jun 19 '12 at 13:23

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