How do we analyze the security of a compression function in the secret key model? More formally, let $H$ be a hash function and $F(IV,M)$ its compression function. Suppose we generate a MAC as follows $$ T=F(F(K,M),M_p), $$ where $K$ is the MAC key and $M_p$ is the padded block. Can I say that if one observes the output of the inner compression function call i.e., $F(K,M)$ and retrieve $K$, then this is a certificational weekness of the underlying compression function? (we do not consider it in a certain protocol)
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Yes, if $K$ can be recovered from $H'=F(K,M)$, this is a weakness. The function $F$ is not preimage-resistant, and an attacker may easily generate correct tags for new messages (this is called a forgery). The proposed MAC scheme, however, is terribly weak, and forged tags for other messages can be easily produced (length-extension property): $$ T(M||M_p||M') = F(T(M||M_p),M'). $$ Still, if original $K$ can be recovered, forged tags can be produced for even shorter messages.
However, there could be many $K$'s that produce the same $H'$. If the cost of finding the original $K$ is still higher than the exhaustive search, then such attack is useless for forgery, as the attacker would have to use the length-extension attack. However, the compression function is still vulnerable to preimage attacks, which may be exploited in other constructions (for example, meet-in-the-middle attacks on hash functions).