# Deterministic Authenticated Encryption with AES-OFB and HMAC

I have an encrypted column in a database that stores sensitive information. The existing encryption scheme is deterministic and a database index exists on the encrypted value to allow searching.

I am upgrading the encryption scheme to use authenticated encryption, so the obvious choice seems to be AES-SIV. However, the data is accessed both from a Java app and from PL/SQL stored procedures so I am limited to the cryptographic primitives supported by Oracle's DBMS_CRYPTO package (SIV is not supported).

I read several questions on this site, mainly Why is synthetic IV (SIV) mode considered deterministic authenticated encryption (DAE)? and Is it okay to use an HMAC of the plaintext and a (possibly distinct) key as the IV for symmetric cryptography? and I have come up with the following design:

• Use a 64 byte key, where there first 32 bytes are the HMAC key and the remaining 32 bytes are the AES cipher key.
• Use HMAC-SHA512 on the plaintext to generate a the initialisation vector (use first 16 bytes only).
• Encrypt using AES in OFB mode (since CTR mode is not available). OFB mode will preserve length and (I believe) avoid padding oracle attacks.
• Concatenate the 16 byte IV and the ciphertext in the database column.

My questions are:

1. Does this design provide deterministic authenticated encryption?
2. Is there a better design that would allow searching on the encrypted data?
• Regarding point 2: What kind of searching do you want to do? Please keep in mind the possible attacks described in blog.cryptographyengineering.com/2019/02/11/… and remember that allowing searches on encrypted databases could open it up to attacks. – rlee827 Mar 29 '19 at 1:45
• Also are you stuck using that particular cryptography library? They still support MD5 and (3)DES, which makes me think that it is quite dated and that other libraries may be better. – rlee827 Mar 29 '19 at 1:48
• @rlee827 thanks for the linked article. I only need exact-match searching so if I understand correctly, the range-based attacks in the article and associated paper don't apply. I can use any standard Oracle database feature, and I believe the DBMS_CRYPTO package is the only one offering modern (ish) crypto support. – Nathan Mar 31 '19 at 22:12

1. Does this design provide deterministic authenticated encryption?

This provides reasonable security as long as you limit the total volume of data encrypted to well below $$2^{64}$$ bytes.

Details. The SIV theorem[1], roughly, is that if $$F_{k_1}$$ is a $$t$$-bit PRF, with PRF distinguisher advantage bounded by $$\varepsilon_F$$, and if $$E_{k_2}$$ is a randomized cipher, with CPA distinguisher advantage bounded by $$\varepsilon_E$$, then $$m \mapsto F_{k_1}(m) \mathbin\| E_{k_2}(F_{k_1}(m), m)$$ with decryption $$t \mathbin\| c \mapsto \begin{cases} m, & \text{if F_{k_1}(m) = t;} \\ \bot, & \text{otherwise,} \end{cases} \quad \text{where m = E_{k_2}^{-1}(t, c),}$$ is a deterministic authenticated cipher with distinguisher/forgery advantage bounded by $$\varepsilon_F + \varepsilon_E + q^2/2^t$$ for any adversary making at most $$q$$ queries to $$E$$ or $$F$$.

• Under standard conjectures about SHA-512, the PRF advantage of a $$q$$-query cost-limited adversary against a 128-bit truncation of HMAC-SHA512 with a 512-bit key is bounded by about $$q/2^{128}$$.
• Under standard conjectures about AES, the IND-CPA advantage of a $$q$$-query cost-limited adversary against AES-OFB with a 256-bit key and messages up to $$\ell$$ blocks long is bounded by
• $$q^2 \ell^2/2^{128}$$, if the IVs are unique, and therefore
• $$q^2/2^{128} + q^2 \ell^2/2^{128}$$, if the IVs are chosen uniformly at random, as SIV hypothesizes.

Summing up, the adversary's advantage is bounded by about $$\frac{q}{2^{128}} + \frac{q^2 \ell^2}{2^{128}} + \frac{q^2}{2^{128}} + \frac{q^2}{2^{128}} = \frac{q + 2 q^2 + q^2 \ell^2}{2^{128}}.$$

I say ‘about’, because this excludes the probability of guessing $$k_1$$ and $$k_2$$, which, if they are 256 bits, is minuscule in comparison even in a multi-target attack on $$2^{64}$$ users; and this excludes the probability of an internal collision in HMAC-SHA512, which is also minuscule in comparison. The dominating term $$q^2 \ell^2$$ is the total number of blocks encrypted. Hence: keep the total volume of data encrypted well below $$2^{64}$$ bytes. A limit of a few gigabytes should be fine.

The real SIV, as presented in the paper and standardized with CTR mode, also handles associated data with a custom tuple PRF construction, instantiated with AES. The custom tuple PRF doesn't matter if you don't have associated data, and the instantiation with a PRP like AES instead of a PRF like HMAC actually hurts security a little (by the standard PRP/PRF switching lemma).

1. Is there a better design that would allow searching on the encrypted data?

This looks to me like the easiest secure option with the tools you have at hand.

You could derive a fresh AES key for each message, and cut it down from 64 bytes of key material to 32 bytes of key material, but there's a cost—switching AES keys is more expensive than switching AES-OFB IVs, and you'd have to call HMAC-SHA512 twice or something—and there's no benefit to security unless you expand the tag from 128 bits to 192 or 256 bits.