I have faced a similar problem, for which I implemented the following mitigation. I would greatly appreciate input as I do not claim that this is necessarily an excellent solution.
Store IDs as
HMAC(ID, master-key) and each user's password is used to derive a per-user key to encrypt
Adversary capabilities / limitations
It protects against an adversary capable of reading all at-rest data, but not one that can read memory (e.g. intercept inter-process communication between the web server and the CGI).
One-to-one salts hinder searching
Efficient searching in your case requires indexing and searching for a single value. By salting each ID number you have to calculate
HASH(search query, salt) for all salts which is (a) inefficient when done for each search, and (b) ineffectual from a security perspective as described below.
Tiny search space
The primary issue lies in the fact that the search space of ID numbers is so small. Brute force attacks on hashes are, in addition to other means, mitigated by increasing work factors (a.k.a. stretching) with PBKDF2, bcrypt, scrypt, etc. However the search space is in fact so small that any significant-enough increase in work factor for adversaries would be too inconvenient for users (e.g. 30s+ per search).
Change the problem
My approach was to modify the problem to one of protecting a secret key. HMAC allows for both data (the ID number), and a key. IDs are stored as
HMAC(ID, key) while searches are performed with
HMAC(search, key). This requires exact matches, but can be made case-insensitive with
uppercase(search). A brute-force attack with a 256-bit key is infeasible even without increased work factor.
How do we protect the key? Query-API users are authenticated, so their password can be utilised (after salting and stretching) as the 'input keying material' (IKM) for HKDF. HKDF allows for independent keys to be generated from a single entropy source (the IKM) by inclusion of 'contextual information' and a salt. For the function
HKDF(IKM, context, salt) where
IKM = PBKDF2(password, rounds) we then calculate
HKDF(IKM, 'Authentication', 'user-specific non-secret auth salt') and
HKDF(IKM, 'KeyWrapping', 'user-specific non-secret wrap salt'). The former is stored in the database much like a regular password-authentication hash and the latter is used to wrap (i.e. encrypt) the master key used in the earlier HMACs (note that each user has their own wrapped master key).
Each time a session is authenticated, the unwrapped master key is wrapped inside an encrypted session. You can use HKDF with the (already secret) session ID to derive encryption / storage keys for the session. Unlike passwords which need to be stretched (incurring a second or two's delay upon authentication), session IDs can be generated from a CSPRNG (make sure to use
This raises another problem in that we need to initially wrap the master key for every user without actually knowing their password. Upon creating the user in the database they should have a private / public key pair created. The private key is encrypted with
HKDF(IKM, 'PrivateKeyEncryption', 'user-specific non-secret PKI salt'). Each user can then have the master key given to them by an administrative user. Upon logging in the system checks their pubkey inbox for any new master key and then wraps it for next time. You could actually just use the asymmetric approach, but it's computationally more expensive.
- It is impossible to reset lost passwords without requiring an administrative user to give the master key to the user.
- I'm NOT a cryptographer - there may be vulnerabilities that result from having multiple ciphertext instances of the same plaintext (EDIT: see first comment). If so, can this be mitigated by using random-length entropic prefixes and suffixes? Or is an IV sufficient? There may be other issues that I have completely overlooked.
- This relies on ephemeral secret keys (password upon logging in, session ID on each request) being stored in memory. I'm not sure how your cron job will function; one possible solution is to have it use asymmetric encryption with knowledge of a public key whose private key is encrypted with the master key that all users can access (any authenticated session can then move keys into the database).
- Does your threat model require such extensive engineering? Complexity results in more places for things to go wrong.