# Rate the security of the following MAC

Ok we know when we add a random IV in our "modified encrypted" MAC became useless and the IV can be forgery, then our encryption scheme becomes vulnerable to chosen plaintext attacks.

According those proves :

Finding IV for forgery of AES CBC-MAC with non-fixed IV

CBC-MAC insecure with random IV

But the addition at the last step of a new IV2, make any change?. Supposed NO, but how can prove it.

*The length of the IVs or Plaintexts at the scheme, does not state the length, the IVs or Plaintexts Can be Variables Or Fixed.

*We agree that all the IVs are public.

• Can you rate the security of the following MAC, where the IV and IV2 values are Random with fixed length with fixed message length?.

• Can you rate the security of the following MAC, where the IV and IV2 values are Random with variable length with variable message length?.

• Can you rate the security of the following MAC, where the IV and IV2 values are Random with fixed length with variable message length?.

• Can you rate the security of the following MAC, where the IV and IV2 values are Random with variable length with fixed message length?.

Under what conditions can this structure be considered safe with random length IVs?.

• Hi, those schemes are not encryption and rather MAC. The goal is to prevent from forging a new tag. In fact, the IV of the first construction should be fixed. With this context can you see issues with both constructions? Commented Dec 7, 2023 at 8:16
• Re-updated for version 12 of the question: Please fix the Q! 0) What's that notion of IV with variable, even random length?! The drawing implies IVs are as wide as the block cipher's message block, therefore IVs are fixed width/length. Accordingly remove any of the new sub-questions with variable width/length IV. 1) Tell if IVs are fixed and public; or vary in value with each MAC (as in the links); or if that's left to discuss. 2) The first sentence is hard to get; e.g. the drawing is not for an "encryption scheme".
– fgrieu
Commented Dec 7, 2023 at 8:57
• Hints: If the assignment does not tell if IVs are fixed or not, then my guess is that you are supposed to discuss that first! Then I recommend discussing the attack if the block with Key 2 is removed and plaintext size is variable; and explain how Key 2 fixes that; then discuss what theoretical attack remains e.g. with DES the block cipher. Finally, can you prove that any attack that works against the scheme without IV2 can be adapted to the scheme with IV2 ?
– fgrieu
Commented Dec 10, 2023 at 20:57
• 1) The Keys is random so they are not fixed... Commented Dec 11, 2023 at 8:41
• 2) If we suppose that the 2nd Key is removed.... then a forgery attack in the MAC will be easy with random IV not 0. After the addition of the 2nd Key the scheme could be secure if the IV is 0 but not with random IV(the links above's is the supposed forge attack at the IV) the attack will be the same as the above links.....But the addition of the IV2 could improve anything, can we manipulate that IV(2) if it is at the last block?. You will tell me if we can manipulate the first IV then the scheme is broken, but if we cant manipulate the IV(2) then we can save things. Am i right?. Commented Dec 11, 2023 at 8:51

The question is about a MAC built from a block cipher, which we assume has a fixed-size block, and XOR of blocks. This implies that any IV(s) are the same size as a block, as in the drawing. Thus we must ignore everything about variable or random-size IV that popped in the question between it's revisions 4 and 5.

In a Message Authentication Code scheme, the same algorithm is used by sender to compute a bitstring called the MAC (or tag) from message and key, and by the verifier to recompute a MAC from received message and key (with the recomputed MAC compared to the received MAC to decide if the received message is accepted or not). Adversaries knowing everything of the method except Key(s), thus including IVs, and allowed to get examples of (Message, MAC) pairs possibly including for messages of their choice, are trying to make a (Message', MAC') pair with new Message' that passes verification, with probability sizably better than supplying a random MAC. Unless otherwise stated, messages are assumed to be variable size (though in the drawing, that size much be a multiple of the block size).

If either of IV and IV2 in the question's drawing are changed randomly at each message (as considered in some of the variants of the questions and comments), then the IV(s) that can change must be transmitted along the value labeled "Tag" in the drawing, or made part of the MAC (at the expense of not having quite the same algorithm for the verifier). Argument: without both IVs, the verifier would be unable to recompute the right "Tag". Therefore, we have to assume that adversaries, which already are assumed to be able to change the message and the MAC, are able to change the variable IV(s) too.

It's easy to show that in this case, a simple attack breaks the security of the MAC. The links in the question are about that. Specifically: with a random IV part of the MAC, given a single example of (Message, MAC) pair, it's possible to make another (Message', MAC') pair that passes verification, with Message ≠ Message'. When that attack is identified, it's easy to see that the addition of random IV2 (if part of the MAC) only worsen things.

Thus it's essential for security that both IV(s) in the drawing are fixed (or equivalently, transmitted by some channel secure against alteration; or determined from the message; but nothing in the question suggests either, so I won't consider these non-standard hypothesis any more). Further, the standard definition of a MAC scheme is with any IV that it might use fixed and public.

