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?

  • 1
    $\begingroup$ 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). $\endgroup$
    – SEJPM
    Commented Jul 4, 2020 at 14:40
  • 1
    $\begingroup$ 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. $\endgroup$
    – Maarten Bodewes
    Commented Jul 4, 2020 at 16:56
  • $\begingroup$ 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... $\endgroup$
    – kelalaka
    Commented Jul 4, 2020 at 20:40
  • $\begingroup$ This simply tells the importance of the IV if one uses 128-bit block cipher. It is better to use 256 bit. $\endgroup$
    – kelalaka
    Commented Jul 4, 2020 at 21:40
  • $\begingroup$ @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? $\endgroup$
    – jschw
    Commented Jul 5, 2020 at 5:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.