How to properly hash a key? big vs small digest

Question

We have to roll (decommission) database access keys often, but it's important to know which key each system is using in order to avoid removing a key in use thus creating unavailability. We want each system to report which key it's using without exposing the key itself, of course.

We are using randomly-generated keys with 512 bits of size, and we plan to hash those keys and make hashes available in a less secure media.

Here comes the dilemma: Should we use a large or a small digest?

The minimum digest size would be 32 bits. We only need to compare a handful of keys each time, so it's ok to have 1-(1/(2^32)) of confidence (which gives more than 99.99999%). Also an eventual collision just delays decommissioning of the colliding keys a little, so it's harmless.

Of course if the attacker sees the hash, he/she can filter out all keys that doesn't produce the same hash, reducing the search space to 2^(512-32), or 2^480, which we consider secure enough.

However some colleagues suggested that a small digest is susceptible to rainbow tables and other attacks, so we should use a full digest of SHA-256 or SHA-512. That sounds strange to me, because if our key itself is 512 bit, then a SHA-512 hash would generate no collision and the attacker would only have to find the key that produces the same hash. All this processing can be done offline, with no access to the database to test the keys. So it looks more dangerous than using a 32 bit digest.

How can we settle this?

Answer 1

In your specific use case, this assertion is faulty:

... suggested that a small digest is susceptible to rainbow tables and other attacks ...

A rainbow table is only a lookup table of pre-computed digest values. Think of your use of a hash like the index at the end of a book, telling you what page number to read to find the real context containing that word. Like a book, the same page number can index many different words - we call these collisions. With a hash algorithm the page size isn't limited like a book page, so an infinite number of collisions are possible. In that case, knowing the page number doesn't tell you which of the infinite possible collisions is actually your key, so it reveals little to the attacker.

Consider the absurd case where you collapse your digest length down to only two bits; with only four possible values, you'll see that knowing the digest value of 0, 1, 2, or 3 doesn't tell you what the key is. That's why a rainbow table won't help the attacker.

The reason rainbow tables are useful to attackers is that some systems only store digest values in place of passwords. (Microsoft's old LANMAN system infamously did this by storing the hashes of 7 character passwords.) In those systems, knowing any password that generates the desired hash would allow the attacker to re-create the hash value and gain entry. But in your case, knowing the digest value does not reveal which of the collisions is the real key; simply knowing the digest value does not provide the attacker with access.

Knowing the digest value provides the attacker with the ability to reduce the number of keys he tries to guess with, but with 2^512 to choose from, the reduction of 2^32 possibilities doesn't reduce his search space to a feasible guessing range, which as a practical matter would probably be less than 2^80. You actually thwart the attacker more by providing a shorter digest length, as it reduces his ability to limit his search space.

You should choose a digest length that will provide you with acceptably high confidence that you won't mistake one legitimate key digest for another. That's all you have to worry about.

Answer 2

In practice it literally doesn't matter.

If your key size is 512-bit (I'm not sure what cipher you're using, as none that I'm aware of use 512-bit keys, but whatever) then you've got two scenarios:

• In a small digest you've got so many collisions that discovering the original key by looking for matching values will give you a silly number of results. Not to mention trying to execute any remotely computationally complex algorithm 2⁵¹² times, or even 2²⁵⁶ times, is practically impossible.
• In a large digest you've got less collisions (a SHA-512 hash of all values in the 512-bit space will, in all likelihood, produce a number of collisions - it's just really hard to prove) but a much slower hash function. Again, with an input space of 2⁵¹² or 2²⁵⁶ it's practically impossible to brute-force.

There's a lot of incorrect thinking on both sides of your argument, though:

• Brute-forcing a single 256-bit value on a conventional computer would require more energy than we can observe in the known universe due to Landauer's principle. More context on this can be found in a post on Bruce Schneier's blog. A 512-bit value is even more ridiculous - it just won't happen, even if you've got an efficient implementation of Grover's algorithm on an incredibly advanced quantum computer.
• Rainbow tables aren't useful on these kinds of attack. The idea of a rainbow table is to enumerate all possible input values ahead of time for a known hash function, and store the plaintexts and hashes in a chain. This makes it very easy to perform lookups against a hash and get the original value. However, this is only feasible for sensibly sized input spaces, e.g. passwords. With a 512-bit input space your number of states is so large that storing even an 8-bit hash for each input value would require 2⁵¹² bytes (i.e. 1.190853×10¹³⁹ petabytes) of storage. Even if you could somehow compute all those hashes (Landauer's principle again) you'd need to store them somewhere. Even if you could store an entire byte, somehow, on each photon in the known universe, you'd have nowhere near enough - only about 10⁵⁰th in fact.

All in all, just pick a strong cryptographic hash like SHA-256 and don't worry about it.