Showing a CBC-MAC is not preimage resistant with a proof

Question

So hypothetically I have a an arbitrary block cipher operating in CBC-MAC mode that makes use of a public and static $IV$ as well as a static key $K$.

I want to be able to that this won't be preimage resistant using a proof for an arbitrary single-block message $P$ that hashes to a given digest $T$. So far I've gotten as far as $$T = E(P \oplus IV, K)$$ $$D(T, K) = P \oplus IV$$ $$P = D(T, K) \oplus IV$$ I can't for the life of me figure out how to move from this to something that will show that the operation is not preimage resistant. As far as I understand if $K$ and $IV$ are fixed it should be computationally infeasible to find another $T_x$ such that $$D(T,K) \oplus IV = D(T_x, K) \oplus IV$$

Ideally I'd want to be able to extend this to show that for $P$ of any length I could find a $T_x$.

Answer 1

According to wikipedia's page on CBC-MAC:

If the block cipher used is secure (meaning that it is a pseudorandom permutation), then CBC-MAC is secure for fixed-length messages.[1] However, by itself, it is not secure for variable-length messages. Thus, any single key must only be used for messages of a fixed and known length.

Your case presents no such vulnerability, since you're hashing a fixed number of blocks ($1$, to be exact). If you were to compute the CBC-MAC of a variable-length message you could perform such a preimage attack.

Answer 2

If the problem statement can be read as $K$ being public, or a decryption oracle for the block cipher being available somewhere, then the reasonning in the question has solved it.

In the following I'll assume otherwise, and that the question really asks for a one-block preimage for arbitrary $T$. Further I'll assume availability a MAC-producing oracle, because that's a standard hypothesis when attacking a MAC.

The $D(T,K)=P \oplus IV$ equation shows that what's asked is equivalent to a decryption oracle for the block cipher. And it can similarly be shown that a MAC-producing oracle yields and encryption oracle.

For an arbitrary cipher, we can't turn an encryption oracle into a decryption oracle. Hence what's asked is proven impossible, even if a MAC-producing oracle is available. The correct answer is on the tune of: can't do, here's a bulletproof argument for why. More often than not that's the best option facing a student, and even more often a practitioner!