# 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

• The best would probably to use AES-SIV. Here's a multi-language implementation / binding. – SEJPM Mar 15 '19 at 11:02
• @SEJPM AES-SIV looks good. would you like to turn this to an answer so I can give you credit? Thanks – josh Mar 15 '19 at 14:30
• @SEJPM can i ask you to address the paragraph that starts with "another option..." Is AES-SIV better than AES with a deterministic IV prepended to the ciphertext? – josh Mar 15 '19 at 20:54

Would it help if i passed in the IV (instead of hard coding it) which would act as a second key?

No. Most attacks on IV-reuse don't need to know the IV and merely exploit the fact that it was reused under the same key.

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?

It depends. IV-reuse in CBC-Mode allows you to detect common prefixes. So if two ciphertexts share eg the same first block but have different second blocks, you can detect this fact. But you can't actually extract concrete values. Of course leaking prefix-equality isn't optimal (actually it is if you require tto be able to stream-process messages).

Another option (that I havn't tried yet), suggested here, says to hash the ssn and use that as a IV.

(Variants of) This is the basic principle of SIV-Mode. You first compute a MAC over the message and optionally an IV, use this as a tag and use this tag as the IV. This allows you actually only leak complete equality of ciphertexts which I think is the property you are after here.

Is AES-SIV better than AES with a deterministic IV prepended to the ciphertext?

Yes. First because most modes are not designed to handle repeating IVs and break more or less horribly (GCM moreso than plain CTR moreso than CBC). Second because AES-SIV is actually standardized for misuse-resistant authenticated encryption, which is authenticated encryption which still offers the desired only-equality-leaks-on-IV-reuse security you want.

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

So if you need decryption capabilities, the aforementioned AES-SIV is your best option. It has seen the most analysis and it sounds like your messages aren't long enough to warrant AES-PMAC-SIV and you're actively and intentionally misusing your IVs and thus AES-GCM-SIV is out, which is more optimized for accidental re-use. There's a library that looks decent that implements it and offers bindings for C#.

• Thanks so much for your through and clear answer. Appreciate you taking the time – josh Mar 17 '19 at 3:09

First, you should specify:

1. what you need to be able to do in your database to get your job done;
2. what capabilities an adversary may have; and
3. 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.

• I appreciate your lengthy and informative answer. unfortunately i do require recallability so a one-way hash is not possible. My apology's for not stating this in my post. Looks like AES SIV is what I am after. – josh Mar 15 '19 at 14:33
• Yes, it sounds like for your application AES-SIV is a reasonable choice. That said: please do read Matthew Green's blog post about leaks in encrypted databases. – Squeamish Ossifrage Mar 15 '19 at 14:39
• can i ask you to address the paragraph that starts with "another option..." Is AES-SIV better than AES with a deterministic IV prepended to the ciphertext? – josh Mar 15 '19 at 20:54
• @josh AES-SIV is AES-CTR with a deterministic (but secret) hash of the message used as the IV/nonce (and authenticator). (If you use a public hash rather than a secret hash of the message, then an adversary can confirm a guess about what the SSN is by computing the hash and comparing it to the prepended IV/nonce.) AES-GCM-SIV is a little more involved with somewhat better security bounds, but is costlier in software, and hasn't been stably defined for a decade like AES-SIV has been. – Squeamish Ossifrage Mar 15 '19 at 22:20
• @SqueamishOssifrage I thought the bounds for AES-GCM-SIV were reduced in recent analysis for the nonce-reuse case and I was under the impression that AES-SIV handles large-scale misuse better? Are they actually equally bad? :o – SEJPM Mar 15 '19 at 23:06