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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.