XCBC Authentication

Question

So XCBC was made to counteract lengths attacks against CBC-MAC, but how exactly does the modification made defeat this attack? All I can find are a few papers on why 2-key XCBC isn't actually secure.

Answer 1

How exactly does the modification made defeat this attack?

So first, let's quickly recap how XCBC works:

1. Receive a message $m$ and three keys $(k_1,k_2,k_3)$ with $k_1$ being the key for a block cipher (or a fixed-domain PRF) and $k_2,k_3$ being random strings of length $n$, the block cipher's block length (or the PRF's input length).
2. Split $m=m_1\mathbin\|\dotsb\mathbin\|m_\ell$ into blocks of size at most $n$ bits where only the last block has size ${\leq} n$.
3. If the last block has a length strictly shorter than $n$, pad it with a single 1 bit and zero bits, then XOR in $k_2$, else XOR $k_3$ into the last block.
4. Now apply standard CBC-MAC with the key being $k_1$ on the result of the third step.

---

The next thing to know is that CBC-MAC is a PRF (and thereby a secure MAC), if no valid input can be a strict prefix of another valid input, that is, it can never happen that CBC-MAC receives e.g. $m_1$ and $m_1\mathbin\|m_2$ as input.

Now the question is how the above padding achieves this prefix-free-encoding. It does so by exploiting the fact that you cannot possibly know $k_2$ nor $k_3$ and so you can't construct an intermediate block that is the same as a padded block. A quick example: Suppose you query the block $m_1$ which gets padded to $m_1\oplus k_2$ and then you query another message $m_1\mathbin\|m_2$ which gets padded to $m_1\mathbin\|(m_2\oplus k_2)$. Clearly $m_1\oplus k_2$ is not a prefix of $m_1\mathbin\|(m_2\oplus k_2)$. Furthermore to construct a prefix, you'd have to find $m_1\oplus k_2$ through trial-and-error (assuming the block-cipher / fixed-domain PRF is good) which is equivalent to correctly guessing $k_2$.

Also see "CBC MACs for Arbitrary-Length Messages: The Three-Key Constructions" by Black and Rogaway from 2000 for a more formal treatment of the above.