CODEWITHSUNDEEP
encryptioncryptographyhash
alexey
alexey

Reputation: 8480

Short (6 bit) cryptographic keyed hash

I have to implement a simple hashing algorithm.

Input data:

Output data:

Requirements:

Possible solutions:

  1. Keep full mapping as a key. So the key has length 2^16*6 bits. It's too long for my case.
  2. Linear code. Key is a generator matrix. It's length is 16*6. But it's easy to find generator matrix using several known hash values.

Are there any other possibilities?

Upvotes: 3

Views: 1640

Answers (2)

Ilmari Karonen
Ilmari Karonen

Reputation: 50338

Mensi' suggestion to use truncated HMAC is a good one, but if you do happen to be on a highly constrained system and want something faster or simpler, you could take any block cipher, encrypt your 16-bit value (padded to a full block) with it and truncate the result to 6 bits.

Unlike HMAC, which computes a pseudorandom function, a block cipher is a pseudorandom permutation — every input maps to a different output. However, when you throw away all but six bits of the block cipher's output, what remains will look very much like a pseudorandom function. There will be a very tiny bias against repeated outputs, but (assuming that the block cipher's block size is much larger than 6 bits, which it should be) it'll be so small as to be all but undetectable.

A good block cipher choice for very low-end systems might be TEA or its successors XTEA and XXTEA. While there are some known attacks on these ciphers, they all require much more extensive access to the cipher than should be possible in your application.

Upvotes: 0

mensi
mensi

Reputation: 9826

A HMAC seems to be what you want. So a possibility for you could be to use a SHA-based HMAC and just use a substring of the resulting hash. This should be relatively safe, since the bits of a cryptographic hash should be as independent and unpredictable as possible.

Depending on your environment, this could however take too much processing time, so you might have to chose a simpler hashing scheme to construct your HMAC.

Original Answer the discussion in the comments is based on:

Since you can forget cryptographic properties anyway (it is trivial to find collisions via bruteforce attacks on a 5-bit hash) you might as well use something like CRC or Hamming Codes and get error-detection for free

Upvotes: 5

Related Questions