# Rotatable hash-based duplicate check

I want to check duplicates of secret information which is also already encrypted in our database(using ECC algorithm, one of the std curves). plaintexts can be phone numbers, zip codes, etc. Since it's not possible to query encrypted information without doing a full table scan or building on index on long ciphertext, I am thinking of doing something like hmac(key, plaintext). However, since this is susceptible to a rainbow table attack, I am considering if it's better to perform hmac(salt || key, plaintext).

Ofcourse, since this is for "duplicate" checking, I cannot randomly generate a salt, since each secret has to hash into the same hash value. So the idea is to generate, say, 128 salts(that I can rotate regularly) and pick salt using salt = saltlist[crc32(plaintext) % 128], this gives some rainbow table protection + the ability to find duplicates, which still allowing every key and salt to be rotated. Since we have a finite set of salts, we can store it securely in a key store.

Questions:

1. hmac(salt || key, plaintext) or hmac(key, salt || plaintext)?

2. Does having 128 salts(or any constant value) even provide any additional protection. (if the number of values goes into millions)?

3. Does it even make sense to have an extra secret key, or just hmac(oneof128salts, plaintext) provide the same amount of protection?

I am not sure if this is over-engineered?

• 'However, since this is susceptible to a rainbow table attack'; are you assuming that attacker knows the key? If not, a rainbow table is impossible. – poncho Aug 8 '17 at 3:20
• I am assuming the key leaks. – jetru Aug 8 '17 at 3:37
• Can you (a) describe your schema and intended goal more precisely (what is secret? what are the plaintexts you're storing? what are the ciphertexts you're storing, i.e. how are the plaintexts encrypted? what duplicates are you trying to detect?), and (b) precisely articulate the capabilities of the adversary? For instance, does the adversary know key? Does the adversary provide a complete set of plaintexts or ciphertexts up front? Does the adversary adaptively provide new data after observing how the system reacted to past data? – Squeamish Ossifrage Aug 8 '17 at 3:40
• Squeamish: Answered a few of your questions – jetru Aug 8 '17 at 4:26
• Ah! That link is exactly the type of feature I want. I just realized that I was planning to store the hash key in about the same way as the encryption keys, which would make the whole thing pointless. But assuming encryption/hash keys were stored separately in key stores, would my scheme be additionally secure in the event of a key leak? – jetru Aug 8 '17 at 5:57