Hiding identifying data while allowing matching?

Question

I do research with people about their illegal drug use, and for one project I'm doing surveys with them when they visit a needle exchange. So over time the same people get repeatedly surveyed as they visit the exchange many times over.

In order to link together multiple surveys from the same person across time (because we want to track things like engagement with drug treatment and changes in level of drug use), I ask them to give me some information that they can remember from visit to visit but which would at least moderately limit the ability of someone to identify them from it: the first two letters of their mother's first name, the day of the month on which they were born,and their gender. E.g. a woman (F) born on [month]/20/[year] whose mother's name is Jane would get the code JA20F.

So every survey gets this code as a unique identifier, and you can link multiple surveys done by the same person without having to record blatantly identifying info like names and dates of birth (or ask a street-based drug user, potentially with mental health problems as well, to remember a unique study ID from visit to visit). Not perfect from a security point of view, and not unique if you have thousands of people, but when the data is being entered on a single laptop with full disk encryption and all study files are stored encrypted and you have a Federal Certificate of Confidentiality (protects research data on illegal activity against subpoena), and there's only about a thousand people using the service, probably good enough.

But storing that identifier still bothers me. I'd really like to do something to it at the point of data entry so it can't be 'reversed' back to the potentially identifying day of birth, gender, and first two letters of mother's first name. My initial thought was to hash the unique identifier before storing it, which again is better than nothing but anyone who knows the format of the unique identifier could easily use a rainbow table approach to unmask it. As I understand salting, self-salting would mean the hash was different each time for the same individual, so I'd lose the ability to link surveys done by the same person. And using a single salt would just make the salt the vulnerable piece of data.

Does anyone have any ideas (or well established techniques I'm just ignorant of) for one-way hashing a string which a) is not vulnerable to rainbow tables, but b) produces the same output every time from the same input?

Answer 1

Any transformation of the identifier, including those in the question, is bound to have at least one drawback: after a transformation of cryptographic quality, it will be next to impossible to re-agregate identifiers that refer to the same person but have been slightly garbled (perhaps because there are two common spelling of the mother's name).

Even ignoring that, I do not see a convenient and bulletproof solution, basically because you start from a very short identifier.

One improvement would be to encrypt the identifier using a secret key, with format-preserving encryption, so that the encrypted result remains short, compatible with existing practice, and the encryption demonstrably can't introduce more collisions than there is originally. A most serious problem then is protecting the secret key, and limiting its use (which is necessary since it is enough to encipher a few chosen inputs to break the system).

Better than nothing is making this key passphrase-protected (like a PGP key is), with the passphrase entered on the laptop by the legitimate user at the beginning of data-collection activities. Standard key stretching techniques can make that quite safe against passphrase search, while still robustly detecting an accidental mis-keying. While we are at it, all data collected should be kept encrypted with standard techniques (using a different key, possibly protected by the same passphrase for convenience).

Even better is moving the key in a Smart Card, protected by user PIN with consecutive errors counter. Next step (recommendable, and quite easy even with standard Smart Cards) if moving at least a building block of the format-preserving encryption into the Smart Card itself, so that the key never leaves the Smart Card (said building block could be AES or a MAC, and the corresponding key, used in the round function of a Feistel cipher). Ultimately, the sensitive data could be held in the Smart Card itself and inaccessible without the PIN.

Beware however that nothing in the above can resit an active compromise of the laptop (e.g. key logger) performed before sensitive data is entered.

Answer 2

In this case there is no need for a rainbow table, since at most the identifier has about 15 bits of information. You can cycle through all possible values (there are $26^2 \cdot 31 \cdot 2 = 41912$) and even if they were hashed with a salt you will find the preimage in a fraction of a second.

So the only way to protect the information is with a secret key, which would likely be compromised if the data was, or with another authentication factor (like password) which might not. Of course, you need the factor whenever you enter data, so at that point the data is necessarily vulnerable. If you already encrypt your data with a password, this does not really add anything.

---

If you collected more information, you could get a high enough amount of "entropy" that a salted password hash might make preimage finding difficult, but that would require a lot of information and then you would be making identification definitive. I would not recommend that.

Instead, the best you can do is keep the laptop secure. Collect just enough information, but no more. And when done collecting and collating all the data, immediately remove/replace the identifiers with non-identifying numbers – e.g. random numbers – so that there is nothing to compromise thereafter.