I have to roll database access keys often, but it's important to know which key each system is using in order to avoid unavailability. I want the systems to report that without exposing the key itself, of course.

I'm using randomly-generated 512-bit keys, and from each key I'm planning to make a 32-bit hash. I only need to compare a handful of keys each time, so it's ok to have $1 - \frac{1}{2^{32}}$ of comparison confidence (which gives more than 99.99999%).

If the attacker sees the hash and knows the key size, he/she can filter out keys that produce a different hash. However, he/she will still have $2^{480}$ keys to brute-force access the database.

Does that make sense or is there a better solution? If this will work, which hash function should I use for the 32-bit hash? CRC/Checksum/something else?

  • $\begingroup$ Any reason you don't list truncating a cryptographic hash function like SHA2 down to 32 bits as an option? I ask since you mention collision-resistance and preimage-resistance in your tags and crypotgraphic hash functions provide both. $\endgroup$ May 2 '16 at 18:22
  • $\begingroup$ Thanks, there's no special reason. How truncating works? Just remove the unwanted bits? I added the tags to call attention of hashing experts. $\endgroup$
    – fernacolo
    May 2 '16 at 18:26
  • 1
    $\begingroup$ Yes truncation means take the first 32 bits of output from the hash function (or the last 32 bits, it doesn't really matter as long as you are consistent). In the case of SHA2 the output is 256 bits, in general most cryptographic hash functions output at least 128 bits. $\endgroup$ May 2 '16 at 18:39
  • 1
    $\begingroup$ @puzzlepalace, with 32-bits of output you'd see a collision after $2^{16}$ outputs anyways (very likely) so why bother with a crypto hash? Beyond that the usual issue with pre-image resistance is to find a pre-image and not the pre-image which would require an insance amount of work anyways here (after all you can't get a 512-bit entropy value compressed down to 32-bit anyways). The only advantage of SHA-2+truncate would be extensibility for the point where the OP wants to expand from 32-bit away which is trivial with truncation. $\endgroup$
    – SEJPM
    May 2 '16 at 19:37

In general, you never want to use CRC/weak checksum for any computations on secret material (like keys). CRC is a linear function and by showing CRC of a key, you reveal a lot of equations that hold among the key bits. This is equivalent to showing the same number of bits of the key as the length of the checksum.

The proper way of doing it has been suggested by @puzzlepalace: Take a cryptographic hash function (like SHA-2), compute the hash of the key and take only 32-bits of the digest.

Key fingerprint of 32-bits may be too small: if you have ~2^16 keys, you will get different keys that give the same fingerprint. You need to take this into account when designing your system.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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