Deterministic Encryption using AES I am in need of a deterministic encryption algorithm I can use on social security numbers (9 character string, numbers only) that I will store encrypted in a MongoDB and need to be able to search for them and recall them (ruling out one way hashes).

For example, 11122333 is encrypted and then stored in the db.  The user then wants to know if 111223333 is in the db so i encrypt it and then search for the cipher text in the db.

db.patient.find({"PatientDemographics.SocialSecurityNumber" : "N9DF63vmf0fedH/YW5Et6g=="})

What I came up with is to use AES (in CBC-Mode) but purposefully gimp it using a un-changing IV.  I have it working with this change. I just want to make sure I am not completely ruining the encryption and only doing what I need to do to enable searching.

To summarize, If you got a dump of the db with the SSNs encrypted as described above, would you able to get the cleartext via some sort of attack without knowing the IV and Key? Would it help if i passed in the IV (instead of hard coding it) which would act as a second key?

Another option (that I havn't tried yet), suggested here, says to hash the ssn and use that as a IV.  I would then have to prepend the IV to the ciphertext and store it in the db.  Is this cryptographicly better?  My approach is having a secret static IV (requires key and IV to decrypt) vs this one having a deterministic IV prepended to the ciphertext (requires only key to decrypt).

If this is the wrong approach, can you recommend another that fulfills the searching requirement (implemented in C#)?

Hoping to get more constructive feedback than i got from the main site
First, you should specify:


what you need to be able to do in your database to get your job done;
what capabilities an adversary may have; and
what you want to ensure the adversary can't do.


Here's some generic guesses, but you should fill these in with specialized knowledge of your application's needs.

For (1): If all you need to do is search by a known SSN, as in SELECT * FROM users WHERE ssn = '123-45-6789' if there were no cryptography—in particular, if you never need to SELECT ssn FROM users WHERE ... and get back an SSN—then it is sufficient to hash the SSN irreversibly; there is no need for reversible encryption.

For (2): The standard threat model here is database disclosure.  But you might have a separate application server and database server, which have different attack surfaces and different risk of compromise, so you might consider compromise of the application server separately from compromise of the database server.

For (3): Obviously, one might hope that if your database is compromised, then the adversary nevertheless can't the SSN of anyone indexed by other information in the database.  But beware here: there's a lot that can be learned from the structure of databases even if individual records or identifiers are concealed.

Once you've read about leakage from databases even if encrypted, let's suppose for the moment that you just want to search by SSN, not look up SSN.  Here are some approaches.


You could store $\operatorname{SHA-256}(\mathit{ssn})$.

However, anyone who can read the database and find a hash $h$ in it can quickly enumerate all SSNs to find which one $h$ corresponds to by testing whether $h = \operatorname{SHA-256}(\text{000-00-0000})$, $h = \operatorname{SHA-256}(\text{000-00-0001})$, etc.  The problem here is that SHA-256 is a public function that anyone can evaluate, including the adversary, to test a guess, and the space of SSNs is very small.
You could store $\operatorname{Argon2}(\mathit{salt}, \mathit{ssn})$, with a per-row unique salt, and the largest time and space parameters for Argon2 that fit in your budget.

This raises the adversary's cost of testing a guess.  However, Argon2 is still a public function, so an adversary can still just test guesses—in parallel to get answers sooner, at the same total cost—and using Argon2, or any other sequential memory-hard hash, increases the cost for you to run your application too.
If there is a meaningful separation between the application server and the database server, so that an adversary could plausibly compromise one without the other, then you could store a secret key $k$ on the application server, and store $\operatorname{HMAC-SHA256}_k(\mathit{ssn})$.

Then, if only the database server is compromised, the adversary learns essentially nothing about the SSNs themselves: since they don't know $k$, they can't evaluate the secret function $\operatorname{HMAC-SHA256}_k$ to even test a guess.  Of course, once they break into the application server and recover $k$, the security is essentially as if you had used SHA-256.

The specific criterion here is that HMAC-SHA256 is a pseudorandom function family, or PRF.  Other PRFs would work too: keyed BLAKE2, SHA-3 KMAC, AES-CMAC, etc.


If you do need to store and retrieve the SSNs, you should use a deterministic authenticated cipher, such as a nonce-misuse-resistant authenticated cipher like AES-SIV or AES-GCM-SIV with a fixed nonce.  As it happens, authenticated ciphers like these also serve as pseudorandom function families, so you get essentially the same security as HMAC-SHA256 as long as the key $k$ is not compromised.  Be careful to check on the scaling limits of AES-SIV or AES-GCM-SIV in comparison to the potential volume of your database.