Complexity of deriving message from CMAC vs HMAC when the key is known

Question

From the description of CMAC and HMAC, given the key and the tag, I think it is easy to derive the CMAC message than the HMAC message.

After obtaining the key and tag for CMAC, an intruder can apply repeated decryption to get the blocks of the message until it represents a valid English text (assuming common case). For HMAC, it is difficult due to the brute force required to reverse the hash function?

Is my understanding valid?

Side note: Such reverse derivation of the message is important in the case of network protocol where parts of a message are sent with AES-CMAC function. The corresponding keys (nonces) are also revealed in the later exchange of messages.

Answer 1

Is my understanding valid?

It's close. I would put it this way: with CMAC, if you know the key and the CMAC output and know (have a guess) of the entire message except for a block (16 bytes for AES), it is easy to compute what that unknown block would have to be to make CMAC generate the observed output.

This doesn't apply to HMAC; there, they only thing you can do is test various messages, compute the HMAC of all of them, until you stumble across one with the observed output.

So, for CMAC, there are 16 fewer bytes of message you'll need to guess, and that makes it easier. And, if you have no constraints on what those unguessed bytes can be (that is, they're not "English text", but any arbitrary length 128 bit string), you can always quickly find a message with the expected CMAC.