CBC MAC that is using AES as the underlying block cipher, has tag space of 2^128. If we add a random single block, concatenating it with the tag, and encrypt it again in AES CBC mode, with additional key, we get a 256 bit tag of 256 bits space:

TAG = CBC_MAC(K2,CBC_MAC(K1,M)||r) || r

(where r is 128 bit random number) This is a randomized MAC generating tags in the space 2^256. In the same way we can easily generate tag in any size. Is there any standard that is using this method?


  • 2
    $\begingroup$ What problem are you trying to solve? If the "problem" is that someone can forge a CBC MAC tag with probability $2^{-128}$ by picking a random tag, well, your construction has the same probability. Also, see SOJPM's correct response. $\endgroup$ – poncho Apr 28 '15 at 18:55
  • $\begingroup$ Well, this construction does not have the same probability. The strength is the square root of the tag space, so here its 2^64. In the proposed construction the tag space is 2^256 and the strength is 2^128. As a matter of fact, using this method you can have any strength you want. And see my comment to SJM $\endgroup$ – Evgeni Vaknin Apr 29 '15 at 14:59
  • 2
    $\begingroup$ Actually, what your construction tries to get around is the "birthday bound" that most block cipher modes suffer after $2^{n/2}$ blocks; in the CBC-MAC case, what happens after $2^{n/2}$ generated tags is that you get a tag collision, that that allows the attacker to deduce the equality of two inner states. You can see that it's not actually related to tag length by considering AES CBC-MAC truncated to 64 bits -- the weakness you refer to will still occur only after $2^{64}$ tags (as a collision is interesting only if it happens over all 128 internal state bits) $\endgroup$ – poncho Apr 29 '15 at 19:00
  • $\begingroup$ Thanks for your comment. Nevertheless, I absolutely do not agree: Imagine, for instance, that the tag is truncated to 4 bits only. Clearly, the strength will be in the order of1/4, and not 2^-64. In addition, your first interpretation re my intention is almost correct: The TAG space in CMAC is 128, giving a strength of 64. My proposal can produce TAG at larger length (e.g. 512) with very minimal computation effort $\endgroup$ – Evgeni Vaknin Apr 30 '15 at 10:51

First, don't roll your own crypto.

Second, why would you want to use CBC-MAC, if you have GMAC (GCM-mode) and CMAC and even better HMAC? (all of which are better than CBC-MAC)

Third, don't try to fix problems that have been fixed. (see second)

Fourth, I'm not aware of this construction being standardized and I'd doubt it has been. (see points 1 to 3)

Fifth, in fact there's a proposal that is similar to yours. Look here

| improve this answer | |
  • $\begingroup$ Thanks for responding.Well, the same question is defeintely applicable to CMAC, and PMAC from any type, including GMC. The purpose is to enlarge the tag space with very little additional effort. With this method, you can enlarge the tage space as much as you want. So why do not use say HMAC that is based in SHA-256 for instance? Two reasons: CMAC and GCM MAC are faster to compute. And second, HMAC-256 has a constant tag size, while the above method allows variable TAG size, as desired, with parallel MAC performance, as in GMAC. I hope I answered all your questions. $\endgroup$ – Evgeni Vaknin Apr 30 '15 at 6:54

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.