Deterministic Encryption with AES GCM - how to choose the IV (nonce) I have not a very large background in cryptography so I hope these questions are not very dumb. I don't want to reinvent the wheel, I'm just looking for advise on the best practices about how to build the following. 

I've seeking and reading for several hours now and didn't find any answer that fulfills my concerns. Therefore, I've came out with a solution which I want to have some feedback.

The Problem

I want to provide a stateless micro-service for deterministic encryption of sensitive information. Some of this information (i.e.: personal identification number) might be used as primary keys in databases, that's why the cipher text needs to be deterministic.

This microservice will have an oauth2 schema, so it will be the unique point for encryption and decryption. There won't be key sharing at all.

Different applications will call this service for encrypting sensitive information, sharing it among others and at some point, another application with right credentials will ask for it's decryption.

API pseudocode:

encrypt (sensitiveInfo: String): String
decrypt (ciptherTextStruct: String): String


Considerations


Using AES-GCM, IVs must be unique
IV must be returned along with ciphertext
IV should not be a hash of the plaintext since they don't provide confidentiality.
Ciphertext will be returned within a structure (which will contain a key "version" used for key rotation)


Proposed solution

Basically, I thought the IV to be another ciphertext:

mail (input) +--&gt; hash() --&gt; IV        \
             +--&gt; mail   --&gt; PlainText |-&gt; Cipher text 1 (C1)
password (secret) ---------&gt; Key       /


Then:

Cipher text 1 (C1) --&gt; IV        \
mail ----------------&gt; PlainText |-&gt; Cipher text 2 (C2)
password (secret)  --&gt; Key       /


Finally, the method encrypt (sensitiveInfo: String): String will return a structure with C1+C2 (maybe a json structure), and the method decrypt (ciptherTextStruct: String): String will take C1 from the structure, use as the IV, C2 and the secret key and return the plaintext as expected.

Feedback

I'm worried about having any kind of information disclosure on playing with C1 and C2 that I'm not seeing in this picture.

Edit: I could also use the second IV as a hash of C1, that way no playing between C1 and C2 would be possible.

I'm pretty sure that I am kind of reinventing the wheel on this, so I really appreciate some help about which is the best way to proceed.

Thanks!
Your proposed solution will work, mostly. The only thing that you have to change is, to use a different key in your calculation of $C1$ and $C2$. Both keys may be derived from a common master key but they must not be the same.

Your solution is a bit complicated, though. It would be a lot easier, to just calculate your deterministic IV as a MAC of the plain text (and the additional data, if there is any).

Putting this together, my suggestion would be:

encrypt

Input value: $S$ (password), $M$ (message)

$MK = scrypt(password), K_1 = HKDF(MK, "IV Key"), K_2 = HKDF(MK, "Enc Key")$

$IV = MSB_{96}(HMAC(K_1, M)), C=ENC(K_2, IV, M)$

Return Value: $IV, C$

decrypt

Input value: $S$ (password), $C$, $IV$

$MK = scrypt(password), K = HKDF(MK, "Enc Key")$

$M = DEC(K, IV, C)$

Return Value: $M$