# 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 retrieves $$K$$, then this is a certificational weakness of the underlying compression function? (we do not consider it in any specific 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 '14 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 '14 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 '14 at 10:40
• Can you reformulate your question using this notation? – Dmitry Khovratovich Jan 27 '14 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 '14 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\mathbin\|M_p\mathbin\|M') = F(T(M\mathbin\|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).