# MAC attacks without knowing the key

Attacks on a MAC that do not require the discovery of the key are possible. Consider the following MAC algorithm. Let $M=(X_1\mathbin\|\dots\mathbin\|X_m)$ be a message that is treated as a concatenation of 64-bit blocks $X_i$. Then define: $\Delta(M) = X_1 \oplus\dots\oplus X_m$ and $C_k(M) = E_k[\Delta(M)]$ where $\oplus$ is the exclusive-OR operation and encryption algorithm is DES in ECB mode. Thus the key length is 56 and the MAC length is 64 bits.

How would an attacker breach the system without knowing the encryption key?

• What research have you done on this problem? – Eugene Styer Apr 27 '18 at 17:06
• Well, this is the answer to this question. But I cannot understand anything about it. --> The opponent can attack the system by replacing X1|| . . . ||Xm−1 with any desired values Y1|| . . . ||Ym−1 and replacing Xm with Ym where Ym is calculated as follows: Ym = Y1 ⊕ || . . . || ⊕Ym−1 ⊕ ∆(M) The opponent can now concatenate the new message, which consists of Y1|| . . . ||Ym , with the original MAC to form a message that will be accepted as authentic by the receiver. With this tactic, any message of length 64 x (m 1) bits can be fraudulently inserted. – NextGen Engineer Apr 27 '18 at 17:09
• @NextGen Engineer: I edited the question to make it how it should have been. Hint: if $C_k(M)=C_k(N)$ then replacing message $M$ with message $N$ and leaving the MAC unchanged won't get caught, and counts as a success for an attacker (unless $N=M$). The attack considered has $N=(Y_1\mathbin\|\dots\mathbin\|Y_m)$. Use properties of $\oplus$ to explain why it works. – fgrieu Apr 27 '18 at 17:24
• @fgrieu: thank you for editing and for your answer. Could you be more explicit please. How the new messages XOR the previous delta(M) can provide the same MAC? Also, the MAC is encrypted. How can the attacker ensure that the MAC is correct? – NextGen Engineer Apr 27 '18 at 17:32
• @NextGen Engineer: apply the suggested $Y_m=Y_1 \oplus\dots\oplus Y_{m-1}\oplus\Delta(M)$, the definitions of $M$, $N$, $\Delta(M)$, $\Delta(N)$, and properties of $\oplus$ to conclude that $\Delta(M)=\Delta(N)$. Then apply the definitions of $C_k(M)$ and $C_k(N)$, and that $C_k$ is a function, to conclude that $C_k(M)=C_k(N)$. – fgrieu Apr 27 '18 at 18:16

One way to try tackling simpler problems like this is by writing them out as equations and doing algebra on them. In this case, let's take this statement from your comment with the answer:

The opponent can now concatenate the new message, which consists of $Y_1 || \dots || Y_m$ with the original MAC to form a message that will be accepted as authentic by the receiver.

So this is saying that the following equation is true:

$$C_k(Y_1 || \dots || Y_m) = C_k(X_1 || \dots || X_m)$$

But is it really true? One way we can test this is by using the laws of equations (like in algebra) to rewrite this one over and over and see if it has the same truth value as some other equation that we can independently tell is true.

By applying the definition of $C_k(M) = E_k(\Delta(M))$ to both sides of the first equation we get:

$$E_k(\Delta(Y_1 || \dots || Y_m)) = E_k(\Delta(X_1 || \dots || X_m))$$

And since the function $E_k$ is a block cipher, it has an inverse $D_k$, which by applying to both sides we can get this:

$$\Delta(Y_1 || \dots || Y_m) = \Delta(X_1 || \dots || X_m)$$

Applying the definition of $\Delta(M)$ to both sides we get:

$$Y_1 \oplus \dots \oplus Y_m = X_1 \oplus \dots \oplus X_m$$

So the attack that you've quoted in your comment hinges on the fact that it must somehow cause this equation to be true. Your comment explains the attack as this (I've corrected a notational error):

The opponent can attack the system by replacing $X_1 || \dots || X_{m-1}$ with any desired values $Y_1 || \dots || Y_{m-1}$ and replacing $X_m$ with $Y_m$ where $Y_m$ is calculated as follows: $Y_m = Y_1 \oplus \dots \oplus Y_{m−1} \oplus \Delta(M)$.

Let's try substituting that for $Y_m$ in the equation:

$$Y_1 \oplus \dots \oplus Y_{m-1} \oplus (Y_1 \oplus \dots \oplus Y_{m−1} \oplus \Delta(M)) = X_1 \oplus \dots \oplus X_m$$

XOR is an operation where every element is its own inverse, so $Y_i \oplus Y_i = 0$ which is the identity element. It's also an associative and commutative operation, so in the left side of this equation we can cancel out all of the $Y_i$ terms, and we get:

$$\Delta(M) = X_1 \oplus \dots \oplus X_m$$

Which is nothing other than the definition of $\Delta(M)$, which we were given as a premise. So the technique you cited is guaranteed to forge a message and its tag different from $M$. Worse, it allows the adversary to pick any values they like for $Y_1$ to $Y_{m-1}$.

The short, intuitive summary of that is that the problem with this MAC is that the way the $\Delta(M)$ it combines the plaintext message blocks with XOR gives the attacker way too much latitude. Given any message $M$, it's trivial for the attacker to compute $\Delta(M)$, as well as many, many ways that they can compute a message $M'$ such that $M ≠ M'$ but $\Delta(M) = \Delta(M')$. And since the MAC is just the deterministic encryption of $\Delta(M)$, that guarantees a successful forgery.

• Nitpick: There's a logical error in "And since the function $E_k$ is a block cipher, it has an inverse $D_k$, which by applying to both sides we can get this". Problem is, we are hypothesizing what we are trying to demonstrate (and applying $D_k$ on that). The right line of thought is to prove that $\Delta(Y_1\mathbin\|\dots\mathbin\|Y_m)=\Delta(X_1\mathbin\|\dots\mathbin\|X_m)$ and apply $E_k$ on both sides. This is not equivalent; in particular, it only requires $E_k$ to be a function, which is not required to be invertible (that would matter e.g. if $E_k$ ended in truncation). – fgrieu Apr 28 '18 at 9:46
• @fgrieu The question states that $E_k$ is DES in ECB mode, only called on block-sized inputs, and the tags are the same size as the DES blocks, which means there is an inverse. Your way is indeed more general and thus an improvement, but I do not see that I appealed to any premise not given in the problem. – Luis Casillas Apr 30 '18 at 18:42

The MAC scheme provides tag by encrypt the XOR of message blocks, which can be easily forged since you can do the XOR operation using the message along with the tag and then choose any other message which has a block being used to adjust the XOR value of the message to be the same as the XOR value of the original message.