Assuming fixed and public IVs from now, here are a few things that can be shown:

• With removal of the block with Key 2 (or if Key 2 equals Key 1), and variable message size, there's a computationally easy attack on the MAC. The addition of an independent Key 2 (as in the drawing), or replacing the last block using Key 1 by one with Key 2 different from Key 1, or fixing the message size, or including the message size in the first message block, are four common methods to prevent that easy attack.
• In the drawing's configuration, there's a Meet-in-the-Middle attack recovering the $$k$$-bit MAC key formed by Key 1 ∥ Key 2 (each $$k/2$$-bit), with cost $$\mathcal O(2^{k/2})$$ block cipher evaluations and a lot of memory (with some time vs memory tradeoffs possible). A common method to prevent that attack for most practical purposes is the addition of an additional block with Key 1 after the one with Key 2, as in Retail MAC (aka Enhanced Security DES MAC, rMAC, ISO/IEC 9797-1 MAC Algorithm 3).
• There's another attack requiring $$\mathcal O(2^{b/2})$$ queries to a device computing and disclosing the MAC given a message, where $$b$$ is the bit width of the block cipher; and $$\mathcal O(2^{k/2})$$ block cipher computations to recover Key 1 then Key 2. That attack can in practice be more efficient than MitM, if only because it uses much less memory. Also it works including with the aforementioned countermeasure against MitM. To prevent that attack we want to make it impossible that adversaries get any near $$2^{b/2}$$ MACs, by choosing a block cipher with large block size, or (including and) a block cipher with a large key (AES-128 leads to $$b=128$$ and $$k=256$$, which is fine in both regards for most applications); or, as a fallback, counting and limiting the MACs generated, or slowing MAC generation to the same effect.

For all attacks in that second part of the answer, the addition of one or two fixed public IVs chosen randomly does not help. I suggest to show that any attack that works against the scheme without IVs can be adapted to work against the scheme with IVs. That holds for IV and IV2 independently.

Combined with the fact that it's the IVs that allow attack in the first part, that's probably why the many variants of CBC-MAC generally do without IV at all, or use an all-zero IV.

• This answer does not give all the details, because the question is likely homework.
– fgrieu
Commented Dec 11, 2023 at 12:51
• Thank you verry much for you answer. I appreciate it. Commented Dec 12, 2023 at 18:07

IV1, IV2: are randomly selected and public. The only way to attack to the scheme is to create a message that has got the same tag. It is impossible to create new tag. To do that in one way I have to break in the block cipher. So the question is how can I change the message to create the some tag? The f(k’,.) must have the same entry, such as the f(k,.), so the only thing that I can change is the IV, which is public. As we can see on the above scheme we have to XOR an IV’, IV2 and the message Dq = m But IV’ = IV ⊕ D ⊕D0

On the f(k,.) entry: IV’ ⊕ m ⊕IV2 = IV ⊕ D ⊕D0 ⊕ m ⊕IV2 = IV ⊕ Dq ⊕D0 ⊕ Dq ⊕IV2 = IV ⊕D0 ⊕IV2.

D0 cannot be changed. So if I choose an IV2 such as when IV ⊕IV2 = IV. For that IV2 must be zeros. e.g. IV = 11011001 IV2 = 00000000 ⊕

      11011001


So the above MAC, where the IV1 and IV2 values are randomly selected, is not secure.