# Is it okay to have no IV when using AES-CBC with unique keys, that are however derived from one shared key?

Given $$\operatorname{AES-CBC}$$ (128-bit), with $$IV=0$$ and unique encryption keys $$K_{Enc} = \operatorname{CMAC}(MK, \text{known_text})$$ where $$MK$$ is a shared symmetric 128-bit key and $$\text{known_text}$$ would be some concatenation of a message counter and a device ID, that are transmitted in plain text. $$K_{Enc}$$ are by themselves unique keys, however, the CMAC algorithm and $$\text{known_text}$$ are known to the attacker. This answer says that if the first CBC block is known plaintext, the complexity of finding one unique key reduces by $$n$$, the number of intercepted messages (with unique keys).

• In this case, does this only make finding $$K_{Enc}$$ easier, or is $$MK$$ affected in the same way?

• Additionally, if $$MK$$ is also affected, is an attack with only the factor $$n$$ relevant?

• Considering there are $$2^{128}$$ possibilities for $$MK$$, wouldn't n have to be ridiculously large to make computing $$MK$$ feasible?

• CMAC is a provable PRF if the underlying block cipher is a PRF (or PRP) like AES (proof and bounds here as Corollary 5.1). Unique inputs to a PRF yield outputs that are indistinguishable from random. Using deterministic encryption is fine if you use a fresh key each time. However I couldn't (quickly) find a multi-user security analysis for CBC, so no answer (yet). – SEJPM Jul 4 '20 at 14:40
• I don't see how finding MK would be easier whatever amount of known input / output is known. The CMAC / PRF should offer enough protection. And since the keys used are only linked together by the PRF and MK, I don't see that they are being affected either. Of course, using CBC means that you can bugger up things in various other ways, especially when using it for transport security. – Maarten Bodewes Jul 4 '20 at 16:56
• The $n$ is the number of the known plaintext. That falls into multi target attack since there are $n$ targets. With known $n$ keys one also needs their corresponding known_text. In any case, as pointed it is PRF. Note that, after $2^{64}$ key generation you will get collisions with 50% probability. This is not negligible and one should stop way earlier... – kelalaka Jul 4 '20 at 20:40
• This simply tells the importance of the IV if one uses 128-bit block cipher. It is better to use 256 bit. – kelalaka Jul 4 '20 at 21:40
• @kelalaka To clarify: after $2^{64}$ key generations there is a chance of 50% that at least one collision happened, is this correct? If I stop after $2^{32}$ keys, then the chance for a collision should be negligible, and I would still have a security level of $128-32$ bits, for any single key, correct? – jschw Jul 5 '20 at 5:29