[Cryptography] Pragmatic, column-level data encryption at rest. Possible?

[Jaycevee]

I am a software developer and security professional in a regulated
industry. Over the last five years I have seen more prospective
customers making demands for data encryption at rest. It always made
common sense to me that backup data and employee laptops can be easily
encrypted, and should be.

That being said, it's apparent more customers are now demanding database
encryption. At first, I always thought this was silly, given that
apparent solutions include whole disk encryption or so-called
"transparent database encryption", which does nothing to alter the
visibility of data through the existing SQL interface. It seemed obvious
that the only possible thing that could protect you from is the theft of
a server, and then only if the attacker isn't sophisticated enough for a
cold boot attack (or splicing a battery into the power cable while the
system is running, or attacking it over a peripheral bus, etc.) Assuming
your solution didn't involve admins punching in the decryption key on
every boot, it seemed to me that there was another huge hole in key
management.

For some years, I managed to dodge that requirement, and maybe only lost
one big deal by being honest.

Bruce Schneier wrote about this exact problem in 2006 and seemingly
succumbed to pressure to walk back his argument in 2014:
https://www.schneier.com/blog/archives/2010/06/data_at_rest_vs.html

Now, we have customers demanding field level encryption, and I'm on the
verge of going bonkers. For what it's worth, we're not talking about
credit card or bank account numbers, or the names of active-duty CIA. We
store "PII", but we're talking about some pretty limited data like
customer names, account numbers and phone numbers. Unfortunately, we
have requirements for that data to be searchable (in a way that does not
involve whole-table scans), and most of the data has to be available for
batch processing.

The way I see it, there are two issues. I can't work out how you can
make the data searchable without storing an index of unsalted hashes,
which obviously becomes the weak point in the cryptosystem protecting
the data. Even with the index of hashes, you can't search on partial
values, but let's put that aside for a moment.

Even with perfect ciphers, all this does is to create a key management
nightmare. The fact that batch processes must manipulate virtually all
of the "encrypted" data makes it all seem pointless.

I'm aware that there are research projects on homomorphic encryption but
I don't know that there are any commercially viable solutions.

There are a few things about my present situation I find to be
especially interesting:

1. PCI-DSS version 3 still allows full-disk encryption to satisfy
Requirement 3 (protecting stored credit card numbers). But given that
PII legal standards are evolving such that any *single* item of
information such as a customer name constitutes PII (thanks California),
a requirement for column-level encryption of this PII seems over the
top.

2. There is remarkably little information in my (admittedly casual)
Google searches about this kind of crypto problem. In contrast, the web
is full of vast amounts of information about nearly any other computing
or crypto concept you can imagine. If this is a solved problem, why the
secrecy?

3. What information does seem to be available is usually in the form of
marketing copy for products that smell like snake oil.

4. A few customers are starting to act like this is standard, best
practice. I have no doubt some of my competitors may be exaggerating
what they are doing, but by how much?

5. Is the computer business doing itself a massive disservice by
pretending we can do this, leading the less informed to believe in (and
to demand) witchcraft?

What I'm hoping for is a sanity check. Am I just uneducated about this
subject? Am I overstating my case like Schneier said he did in 2006?
What constitutes best practice in this area? If, as Schneier later said,
database encryption at rest may not improve security in the crypto sense
but in the computer security sense, where are the O'Reilly books on
using these systems? If my training as a crypto consumer has taught me
anything, it's that I shouldn't invent such a system myself. So what can
I pull down off the shelf that isn't $1,000,000 worth of smoke and
mirrors?