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.

You could probably extend this by making a "full text" index of hashes, if you needed to, but it could get complicated really fast.

ADDENDUM

It's been suggested that I add a footnote to my answer per a fairly lengthy debate in chat about vulnerability to dictionary attacks, so I will discuss this potential security risk to the above approach.

Dictionary Attack: A dictionary attack is when someone pre-hashes a list of known values, and compares the hashes to your hashed column in the database. If they can find a match, it's likely that the known value is actually what is being hashed (It's not definite though, because hashes are not guaranteed to be unique). This is usually mitigated by hashing the value with a random "salt" appended or prepended so the hash will not match the dictionary, but the above answer cannot use a salt because you lose the searchability.

This attack is dangerous when dealing with things like passwords: if you create a dictionary of popular password hashes, you can then quickly search the table for that hash value and identify a user that has such a password and effectively extract credentials to steal that user's identity.

It is less dangerous for items with a high degree of cardinality, like SSN's, credit card numbers, GUIDs, etc. (but there are different risks [read: legal] associated with storing these, so I am not inclined to advise on storing them).

The reason for this is in order for a dictionary attack to work, you need to have pre-built a dictionary of possible values and their hashes. You could, in theory, build a dictionary of all possible SSNs (a billion rows, assuming all formatting permutations are removed; multiple dozens of trillions of entries for credit cards)... but that's not usually the point of a dictionary attack, and basically becomes comparable to a brute-force attack where you are systematically investigating every value.

You could also look for a specific SSN or credit card number, if you're trying to match a SSN to a person. Again, usually not the point of a dictionary attack, but possible to do, so if this is a risk you need to avoid, my answer is not a good solution for you.

So there you have it. As with all encrypted data, it's usually encrypted for a reason, so be aware of your data and what you are trying to protect it from.

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.

Answer 4

I'm looking into this and came across your question. I'm leaning towards the approach outlined in section 5.4 of the paper "Practical Techniques for Searches on Encrypted Data" http://www.cs.berkeley.edu/~dawnsong/papers/se.pdf

The basic gist is to create an index that contains encrypted keywords that are present in the encrypted search document. The trick is to also encrypt the locations in the document (or database) where those keywords are present.

Answer 5

Programmatically, an efficient solution is to

1. retrieve ALL of the records for ONLY the field you are searching against with the record id
2. decrypt those into a temporary table
3. perform the search against that table
4. use the id's to retrieve the full records (all fields) that match the search criteria
5. decrypt those and return them to the user

The point is that 1 and 4 are significantly smaller sets of data than retrieving and decrypting all fields of all records in the beginning.

Hope that helps.

Answer 6

This is possible with full search functionality by using MYSQL's internal encryption functions.

Here's an example:

!!! I AM USING MYSQL ENCODE() HERE FOR SIMPLICITY, MYSQL_ENCODE IS NOW CONSIDERED INSECURE, USE ONE OF THE OTHER INTERNAL MYSQL FUNCTIONS INSTEAD!!!

UPDATE my_table
SET field=ENCODE('my_data', 'my_password')
WHERE ID=1;

SELECT DECODE(field, 'my_password') as field FROM my_table
WHERE field LIKE 'data';

As the comment above suggests, do NOT use ENCODE(), use one of the other encryption functions I am only using ENCODE in this example due to its simplicity

If you are doing this within an application such as php, you can do this within your db gateway or repository classes by storing a list/array of each table's encrypted columns within the its respective gateway class.

class UserGateway
{
    protected $encrypted_fields = array(
        'username',
        'email'
    );

    public function get($fields, ...)
    {
        foreach ($fields as $k => $field) {
            if (in_array($field, $fields)) {
                $fields[$k] = $this->decodeSelect($field);
            }
        }

        $sql = 'SELECT '.implode(',', $fields);

        //......
    }

    protected function decodeSelect($field)
    {
        return "DECODE($field, $pass) AS $field";
    }
}

Of course this is very rough and insecure code that should not be used in production without significant improvement. But it should serve its purpose in giving the general idea.

Answer 7

So I had an idea that might accomplish this, but it's all conceptual.

Suppose that you had the value "Lorem ipsum dolor sit amet", and you wanted to do a search for "lorem". One way is that you could take the original and break it up into chunks (lowercased), and put them in a second table. The whole (original) value is in the original table column with row_id 123, but a new table called "chunks" might have:

row_id | chunk | foreign_row_id
1      | lo    | 123
2      | or    | 123
3      | re    | 123
4      | em    | 123
5      | m     | 123
6      |  i    | 123
7      | ip    | 123

Think of it like a substring index, where every substring is 2 characters long.

Now, when a user wanted to perform a search, you would similarly chunk that up, then do a lookup. If they typed "lo", then you see which foreign row IDs matched. But if they enter "lore", then you do a search for all foreign row IDs that had a matching chunk for "lo", "or", AND "re".

So far, not too practical. However, if the original value "Lorem ipsum dolor sit amet" is encrypted or hashed, then you could ALSO chunk up the 2-char substrings, encrypt/hash them, then do a lookup on the chunks instead or the full string. No decryption or unhashing necessary.

The logic would be:

1. Chunk the search string
2. Encrypt/hash each 2-char chunk
3. Do the lookup and find all encrypted/hashed chunk matches.

Any match can then be fetched from the original table. This would protect the data at rest, because if the chunk table was compromised, they can't do anything with a bunch of encrypted/hashed 2-char values. You can't take 2 encrypted/hashed substrings and recombine them or get anything meaningful from them.

If I am the inventor and got to name this, since it's similar but not quite the same as making a Rainbow Table, I would called this "Fruity Pebbles Tables". Because of the chunks.

Answer 8

Assumming you are searching in SQL and against the full value and not partial (e.g. LIKE 'value%')...when capturing the search data, encrypt that data using the same algorithm used when the data was encrypted and search for that.

For example:

What would have been:

SELECT FieldA, FieldB 
FROM Table1 
WHERE FieldC = 'Value'

Might instead look like:

SELECT FieldA, FieldB 
FROM Table1 
WHERE FieldC = 'hsk&%67ghhks83'