# Secret key model for a compression function cryptanalysis?

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)

-
The question is unclear. When one talks about a compression function, all the input variables can be chosen arbitrarily (or you may consider them as a large single variable). Hence recovering chaining value does not make sense, as the input is known. –  Dmitry Khovratovich Jan 26 at 16:52
I'm sorry if the question doesn't make sense as I'm trying to understand the accepted cryptanalytic models. So what you're saying is this cannot be considered as a preimage attack for the compression function, if I'm chossing the input messages and collecting the oracle's responses then recovering the used chaining value? Thanks in advance. –  Ricoz Jan 26 at 22:36
Consider a compression function $F(A,B) = C$. The hash function $H$ is defined as follows: let $A_0$ be constant, then $H(M_1||M_2||\ldots||M_n) = F(F(...F(F(F(A_0,M_1),M_2),M_3)...M_n)$ –  Dmitry Khovratovich Jan 27 at 10:40
Can you reformulate your question using this notation? –  Dmitry Khovratovich Jan 27 at 10:40
Consider the hash function $H$ and its compression function $F(IV,M)$ are used in a secret IV MAC scheme where the Tag $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? –  Ricoz Jan 28 at 4:07

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).