2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dmitry Khovratovich Jan 26 '14 at 16:52
  • $\begingroup$ 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. $\endgroup$ – Ricoz Jan 26 '14 at 22:36
  • $\begingroup$ 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)$ $\endgroup$ – Dmitry Khovratovich Jan 27 '14 at 10:40
  • $\begingroup$ Can you reformulate your question using this notation? $\endgroup$ – Dmitry Khovratovich Jan 27 '14 at 10:40
  • 1
    $\begingroup$ 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? $\endgroup$ – Ricoz Jan 28 '14 at 4:07
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.