Attack on envelop mac

Question

As I am reading the Paper: MDx-MAC and building fast MACs from hash functions

I am having trouble understanding the Attack on the Envelope Method (4.3). In particular, I am not sure what chaining variables are referring to and what Prerequisites have to be met in order to execute the attack.

Maybe a more detailed/ rephrased explanation could help me to understand the gist of the attack.

Answer 1

The MAC under attack is built from a hash $h$ (assumed to process a hashed message by splitting it in blocks processed only once, as most hashes do), with a key split into $K_1$ and $K_2$ of equal size. It computes the MAC of a message $x$ as $$\operatorname{MAC}_{K_1\mathbin\|K_2}(x)=h(K_1\mathbin\|x\mathbin\|K_2)$$

The attack in the paper recovers $K_1$ and $K_2$ from an oracle accepting to compute the MAC, in 3 steps

1. We make online queries to the oracle until we find $x$ and $x'$ with the same MAC, and such that this occurs due to a hash state collision before $K_2$ is hashed. The later condition is testable by a few extra queries to the oracle. It is chosen $x=x_1\mathbin\|x_2$ with a hash block frontier between $x_1$ and $x_2$, with $x_1$ large enough to find a collision, and $x_2$ used to test for a hash collision before the frontier, per the criteria that if $h(K_1\mathbin\|x_1\mathbin\|x_2\mathbin\|K_2)=h(K_1\mathbin\|x_1'\mathbin\|x_2\mathbin\|K_2)$ for a few distinct values of $x_2$, then most likely there was a hash state collision before the frontier.
2. We find $K_1$ by offline exhaustive search, with the selection criteria that $h(K_1\mathbin\|x)=h(K_1\mathbin\|x')$ (changing $x_2$ and/or using a second collision similar to that in 1 to weed out false positives).
3. We find $K_2$ by offline exhaustive search, with the selection criteria of computing the correct MAC for a few examples kept from step 1.

For a hash with $s$ bits of internal state at block boundaries and a key of $k$ bits, step 1 costs $\mathcal O(2^{s/2})$ oracle queries, and steps 2/3 costs $\mathcal O(2^{k/2})$ hash computations. Truncating the MAC width to a fraction of $s$ increases the attack cost, but does not change these asymptotics.

The attack is practical if $s=64$, $k=128$, and it can be made $2^{32}$ oracle queries.