How to obfuscate a relation between two tables in a database?

Question

I have a kind of weird use case here, and I'm not sure how to deal with it.
I'm working on a project that stores medical data. The following requirement has been addressed by another team, but hasn't been much documented. I'm trying to understand if this is an acceptable solution, if there are any obvious vulnerabilities I may have missed, and if there's a better way to do it.

Requirement

The database stores medical data about patients.
We need to be able to query on the patient's name, surname and birth date.

On the other hand, in the case where someone would gain unauthorized access to the data, for example in the form of a database dump, we need to prevent that person from matching with certainty identities (name, surname and birth date) with medical information.
We are not required to protect the data against someone having admin privileges on the SGBD.

Present system

The Patient entity is divided in two tables. The first table holds the name, surname and birth date, while the second is the actual medical record, with all the relations to other entities.

The association is made through a hash of the identity stored in the medical record.

Identity                        Record
|id|name|surname|birthDate|     |id|hash|Some other fields...|

Basically, to get both the identity and the record, the SQL query looks like this:

SELECT * FROM Identity i JOIN Record r
  ON r.hash = hash(i.id || i.name || i.surname || i.birthDate)

Drawbacks

As stated in the comments, this provides virtually no security, since anyone knowing the code can compute the association.

Since we're using a single one-way hash, navigating from the identity to the medical record requires only one operation, but the opposite requires computing all the hashes.

The probability of simply guessing the association is inversely proportional to the number of records, although there is no way to check if that guess is true. (Unlike when guessing a password, where a public login form can give you confirmation.)

What I found so far

If querying on the name, surname or birth date wasn't necessary, we could just encrypt these fields.
If we encrypt these fields, the only way of querying them would be decrypt everything first.
I don't know why they used hashing instead of deterministic encryption for the association. Or they could have put a hash of the medical record into the patient table, so navigating from the record to the table would only require one operation.
The hash needs to be keyed or anyone seeing the code can compute the association.
The key would at the very least be stored somewhere on the application server.
The key would be passed to the SGBD in the query. That means it could be intercepted or logged, so the protection would work against someone getting, for example, a dump of the tables, but not against someone with admin rights on the DB.
Adding fake data and randomizing the order of the records can make it harder to guess the association.

Questions

First of all, is this viable at all?
Are there any obvious flaws I didn't mention?

There are a number of recommendations when dealing with hashes (algorithm type, salt, etc), but they usually apply to use cases where the data itself is not present in the database. Is it worth it to put them into practice here?

Is there a better general approach to this problem?

Are there any reference documents about handling medical data?

Answer 1

We need to be able to query on the patient's name, surname and birth date. On the other hand, in the case where someone would gain unauthorized access to the data, we need to prevent that person from matching identities (name, surname and birth date) with medical information.

Hashing in the current form is not a secure way of meeting this requirement. As you already mentioned, you can simply create those hashes for all patient and are done.

You do mention keyed hashing and encryption, yet I am unsure as to how that would increase security as the key would have to be somewhere and as long as that's not an HSM, database access probably comes with access to that key as well.

The secure way of solving the requirement would be to not store the patient data at all; there doesn't seem to be a requirement to list all patients or parts or filter patients by date of birth. If you choose the hash to be over FirstName|LastName|DateOfBirth, you can easily query for that data and receive all records for that patient without needing to persist that data.

If you must (I'm sure you must, albeit not in direct relation with the medical data) keep the patient data, keep it separate, i.e. in a physically different database.

Answer 2

It seems you have both Identity.id and Record.id, presumably both autoincremental primary keys, and both tables getting inserts approximately at the same time, so in many cases both ids will actually have the same value (or a fixed offset). You are doing things in a convoluted way attempting to be more secure, but it's broken.

I also don't see the point on using the name, surname and birthdate in the hash. Just name, surname and birthdate are not unique enough by themselves. Thus the need to for the id. But as you are taking into account the id, you don't need the other fields, and could simply use hash(Identity.id) or instead of a hash, an HMAC() or an encryption of the id.

Still, it would probably be simple to match many pairs of records just based on the order of insertions. In fact, the whole concept of "we must prevent someone that gets the whole database from matching the identities" is probably flawed. At least, if you protected the relation with a key stored in the application, you could take steps to protect that piece, and never store it alongside the database itself.

Finally, you mention that going from medical data to patient names requires computing all the hashes, and that is problematic, but I wonder if perhaps it was intended that the application should never go from medical data to patients but all searches must begin by looking up the patient. In which case they would have considered this not to be an issue.