Security flaws of storing strings and some of its substrings using Microsoft SQL Server Transparent Data Encryption?

Question

I am creating a database table with an encrypted value, say users:

Say John encrypted is U2FsdGVkX193AOGlBRE1RNScJRGN9vSB4erIljJwaKw=.

UserId | Name
------ | --------------------------------------------
1      | U2FsdGVkX193AOGlBRE1RNScJRGN9vSB4erIljJwaKw=

Johnny would be encrypted as U2FsdGVkX19lYDuvuBg3BzTnZro4J6zKoo9s/TLeiPU=.

UserId | Name
------ | --------------------------------------------
1      | U2FsdGVkX193AOGlBRE1RNScJRGN9vSB4erIljJwaKw=
2      | U2FsdGVkX19lYDuvuBg3BzTnZro4J6zKoo9s/TLeiPU=

How could I search for names beginning with Jo?

I was thinking of storing:

NameStub | UserId
-------- | ------
Jo       | 1
Jo       | 2
Joh      | 1
Joh      | 2
John     | 1
John     | 2
Johnn    | 2
Johnny   | 2

I can now do searches like 'Jo%', 'Joh%' and both will include both users.

I can see the obvious security flaw with the above that anyone can map out stubs like Jo or Joh.

So I have decided to store the stubs encrypted:

NameStub    | UserId
----------- | ------
enc(Jo)     | 1
enc(Jo)     | 2
enc(Joh)    | 1
enc(Joh)    | 2
enc(John)   | 1
enc(John)   | 2
enc(Johnn)  | 2
enc(Johnny) | 2

where enc(x) is just the encrypted value for x.

When searching for Joh, I will encrypt Joh and then query for matching stubs and any associated users with names for that stub.

Note:

• Both of the encrypted columns will use different keys and algorithms to protect the data.
• I will be using Microsoft SQL Server Transparent Data Encryption (TDE).

I need to understand if I am missing something fundamental here.

Answer 1

TLDRTLDR

Don't do this!

TLDR

• TDE is irrelevant for this question.
• Don't do this (index encrypted substrings of encrypted strings).
• Don't index encrypted values generally.
• If you are going to do this anyways, use an HMAC or other MAC algorithm to generate the encrypted values to be used in the index(es).
• If you're feeling really lucky, consider using a format-preserving encryption algorithm or a "Searchable Symmetric Encryption (SSE)" algorithm instead of a MAC algorithm.

TDE

I'm assuming "TDE" is Microsoft SQL Server Transparent Data Encryption. TDE is irrelevant (for your question). TDE encrypts an entire database and is 'transparent' to database users or other clients connecting to the database. What TDE protects from is an adversary accessing the data in the database offline, i.e. via copies of the database files or copies of the encrypted data, but without also having access to the encryption key with which the secured data was encrypted. Think of an attacker stealing a backup of the database, e.g. stealing a backup tape cartridge containing the database data or log files. If an attacker can access a live database for which TDE is configured, and the database system doesn't otherwise deny them access to the secured data, they can access any data in it (that's not otherwise encrypted apart from TDE).

Indexing Encrypted Data

The most secure method of searching encrypted field values is going to be to decrypt all of the field values to be searched first. Ideally, you'd do this directly in the database, e.g. in a stored procedure or function. It seems unlikely that an attacker could read the memory of your database process(es) but not also access the encryption key(s) used to encrypt the data in the database.

Your idea of storing encrypted "stubs" or substrings will weaken the security, perhaps substantially. This is a great answer on another question on this site that seems to generalize your question somewhat:

• encryption - Indexing encrypted data for efficient searching

That answer points out an important reason why this approach weakens the security:

At best, what you could do is to implement deterministic encryption, such that encryption of a given record value always yields the same encrypted result. This leaks a modicus of information (if two records have the same contents then this will show, despite the encryption layer); on the other hand, it allows for exact searches: you encrypt the value to search, and use the index on the encrypted values.

You can't create an index of encrypted values without exposing (to people that can see those encrypted values) that equal values are equal. Typically, values would be encrypted with a salt that's unique to each specific instance or occurrence of a value but one consequence of that is that any number of instances of the same cleartext will be encrypted using different salts and thus will result in different encrypted values. This is one reason why decrypting the values to be searched – before searching – is probably the best choice if you really need to store these values encrypted by default, even for authorized database users.

Note that this same weakness applies even for searches for exact matches, i.e. even if you're just indexing the encrypted values whole for performing searches for exact matches. In fact, for the two sentences I quoted above, the sentence immediately following is:

Substring searches, however, should be avoided at all costs.

(That's referring to indexing encrypted substrings.)

Algorithms for Indexes of Encrypted Data

But – if you decide that weakening security as described above is something you're willing to accept, then – cryptographically – the top two answers on this related Stack Overflow question suggest using a MAC algorithm to generate the indexed version of the field to be searched:

• database - What's the best way to store and yet still index encrypted customer data? - Stack Overflow

This answer on the same question above suggests carefully considering using a format-preserving encryption algorithm, the care being in knowingly using a class of algorithms that are relatively new and thus possibly vulnerable to attacks not yet publicly known.

In this comment on this very question, @AlphaD suggests considering using a "Searchable Symmetric Encryption (SSE)" algorithm. This should only be considered with even more care than for considering a format-preserving encryption algorithm. SSE algorithms are so new that there wasn't even a Wikipedia page for them when I checked.