Concerns about using a hash to determine if specific input data has already been encrypted

Question

A system is used to securely store account numbers.

When an account number is added to the system it is securely encrypted and stored in a database along with the IV and a reference to the encrypted record is returned (so that the encrypted record can be retrieved at a later date).

If a second request for an identical account number is made, rather than creating a new record, the existing reference must be returned to avoid duplicate entries in the database.

Storing a hash of the account number along with the record would provide a means to determine if a particular account number has already been stored, but my concerns are whether there are any implications for the hash being used to identify the account numbers.

I gather that all secure modern-day cryptographic hashes have pre-image resistance (so the hash can't be "reversed"), but if the account numbers themselves come from a limited set then presumably the account numbers could be determined via the hashes by brute force?

Are the ways to protect against this?

Would increasing the number of hash iterations slow down any brute force attempts to the point where the hashes wouldn't be considered a security issue? When selecting iterations to use other than the general size of the iterations (1000, 10,000, 100,000) are there other things to consider... is there any value in selecting a non round number such as 993 hash iterations rather than 1000?

When using a hash as a lookup value like this individual record level salts aren't usable, but I presume using a system specific salt would still be useful (to minimise the use of pre-built rainbow tables?) Would storing the system salt in a different location to where the hashes are stored (i.e. not in the database) offer any value (or is that just security through obscurity?)

Answer 1

Instead of using a hash function, use a pseudo-random function (PRF). Unlike hash functions, which are publicly computable, PRFs use a secret key. HMAC-SHA256 is a widely supported PRF (although usually it's used as a MAC, which is a bit different). Use a different key for the PRF then you use for encryption.

Another possibility is to use a deterministic encryption scheme, such as SIV. These ensure that the only information leaked (asside from plaintext lengths) is plaintext equality: the same plaintext results in the same ciphertext each time, but close-related plaintexts don't result in similar ciphertexts. Unless you're crunched for space in the database, though, there's no real advantage to this approach for your purposes, and implementations may not be as widely available.

To address some of your other questions:

A salt would prevent the use of pre-built rainbow tables, but, depending on the length of account numbers, this may not be sufficient.

Suppose you use 10,000 rounds of a SHA256. If there are 8 digits of an account number that an attacker cannot guess beforehand, bruteforcing all the account numbers requires 10^8 * 10,000 = 10^12 SHA256 calculations. A modern GPU can do 10^9 SHA256 calculations a second. This would result in all the account numbers in your database being broken in 10^3 seconds, which is under 17 minutes.

You might be able to play with the numbers a bit to make things more reasonable, but my advice would be to go with the PRF. Then you don't have to worry about this sort of thing.

I'm assuming that anyone who could steal the PRF key could also steal the encryption key, and therefore am not worrying about this possibility. But you could certainly combine the PRF with a large number of hash rounds to provide some measure of defense-in-depth. If you opt to go this route, consider using bcrypt rather than, e.g., SHA256. Bcrypt is less easily bruteforced on a GPU. Some experts also recommend scrypt for this purpose, but scrypt is new enough that I would be hesitant to rely upon it.

Edit: There's another related (but distinct) disadvantage to using repeated hashing: An attacker who obtains the hashes can easily answer the question, "Does account #XYZ exist in this database?" Depending on what these account numbers and database are used for, this might be a real concern for your users. A PRF does not allow this attack, provided the key remains secret.