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 Jul 4 '20 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 Jul 4 '20 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 Jul 4 '20 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 Jul 4 '20 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 Jul 5 '20 at 5:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.