Is it possible to generate a message using the mac and the key?

Say that you have the Key and the MAC value that was generated from the Key using CBC. Is it possible to generate a message with just the mac and the key? If so, how would you do it?

-
By 'generate a message' do you mean construct a message whose MAC under key $k$ is your given MAC value? – pg1989 Sep 9 '13 at 1:02
– Ricky Demer Sep 9 '13 at 1:39
Take a look at this attack. Could you please clarify the terms of your question? As it stands it's a bit ambiguous. Do you mean what pg1989 is suggesting or is it something else? – rath Sep 9 '13 at 2:10
Actually the wikipedia article that you pointed out, answered my question. Thanks. And yes, pg1989 is correct, I meant construct. – mike Sep 10 '13 at 18:52
I think I spoke too soon. I don't quiet understand the wikipedia article. How does using the same key for the cbc-mac and the cbc a security compromise? Wouldn't block chaining change the mac if one of the plaintext was modified? – mike Sep 11 '13 at 3:55

This depends on the MAC algorithm.

Two examples:

With HMAC based on a secure hash function, no, there is no known way to construct a message fitting the MAC other than brute-forcing it. (If you want to find a specific message, like when you have a MAC of a message containing a password and some fixed text, brute-forcing the password might be quite feasible.)

With CMAC (a MAC-algorithm based on a block cipher), given the key and MAC value, it is usually quite easy to construct a fitting message, you even can chose all but one block of your message freely.

In general, MACs based on hash-functions are usually safe, MACs based on block ciphers not.

Have a look at the CMAC algorithm, assuming we have a full-length message (multiple of block size). In the image the length is 3 blocks.

             +-----+     +-----+     +-----+
| M_1 |     | M_2 |     | M_3 |
+-----+     +-----+     +-----+
|           |           |    +--+
|     +--->(+)    +--->(+)<--|K1|
|     |     |     |     |    +--+
+-----+  |  +-----+  |  +-----+
|AES_K|  |  |AES_K|  |  |AES_K|
+-----+  |  +-----+  |  +-----+
|     |     |     |     |
+-----+     +-----+     |
|
+-----+
|  T  |
+-----+


(Image modified from RFC 4493, page 5.)

Assume we know the key $K$ and the tag $T$, we did choose $M_1$ and $M_3$ arbitrarily and we now want to produce a message by finding a fitting $M_2$.

This is the formula:

$$T = E_K(E_K(E_K(M_1) \oplus M_2) \oplus M_3 \oplus K_1)$$

($K_1$ is derived from $K$.)

We can apply the decryption function on both sides:

$$D_K(T) = E_K(E_K(M_1) \oplus M_2) \oplus M_3 \oplus K_1$$

Next move the XORs over:

$$D_K(T) \oplus M_3 \oplus K_1 = E_K(E_K(M_1) \oplus M_2)$$

Apply decryption again:

$$D_K( D_K(T) \oplus M_3 \oplus K_1) = E_K(M_1) \oplus M_2$$

One more step:

$$D_K( D_K(T) \oplus M_3 \oplus K_1) \oplus E_K(M_1) = M_2$$

Of course this also works with more than three blocks and if the last block is not a full block (then we pad and XOR with another key $K_2$ at the end), as long as one block is free to choose according to the result.

The general idea is that we can move through our diagram from both sides (replacing encryption by decryption if going in the other direction) until we arrive at the one unknown block.

The moral is that a MAC with a known key doesn't give us a secure hash function, where such a result would count as a preimage-attack.

-
I don't understand, wouldn't changing the plaintext change the mac since the change propagates to the end? – mike Sep 11 '13 at 6:18
I added an example of how we can calculate the block. – Paŭlo Ebermann Sep 11 '13 at 20:43