Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
Thank you for your help. –  Ricoz Jan 28 at 19:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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