AES CBC with unique key per message, but fixed IV

Question

I'm working on a project with a scheme in which c[i] = AES-CBC-Encrypt(msg_key[i], IV, msg[i]), and two distinct plaintexts never have identical keys. IV is a string of nulls.

Random IVs are not an option because fully deterministic behavior is essential in this application. The only available sources of entropy (passphrase, id and msg[i] below) are used in key derivation, so no derived IV would be independent of the key. The value i is used for notational reasons only and is not available for cryptographic use, e.g. as a counter.

Keys are derived as follows:

passphrase = string chosen by user, constant for all messages

uuid = non-secret UUID, constant for all messages

msg[i] = plaintext of message i

root_key = PBKDF2(passphrase || uuid)

signing_key = HKDF(root_key, 0x01) # HKDF with extraction as in RFC 5869, IKM=root_key, salt=0x01, info="", L=chosen AES key length

text_id[i] = HMAC(signing_key, msg[i])

msg_key[i] = HKDF(root_key, text_id[i] || 0x02)

text_id[i] is known to recipients in another scheme beyond the scope of this question. The reason for deriving variable keys with a fixed non-secret IV instead of variable IVs for a fixed secret key is twofold:

1. Limit the amount of text encrypted with one key
2. Require knowledge of text_id[i] to decrypt any block of c[i] in addition to the passphrase. (The motivation for this comes from the system this scheme belongs to.)

It seems to me that this scheme addresses the major concerns I have seen raised regarding fixed IVs:

1. In order to produce an key collision in a chosen-plaintext attack, the adversary must find two messages that produce a collision in the HMAC function.

2. Two plaintexts with identical prefixes will not generate ciphertexts with matching or similar prefixes with any greater likelihood than two random plaintexts would.

Someone asked a similar question and got an answer that concerns me a bit: Why should I use an Initialization Vector (IV) when I have unique keys?

On the other hand, by not using a random IV, in some setups, one gives the adversary the same plaintext block enciphered with different keys (that would be the case if the first block of each plaintext is a known constant); this reduces the number of trial encryptions for exhaustive key search by a factor (at worse) equal to the number of different keys.

If I'm understanding this right, the concern is that if an attacker possesses N ciphertexts and knows that their plaintexts all start with a common prefix P at least one block in length, then the attacker can encrypt P under various keys until they duplicate the first block of one of the ciphertexts, at which point they will have discovered the key for that ciphertext. It seems like N needs to be quite large to make this practical, particularly for a 256-bit key.

But fixed IVs make me feel bad inside, and so I wanted to ask... what dangers might I be overlooking?

Answer 1

What you are describing is related to the synthetic initialization vector or SIV family of authenticated ciphers, where the cipher is a deterministic function of a key and a message without a separate initialization vector or nonce. Such ciphers cannot conceal repeated messages, but that is the only inherent flaw.

Some ciphers also admit specifying an IV or nonce, and if the nonce is always unique, then they work like standard nonce-based ciphers, but if the nonce is ever repeated, then they fall back to failing to conceal duplicates but nothing else—we call these nonce-misuse-resistant or NMR.

SIV or NMR ciphers are not very popular right now, partly because nobody agrees on which ones to use, and partly because the security bounds or data volume limits on the most common ones like AES-SIV and AES-GCM-SIV are not very good owing to the small block size of AES—indeed, the name ‘AES-GCM-SIV’ has undergone many revisions over the past couple years in attempts to improve the bounds, and its definition is still not standardized.

The general structure of (a) deriving a key or IV as a pseudorandom function of the message, and then (b) applying a standard cipher with the derived key or derived IV, is generally fairly safe as long as everything involved is large enough to have a low collision probability—if we're talking HMAC-SHA256 to derive an AES-256 key, that should be fine. The main difference between instances of this structure is cost. (Just make sure you don't reuse keys for multiple purposes. For example, if elsewhere you reveal the HMAC-SHA256 under signing_key of public messages, you might leak which public message you just encrypted.) If the cost of HMAC-SHA256 is acceptable to you and to your auditor, great!

What you describe is not exactly an SIV cipher because you derive the key rather than the IV as a pseudorandom function of the message. With ciphers like AES, this incurs a somewhat high cost per message, because AES has an expensive key schedule, which is why AES-SIV is more popular than a hypothetical ‘AES-SK’ with synthetic keys. In contrast, ciphers like ChaCha and Salsa20 have zero overhead to changing keys.

If I'm understanding this right, the concern is that if an attacker possesses N ciphertexts and knows that their plaintexts all start with a common prefix P at least one block in length, then the attacker can encrypt P under various keys until they duplicate the first block of one of the ciphertexts, at which point they will have discovered the key for that ciphertext. It seems like N needs to be quite large to make this practical, particularly for a 256-bit key.

The area*time cost (a good proxy for euros or joules) of a generic attack on a cipher with a $b$-bit key given $n$ ciphertexts is $2^b/n$, using Oechslin's rainbow tables to save hash evaluations, on a $p$-way parallel machine for $p \geq n^2$ to save memory and communication costs, which runs in the time of $2^b/np \leq 2^b/n^3$ sequential AES operations. This is why, for example, AES-128 should not be considered to provide a ‘128-bit security level’—if a billion users use the application (or, your users in aggregate make a billion ciphertexts under different keys using your synthetic key scheme), the cost of breaking one of them is well below $2^{100}$.

If $b = 256$ as for AES-256, it would take $2^{128}$ different targets before the cost drops below $2^{128}$. In other words, you don't have to worry about this. This is why, if you're aiming for a 128-bit security level, you should use ciphers with 256-bit keys like AES-256.

(Actually I don't recommend AES-256 either because it invites timing side channel attacks on software implementations, but if you must use AES you should use AES-256 instead of AES-128 unless you have an overwhelming performance consideration that can be carefully justified within your security goals.)