4

I'm developing a system that has to store Finnish national identification numbers as securely as possible while allowing "does this identification number exist in the system?"-type queries over a web API.

At first glance, the answer might seem obvious: store a salted hash of the number, so that when you're given an API query containing an unencrypted ID number, see if its salted and hashed version exists in the database, as you do with passwords.

However, while this approach might work nicely enough with passwords, it's not nearly as simple with ID numbers, because there are so few possible ones. Their format is DDMMYY[-+A]XXXZ. For any year YY you have 365 or 366 possible DDMM combinations. For each DDMMYY combination you have a sequential number XXX, from 002 to 899. Z is a checksum character calculated from the nine preceding digits. The -/+/A separator between the date and the number sequence denotes the birth century.

If an attacker gains access to the server, they have access to the Python source code and the database, and can therefore instantly see how the salting and hashing of ID numbers is done. Given the small number of possible ID numbers (which can be reduced further with demographic knowledge about the people stored in the database), it's trivial to generate all the possible salted hashes for every possible identification number, for every person in the database.

I considered public key crypto, but that fails because encrypting a value with a public key on two different occasions produces two different ciphertexts, so they can't be used in lookups like hashes can.

Am I missing something obvious, or is there really no reasonably secure way in which to store ID numbers that could be used for lookups AND that could withstand a server breach, where the hashes and the source code with which they were created end up in the wrong hands?

migrated from stackoverflow.com Apr 25 '15 at 22:20

This question came from our site for professional and enthusiast programmers.

  • I'm voting to close this question as off-topic because this is not directly related to programming. Questions such as this are much better suited for Information Security. – Artjom B. Apr 22 '15 at 12:51
  • I've never even heard of that site before. Good to know. (If there's a way to move it there directly, I'm all for it.) – JK Laiho Apr 22 '15 at 12:53
  • Under what circumstances will ID numbers be entered into the system? Will data-entry users be authenticated? Will they also be authenticated when checking if the ID exists in the database? I have implemented a similar solution, but it is reliant on (at least) lookups being in an authenticated environment; I'd like to know a little bit more about your needs so I can tailor an answer. – Arran Schlosberg Apr 27 '15 at 4:16
  • 1
    @ArranSchlosberg The ID numbers are created in the database in bulk by reading in CSV files. These CSV files are regularly uploaded over SFTP by several organizations, each of whom maintains a subset of the ID number pool. Each has a separate SFTP account. (The storage of the CSV files is encrypted and short-lived, just long enough to allow for a cron job to process and then delete them.) The query API is thoroughly authenticated and IP firewalled, limiting its use to only a few different organizations that require access to the ID numbers. – JK Laiho Apr 28 '15 at 7:08
1

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.

TL; DR

Store IDs as HMAC(ID, master-key) and each user's password is used to derive a per-user key to encrypt master-key.

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(ID) and 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 HttpOnly and secure flags).

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.

Caveats

  • 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.
  • 1
    Re caveat 2 see this question: security.stackexchange.com/questions/87073/… – Arran Schlosberg Apr 29 '15 at 4:26
  • 1
    An excellent, thorough answer. Marked as accepted. There are multiple concepts here that are foreign to me, so I can't just run out and implement this right away, but this at least points out several things I need to study. – JK Laiho Apr 29 '15 at 11:55
0

If an attacker gets your Python code, both options (use salt+hash or public key crypto) aren't safe enought...

But when you say:

I considered public key crypto, but that fails because encrypting a value with a public key on two different occasions produces two different ciphertexts, so they can't be used in lookups like hashes can.

It's only true if you sign different contents (because your salt), but why add salt then? why don't sign with public key your hash (without salt) and delegate the security to public key encrypt? Generated chipered content will be always the same, but will be secured with a strong chiper method (as strong as you choise). But again, if an attacker gets your private key your're also owned...

If I'm not missing some mechanism, I think that if no private secret it's kept safe (your python code, your private key...) anyone can generate the same as you.

  • Using PyCrypto's PKCS1_OAEP cipher (which comes recommended by PyCrypto) and RSA, encrypting a string produces a different ciphertext each time, with no salt. – JK Laiho Apr 22 '15 at 12:49
  • 1. There is a problem with your terminology: "why don't sign with public key your hash (without salt) and delegate the security to public key encrypt?" What does this mean? Signing is only done with the private key not the public key. 2. "It's only true if you sign different contents (because your salt), but why add salt then?" Signatures of the same content may be different depending on the padding used. This is a security feature. Also, what is chiper? Do you mean cipher? – Artjom B. Apr 22 '15 at 12:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.