2

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:

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

8
  • you will at least need to encrypt the whole of your second column, otherwise the mapping will leak information about relationships between values. – Jack Dec 3 '19 at 2:34
  • You should understand that whatever this custom encryption algorithm of yours is, it is not secure. Why are you including it? If you are also encrypting with AES, then you should just stick with AEA – Conor Mancone Dec 3 '19 at 2:44
  • 1
    You can try searching for Searchable Symmetric Encryption (SSE). – AlphaD Dec 3 '19 at 3:24
  • 1
    @KennyEvitt Yes, its not something I would consider for production just yet but it's probably the closest to what this question is looking for. – AlphaD Dec 3 '19 at 6:58
3

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:

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:

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.

8
  • The answers on your link, suggests using HMAC but says that will leak information as well. So that would not work as well, correct? I see no substantial increase in security using HMAC. – Shreyash Sharma Dec 6 '19 at 2:36
  • @ShreyashSharma Would you quote what exactly you think claims that HMAC will leak information as well? (There are seven links in my answer and two that I think you're probably referring to.) Maybe you meant these sentences from the "encryption" link?: "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); ...". – Kenny Evitt Dec 6 '19 at 15:51
  • @ShreyashSharma I think I understand your comment now. If you decided that you do want to create indexes of encrypted values for searching, for either 'whole' strings or substrings – despite the weakened security – then you should probably use an HMAC algorithm to generate the values to be used in those indexes. But yes, overall, you probably shouldn't create indexes of encrypted values at all. – Kenny Evitt Dec 6 '19 at 16:22
  • Thank you for the replies and updating your answer. I was going through the paper on CryptDB (people.eecs.berkeley.edu/~raluca/CryptDB-sosp11.pdf) & they have a similar approach in the paper which is detailed on page 5 under "Word Search". They are providing an extra layer of security with the proxy and the database will only give a "yes" or "no" for the LIKE queries. So what if I was to keep the indexes of the complete name strings ("John" "Johnny") on a separate database with its own encryption and TDE and this one database only revealed the indexes(hashed) for that second db? – Shreyash Sharma Dec 7 '19 at 10:28
  • I was focused on TDE as I am trying to accomplish all this to save the data to be seen in plain text from the privileged user, and there will only be one user, that is because I need at least one user to fire queries on the database. – Shreyash Sharma Dec 7 '19 at 10:29

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.