Forgery of a custom MAC

Question

I'm trying to solve a problem that was given to me. The issue I have is that I'm missing some parts to solve it.

I'm confronted with an Oracle that performs MAC on an input that can be of any length using the following function. I need to forge a message that must match the message the Oracle has computed.

$o_1 = E(k, d_1)$
$o_2 = E(k, o_1 \oplus d_2)$
...
$o_N = E(k, o_{N-1} \oplus d_N)$

therefore $MAC(k, d) = o_1 \oplus o_2 \oplus ... \oplus o_N$

where $d_X$ are block size parts of the message (ex.: message is 32 bit long = 4 x 8-bit blocks).

In order to forge the message, the Oracle offers 2 methods:

$mac0(n)$ -> performs $MAC(k,msg)$ with msg = n x d (where d is a 8-bit block full of zeros and n is the number of block asked)

$mac3(input)$ -> performs $MAC(k, d)$ with any input (if the input is bigger than 3 blocks, it truncates it to 3 block; if smaller, it pads the remaining parts with zeros until the input is 3 blocks long).

In the case of the example I'll use an 32-bit long input (4 blocks).

The first thing that I currently do is that I use mac3 with the first blocks which will result in $o_3$. I, then, XOR $o_3$ with the last block ($d_4$) and send the result through $mac3$ again. When comparing with the actual result from the Oracle, I find that it is not equal.

So that's where I'm stuck.. According to what I understood, this might be due to the padding done by $mac3$ since the input is not 3 block long. This is the part I don't know how to solve. Would there be a way to revert the result to find the actual forged message?

Any other ideas?

Answer 1

Let's say $b$ is our block size. We can easily see that if the message has the size $b$, the following holds $MAC(k, d) = E(k, d)$. So, let's first try to solve this for a single block message (let's call it $p$).

One block message

The goal is to compute $E(k, p)$, because that is $MAC(k, p)$.

The message must go through $E$ at some point. The only function that can take the message is $mac3$ (in contrast, $mac0$ takes a number). The problem is that $mac3$ takes exactly 3 blocks of input. So, our one block message $p$ has to be expanded to a three block message in some way. If we put our message block at the beginning of the 3 blocks, the first invocation of $E$ would produce $o_1$ which will be mangled in the second and third invocation of $E$. We can't do that.

What happens if we put our message block $p$ at the end of the 3 block input to $mac3$? The $o_3$ which contains the encryption of our message block $p$ will only be XORed, but not encrypted again. There we have a winner, because it is easy to reverse XOR, since we don't need a key.

Let's recap the way XOR works: if $x \oplus y = z$ then $x \oplus z = y$. Also, $x \oplus x = 0$ and $x \oplus x \oplus y = y$. We're going to need it.

Back to our problem. We can control $o_3 = E(k, o_2 \oplus d_3)$ to be our MAC of our one block message if we can control $o_2$. This is where $mac0$ comes in.

What happens if we set the 3 block message to $0^b | 0^b | p$ where $|$ means concatenation and $x^b$ means to repeat $x$ $b$-times?

$o_1 = E(k, 0^b)$
$o_2 = E(k, o_1 \oplus 0^b) = E(k, o_1)$
$o_3 = E(k, o_2 \oplus p)$
$m = o_1 \oplus o_2 \oplus o_3$

We know that $o_1 = mac0(1)$, but that isn't enough to control $o_2$, because we don't know key $k$. What exactly is $mac0(2)$ then? ...

$o_{1,m2} = E(k, 0^b) = o_1$
$o_{2,m2} = E(k, o_{1,m2} \oplus 0^b) = E(k, o_{1,m2}) = o_2$
$m_{m2} = o_{1,m2} \oplus o_{2,m2} = o_1 \oplus o_2$

From that, we can calculate $o_2$:

$$o_2 = o_1 \oplus m_{m2} = mac0(1) \oplus mac0(2)$$

OK, now we control $o_2$. We still want to calculate $E(k, p)$. So let's set $d_3 = o_2 \oplus p$. This leads to

$$o_3 = E(k, o_2 \oplus d_3) = E(k, o_2 \oplus o_2 \oplus p) = E(k, p)$$

OK, now we're nearly there. The final MAC is $m = o_1 \oplus o_2 \oplus o_3$. Since we already know $o_1$ and $o_2$ from before, we have

$$m = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus p\right) \oplus mac0(2) = E(k, p)$$

Multi-block message

The last formula contains the way how $E(k, p)$ can be calculated for any single-block message $p$. This can be used to calculate the intermediate values $o_x$ if the composite message.

Let's say, our message is

$$d = d_1 | d_2 | ... | d_N$$

Then the final MAC can be calculated as

$o_1 = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus d_1\right) \oplus mac0(2)$
$o_2 = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus o_1 \oplus d_2\right) \oplus mac0(2)$
$...$
$o_N = mac3\left(0^{2b} | mac0(1) \oplus mac0(2) \oplus o_{N-1} \oplus d_N\right) \oplus mac0(2)$
$m = o_1 \oplus o_2 \oplus ... \oplus o_N$

Here is the (untested) Java code for this.