# Adding a Random component to CBC MAC in order to enlarge the tag space

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?

Thanks

• 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. – poncho Apr 28 '15 at 18:55
• 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 – Evgeni Vaknin Apr 29 '15 at 14:59
• 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) – poncho Apr 29 '15 at 19:00
• 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 – Evgeni Vaknin Apr 30 '15 at 10:51