Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?)

share|improve this question
    
Encryption schemes that have indistinguishable encryptions under chosen-plaintext attacks must be non-deterministic, i.e. two identical plaintexts encrypted twice will (with overwhelming probability) have different ciphertexts. So, from a ciphertext level, there won't be duplicate entries. Is it problematic that there are duplicate plaintexts? (Basically, is the duplicate restriction a technical constraint, or is there some business logic that determines it?) –  Reid Aug 5 '13 at 16:03
    
@Reid Yes it's a business requirement to prevent duplicate entries for the same account number. The existing encryption mechanism used is indeed non-deterministic, which is why a different approach is being sort. A hash seems the logical approach for this, but securing the hashing process to make it repeatable by the application, but not by a malicious attacker via brute force is the challenge. –  Sival Dot Aug 5 '13 at 23:11
add comment

1 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.

share|improve this answer
    
thanks for the HMAC-SHA256 suggestion. The critical difference if I understand you correctly for the PRF is the use of the secret key which makes it harder for the hashes to be 'publicly computed'. –  Sival Dot Aug 5 '13 at 23:19
    
Not just harder, computationally impossible unless the key is exposed or the algorithm is broken (given a large enough authentication tag - the output of the MAC). –  owlstead Aug 5 '13 at 23:29
    
However, make sure you don't accidentally allow outsiders to query the PRF as an oracle. –  Stephen Touset Feb 4 at 22:18
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.