4
$\begingroup$

I was doing some self-initiated knowledge gathering about digests, signatures and hmacs and I ran across the fact that you can use CBC as a MAC, but if the message size is not fixed; then it is not secure.

In layman's terms why is this so? Lets say that Johnnyboy has sent a message to QueenElizabeth such that a being the MAC and m being message (m consists of three blocks). If an adversary saw the transmission, the data would look like $(a,m)$ in this particular instance.

The adversary would not know the key used in the CBC-MAC algorithm (it is still unknown), but it is known that the tag which is $a$, message $m$ and the number of blocks.

How could the adversary generate another valid MAC value $a'$ for $m'$ if $m'=m_1||m_2||m_3||m_1 \oplus a||m_2||m_3$ without knowing $K$? and how would fixed length solve this?

From what I understand, all you need to do is take $m_1 \oplus a \oplus a$ which would result in $x_1$ then concatenating the rest - $m_2 || m_3$ - would result in $a' == a$ because the last block would be the same as the output from $m_1.

Lastly, to prevent this attack, the application or system receiving the transmission should check for a specific sized message in order to prevent this existential attack, but I am also guessing this is only secure when message blocks == 1?

Improve this question
$\endgroup$
2
  • $\begingroup$ The title of the question looks wrong to me; nearest logical substitute: How can CBC-MAC be secure only when message length is fixed? $\endgroup$
    – fgrieu ♦
    Nov 14, 2014 at 8:42
  • $\begingroup$ I put the mathematical parts in mathematical notation, but I think you're missing some parentheses in your 4th paragraph, the XOR must be over an equal sized value. Could you have a look? $\endgroup$
    – Maarten Bodewes ♦
    Nov 14, 2014 at 11:53

1 Answer 1

Reset to default
7
$\begingroup$

What you think of is called an extension attack and it turns out that this is the way to go if you would like to break the general CBC-MAC when the message length is not fixed.

All that an adversary needs to do is to mount a chosen message attack. Suppose he asks for the tag on the message $m=m_1||m_2||...||m_l$. The resulting CBC MAC would be $MAC_k(m)=t$. But now the adversary can easily find another message with a valid tag by extending his original message $m$ by $m_1\oplus t||m_2||...||m_l$. By looking at the CBC-MAC construction its easy to see that the tag on the new message $m'=(m||m_1\oplus t||m_2||...||m_l)$ is also $t$, what is in fact an existential forgery.

This is a reason why the CBC MAC is just secure when the message length is fixed. The detailed security analysis of CBC MAC and some work arounds for the case where the message length is not fixed can be found in this paper:

  • Mihir Bellare, Joe Kilian, Phillip Rogaway, The Security of the Cipher Block Chaining Message Authentication Code, Journal of Computer and System Sciences, Volume 61, Issue 3, December 2000, Pages 362-399 http://dx.doi.org/10.1006/jcss.1999.1694.
Improve this answer
$\endgroup$
5
  • $\begingroup$ Interesting, but the adversary does not know the key used for the MAC, so he/she is appending onto the original message m1⊕t||m2||...||ml where the m1⊕t essentially removes the requirement to know the key and because CBC-MAC only uses the last block to calculate t, ⊕t||m2||...||ml would make t' == t? $\endgroup$
    – mcdoomington
    Nov 14, 2014 at 15:34
  • $\begingroup$ Even if message lengths were set, would this make any difference if the number of blocks are greater than 1? $\endgroup$
    – mcdoomington
    Nov 14, 2014 at 16:07
  • $\begingroup$ @mcdoomington regarding your first comment. You're rigth, the adversary doesn't need to know the key in order to mount an extension attack, he just needs to cancel the $t$ out and append the message again. Regarding your second comment, I'm sorry but i don't know what you mean. If the message length is fixed, you're no longer able to mount an extension attack. $\endgroup$
    – rob
    Nov 14, 2014 at 16:23
  • $\begingroup$ I was thinking that the because CBC-MAC chains the messages together to create a tag, then if the message length was fixed, could an attacker alter the previous messages (m1 if we are still using 3 blocks) and manage to get a valid tag? Or is this not valid because of the chaining/concatenation process? $\endgroup$
    – mcdoomington
    Nov 14, 2014 at 18:09
  • $\begingroup$ @mcdoomington: If the message length is fixed, you're not able to change a message block and obtain a valid tag, because you can not compute the output of the underlying blockcipher. $\endgroup$
    – rob
    Nov 14, 2014 at 18:17

Your Answer

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

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