Security of this deterministic encryption scheme

Question

I recently came across a library that promises to do deterministic encryption with the following scheme:

AES with 256 bit key in CBC mode with PKCS7 padding and Synthetic Initialization vector taken from the first 16 bytes of the HMACSHA256 mac of the plaintext. I use the same key for confidentiality and integrity. Ciphertext is Base64Encode( MSB(128, mac(k, plaintext)) || E(iv, k, plaintext) ) where MSB(b, v) stands for the b most significant bits (left-most) of v.

My question is: does this scheme have any security flaws? How would it compare, for example, with using SIV mode as described in RFC 5297? Specifically, does it provide the same guarantee for message authentication and integrity?

Answer 1

Correctly implemented, it should be secure deterministic authenticated encryption. In fact, it is SIV, in the wider sense of using the "SIV construction" as defined in Deterministic Authenticated-Encryption by Rogaway and Shrimpton (except for lacking a header input). The proof of the security of the SIV construction is that:

We will now show that if $F$ is PRF-secure and $Π$ is IND\$-secure then $SIV[F, Π]$ is DAE-secure.

So in this case AES-CBC must be IND\$-secure and HMAC-SHA256 must be a secure PRF. With those assumptions, the mode as described is a secure deterministic authenticated encryption scheme.

Those are slightly stronger requirements than we usually use. HMAC-SHA256 is normally only required to be a secure MAC. Being a secure PRF implies it, but the converse is not implied. In practice there are other protocols that do rely on its PRF security and we have no indication that it would be insecure.

Caveat: the keys being the same actually invalidates the proof, so in the strict sense it is not proved secure. However, for key reuse between HMAC-SHA256 and AES to be exploitable would be an incredible coincidence.

---

Now, in practice there are some problems with the use of CBC mode. While it is provably secure, practical implementations have been known to be weak. Most relevant here is the padding oracle attack. There are ways to avoid it, but without looking at the source of the library I do not know if they are used:

1. Always verifying both padding and MAC in constant time avoids the side channel leak. The error returned must also be the same. This is difficult to ensure.

2. If the MAC is verified before the padding, the attack is not possible. I.e. the MAC is either over the ciphertext (not the case here) or over the padded message (possible here).

3. Ciphertext stealing avoids the need for padding. (Not used here.)

---

On the other hand, the choice of HMAC and CBC does also have some advantages. Namely, it breaks less badly as you get close to the birthday bound:

• CMAC is gets insecure after $2^{64}$ invocations, and is recommended to be only used for $2^{48}$ blocks (see SP 800-38B, appendix B).
• With CTR an IV (or block input) collision means subsequent blocks also collide. CBC usually only leaks individual, random blocks, which is potentially harder to exploit.