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?