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.


1 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.

  • $\begingroup$ So if the final block is <n it is padded with a 1 bit then zero bits to make up the rest of the block, which is then XORs against k2, but if the final block is =n it is XOR by k3, helping to remove the length attack defined by prime. But what by some stroke of good/bad luck beyond all infinitesimal chances, you end up with k2 and k3 being exactly identical. Your encryptions would be identical no matter what, how much of an impact on the security of the cipher would that result in? $\endgroup$
    – Anan
    Commented Sep 20, 2019 at 12:22
  • $\begingroup$ @Anan For random choice of $k_2,k_3$, it's very unlikely to happen that $k_2=k_3$ (I think on the order of $2^{-n}$). But if that were to happen, I think the 2-key insecurity you mentioned in your question would kick in. $\endgroup$
    – SEJPM
    Commented Sep 20, 2019 at 12:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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