Short (6 bit) cryptographic hash

I need to implement a simple hashing algorithm.

Input data:

  • Value (16-bit integer).
  • Key (any length).

Output:

  • 6-bit hash (number 0-63).

Requirements:

  • It should be nearly impossible to predict the hash value if you only have the input value and not the key . More specifically: if I know the hash (x) for x <M, it is difficult to predict the hash (M) without knowing the key.

Possible solutions:

  • Store the complete match as a key. So the key is 2 ^ 16 * 6 bits long. This is too long for my case.
  • Linear code. The key is the generator matrix. Its length is 16 * 6. But it is easy to find the generator matrix using several known hash values.

Are there other possibilities?

+3


source to share


2 answers


A HMAC seems to be what you want. So you can use SHA based HMAC and just use the substring of the resulting hash. This should be relatively secure as the bit of the cryptographic hash should be as independent and unpredictable as possible.

Depending on your environment, this can lead to too long processing time, so you may need a simplified hashing scheme to create your HMAC.



Original Answer that discussion in comments is based on:

Since you can forget the cryptographic properties anyway (it's trivial to find a collision with brute 5-bit hash attacks), you could use something like CRC or Hamming codes and get error detection for free

+5


source


Mensi's suggestion to use a truncated HMAC is good, but if you really are on a highly restricted system and want something faster or simpler, you can take any block cipher , encrypt your 16-bit value (padded with a full block) and truncate the result up to 6 bits.

Unlike HMAC, which computes a pseudo-random function, a block cipher is a pseudo-random permutation — each input is mapped to a different output. However, when you throw away everything but the six bits of the output block, the rest will look a lot like a pseudo-random function. There will be very little deviation from repeated outputs, but (assuming the block cipher block size is much larger than the 6 bits it should be) it will be so small as to be all but undetectable.



A good choice of block ciphers for very low-end systems might be TEA or its successors XTEA and XXTEA . Despite some known attacks against these ciphers, they all require much broader access to the cipher than is possible in your application.

+1


source







All Articles