How to search a MySQL database with encrypted fields

Question

Suppose I need to encrypt certain table-fields of a MySQL database. Additionally, I need to search some of those fields I did encrypt.

How would one search those fields anyway?

Decrypting each record step by step is no option: Suppose I have multiple of thousands of records. It would take too much time and space to decrypt each record and check if each single record matches the search.

UPDATE 2012-09-07

Adding further details to the database schema would be OK, since I'm about to implement a new application. Furthermore, I need to extend applications currently running in production. But even for those application, adding further details would be OK.

UPDATE 2012-09-08

Encryption is the kernel of this question.

Access restrictions, as proposed by some answers, already apply - but do not fit the formal requirement to encrypt data.

This formal requirement is not Payment Card Industry Data Security Standard [PCI].

Answer 1

Obviously they are not meant to be viewed, therefore searching on them would be problematic.

One trick I have used in the past is to hash the encrypted data before encrypting it, and storing the hash in an indexed column. Of course, this only works if you are searching on the whole value; partial values will not have the same hash.

Answer 2

You may want to take a look at CryptDB. It's a front end for MySQL and PostgreSQL that allows transparent storage and querying of encrypted data. It works by encrypting and decrypting data as it passes between the application and the database, rewriting queries to operate on the encrypted data. and by dynamically adjusting the encryption mode of each column to expose only as much information as needed for the queries the application uses.

The various encryption methods used by CryptDB include:

• RND, a fully IND-CPA secure encryption scheme which leaks no information about the data (except its presence and, for variable-length types, length) but only allows storage and retrieval, no queries.

• DET, a variant of RND which is deterministic, so that two identical values (in the same column) encrypt to the same ciphertext. Supports equality queries of the form WHERE column = 'constant'.

• OPE, an order-preserving encryption scheme that supports inequality queries such as WHERE column > 'constant'.

• HOM, a partially homomorphic encryption scheme (Paillier) which allows adding encrypted values together by multiplying the ciphertexts. Supports SUM() queries, addition and incrementing.

• SEARCH, a scheme that supports keyword searches of the form WHERE column LIKE '% word %'.

• JOIN and OPE-JOIN, variants of DET and OPE that allow values in different columns to be compared with each other. Support equality and range joins respectively.

The real power of CryptDB is that it adapts the encryption method of each column dynamically to the queries it sees, so that the slower and/or less secure schemes are only used for columns which require them. There are also various other useful features, such as chaining encryption keys to user passwords.

If you're interested, you're well advised to take a look at the papers linked from the CryptDB website, particularly "CryptDB: Protecting Confidentiality with Encrypted Query Processing" by Popa, Redfield, Zeldovich and Balakrishnan (SOSP 2011). Those papers also describe the various security and performance tradeoffs involved in supporting different query types in more detail.

Answer 3

I don't understand why the current answers haven't questioned the requirements fully, so I'll ask and leave it as an answer.

What are the business reasons? What data do you need to encrypt and why? If you're looking for PCI compliance, I could write an essay.

Questions about your requirement:

• Will you need to return a exists/not exists as a result, or the actual data?
• Do you require a LIKE '%OMG_SEKRIT%' capability?
• Who cannot see the data and why?

RDBMS security is normally done on a permissions basis that is enforced by user/role. The data is normally encrypted by the RDBMS on disk, but not in the columnar data itself, as that doesn't really make any sense for an application designed to efficiently store and retrieve data.

Restrict by user/role/api. Encrypt on disk. If you're storing more important data I'd love to know why you're using MySQL.