We're building a cloud web app backed by a multi-tenant db. To maximize security we plan to encrypt each customer's data with a separate key. The problem is querying. Say they're in the report writer and want to sort their 1,000,000 customer table by LastName. That would perform horribly because all 1M rows would have to be unencrypted and then sorted on every query!

Here are the only options I could come up with. What would you do? Are there other options?

  1. Only encrypt NPI columns in the db and then never allow them to sort or filter by NPI values.

    PRO: Protects sensitive data while still providing great query performance on non-NPI columns

    CON: Not a great UX for our users

  2. Same as #1 but keeps an unencrypted cache of NPI columns in RAM

    PRO: Better UX

    CON: Now DataInUse is unencrypted (is that any better than DataAtRest unencrypted??). Also, filters with NPI and non-NPI columns would be very ugly to code. For example, if the filter was SELECT ALL CUSTOMERS WHERE LASTNAME LIKE "S%" AND BIZTYPE="MEDICAL", the lastname record ID's would have to first come from the cache and then sent to the database to further limit records by biztype.

  3. Give up and keep all data unencrypted in the database and apply db encryption (SQLServer TDE) or disk encryption.

    PRO: Great UX and performance

    CON: Performance would suffer. Also, if the key were compromised all of our customers' data would be exposed and we'd be on the cover of the Wall Street Journal.

  • SSNs are decently random. Sure, for pre-2011 SSNs, the first prefix denotes where people were born, and the lower bits have hints about when, but that's it. There's no reason to sort by SSN (unless mapping to another db that is already sorted that way), so I'd assume your option #1 is acceptable. Unless that's merely one example? Encrypted birth dates would indeed need to be sortable. – Adam Katz Jul 11 '15 at 1:31
  • You could encrypt blocks of customer data instead of encrypting everything with a different key. For more security you could change the keys from time to time – Freedo Jul 11 '15 at 2:59
  • Thanks @Adam but you're on the right track, SSN was a poor example. Let's use LastName or AddressState (I changed my original questions). – sisdog Jul 13 '15 at 4:16
  • What is your threat model? – Aron Jul 13 '15 at 18:25
  • Just a hint: there do exist some hash functions that will give you results with the same sort order as the source data. But, if I remember it right, they are applied to the whole sequence of data. – Barafu Albino Sep 29 '15 at 12:45

The problem is your solution:

"To maximize security we plan to encrypt each customer's data with a separate key."

Stop doing that. Using a separate key for each customer doesn't scale. Use a single key for the entire database.

Alternatively, encrypt the data using a hardware security module (HSM) before it's inserted into the database. Retrieve the encrypted data and then decrypt with hardware security module. Query performance will not suffer. Performance bottleneck is now move to hardware security module.


Have you considered hashing the data you want to index on?

The idea is simple. You add a column where you store the salted/peppered hash of the LastName, next to the LastName column. When the server needs to seek Mr Smith you simply hash the name Smith and then search for that hash value.

The problem of this approach is that it is possible to gain information on the database from the hashes.

  • Unfortunately you won't be able to sort a query result from the hashes, nor will you be able to search on partial strings. – Simon East Jul 19 '15 at 11:06
  • Have you considered a rolling hash... Unfortunately I know of no, cryto rolling hash. Given that you want partial string search you have no choice but to have the data completely readable by the database. Therefore you want TDE. – Aron Jul 19 '15 at 11:09

A variant suggestion:

  1. Create a new ID record for each new customer loaded
  2. Encrypt the SSN
  3. Work only with the new id to select/retrieve

PRO: performance maintained, SSN encrypted
CON: a new ID to memorize for the users

  • I'm not trying to retrieve one row. I'm trying to sort all rows by a given column of NPI information (like LastName). – sisdog Jul 13 '15 at 4:17
  • So as indicated by Aron below, you need an index "in relation" with the confidential information you store. This could be done background by a batch rebuilding nightly this new index on the basis of this confidential info (eg LastName). However special attention to this batch as it need decrypting everything, so it should be sesigned to process row by row. – Philippe Bellamit Jul 14 '15 at 7:22

Your Answer

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

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