# Attack on envelop mac

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.

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.