I have a long list of a specific data structure, each entry contains an encrypted string (uses AES-GCM).

I want to be able to detect duplicates efficiently, without iterating over the entire list. Performing a lookup on any value in the data structure is very quick, but since I'm using AES-GCM, encrypting the same string twice, produces different output (due to an IV).

Is there anything I can add to the data structure to make this feasible?

  • One way might be to use a HMAC. Store the HMAC of the plaintext string in the data structure, and before inserting a new string, check if an element already exists with the same HMAC – Gregorio Di Stefano Apr 1 '17 at 13:02
  • 1
    Depending on how your data is used, you might introduce a security vulnerability if you indicate duplicate strings with a hash or HMAC. If each line is meant to be read by/for different users, indicating a duplicate might give away information to a user who knows plaintext for his encrypted string. Can you go in more detail on how the data structure is used? – Marko Vodopija Apr 3 '17 at 13:25
  • There is only one user for the system. The data structure is just an basic structure describing a file on a file system. The filename is encrypted with aes-gcm. The way I got around this is by storing FilenameHMAC, which is the HMAC of the plaintext filename (using a secret key) – Gregorio Di Stefano Apr 4 '17 at 16:01

Your Answer

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

Browse other questions tagged or ask your own question.