Search on hashed data

Question

We have a request to encrypt customer personal data (e-mail, address etc.) We use MySQL which does not have any TDE like MS SQL or Oracle. So along with encrypting data we need to preserve functionality for querying this data directly (not LIKE). So something like select * from person where email='[email protected]'.

The idea here is to use hashing and to make sure encryption is not made redundant by poor hashing function. So if we use bcrypt which has random salt built-in it should be fine. The problem is that with random salt we can't construct the same hash again to be able to run sql queries. If I use bcrypt('[email protected]') and it will return different hash value I can't run select * from person where hash_email=bcrypt('[email protected]'). I can get the same hash value only if I use the same salt (and work factor). But having application-wide salt does not seem to be a great solution. So what can be done about this?

If having one salt value per application is not smart could it be a kind of improvement if we generate, say, 1000 random salt values and store them in the database? If we need to hash email we can do the following:

1. get some fast numeric hashing function and calculate, say, m=num_hash(email) mod 1000
2. go to salt table take salt where id=m
3. hash email with this salt email_hash=bcrypt(salt,email) and store in the database

For searching we can apply the same routine, obtain email_hash and run query. I guess num_hash(email) mod 1000 does not tell a great deal about the e-mail itself. Having 1000 random salts is better than having just one.

Any suggestions would be welcome

Answer 1

Unfortunately, the protection provided by using a different salt for each e-mail is designed to prevent exactly the same kind of queries that you need. So, if you need efficient queries, you should either use the same salt for all e-mails, or not use salt at all.

Selecting a salt based on the hash of the e-mail is no more secure than using the same salt. To see that, you need to understand what kind of attack salts are designed to protect against. Suppose than an attacker has n hashes to crack, and a dictionary of m e-mails. If each e-mail is hashed with an individual salt, such attacker will need to hash each e-mail in the dictionary with each salt, requiring n·m hash calculations. However, if the same salt is used, the attacker has to hash each e-mail only once, so just m hash calculations are needed. If the salt is deterministically selected based on the e-mail, than again only m hash calculations are needed.

In general, if your applications allows fast lookups by e-mail, the attacker can run the lookup procedure on all e-mails in their dictionary. No matter how the lookup procedure is implemented, if it's fast, the attacker would be able to use it to check all their e-mails quickly. So, using salts properly (as they are used for password hashing) is incompatible with fast lookups.

Answer 2

First of all, encryption is not hashing and hashing is not encryption. You talk about encryption and then go on about bcrypt, but bcrypt is meant for password hashing.

Whether to use hashing or encryption depends on your needs:

• If you have data that you need not know, but that you need to check later (such as a password) must be hashed. If you only use email addresses for identification, but it is never used or displayed, then you can hash those too (though it seems weird to me). Basically data that you want nobody to know and that nobody needs to know, even if they have database access.
• If you have data that must be kept private even if someone steals a disk from the server, but you must be able to find what it read, you should use disk encryption instead of TDE (as you say, MySQL has no TDE). There is no need for TDE specifically.

Inventing your own "poor hashing function" is like trying to rewrite ssh in assembly because you didn't read its man page and failed to notice that what you want probably already exists.

Also note that bcrypt is made to be slow, literally. Querying a database that has been hashed with proper bcrypt parameters is going to be terribly inefficient. The only way to circumvent that slowness is to use bad parameters, at which point you might as well get rid of bcrypt altogether.