Re: HMAC -NMAC security

From: Anton Stiglic (stiglic_at_cs.mcgill.ca)
Date: 06/30/03 

Date: Mon, 30 Jun 2003 12:15:46 -0400

"whoami" <whoami7878@yahoo.com> wrote in message
news:9bd74c94.0306300706.69d61c0f@posting.google.com...
> mdw@nsict.org (Mark Wooding) wrote in message
news:<slrnbg05it.18j.mdw@tux.nsict.org>...

[..]
> * Keeping the intermediate value $H(K_2 \cat x)$ secret makes it
> > harder for an adversary to know whether he's found a collision.
> > -- [mdw]
>
>
> What hard means here? How easy is finding a collision for this inner
> function? Is there any papers explaining the number of trials needed
> to find a collision for hash functions and in particular this inner
> function?

It all depends on what you assume about the hash function H. If you
assume that H(k, .), for a random k, defines a random oracle, then the
birthday paradox will tell you that (with good probability) you should
get your first collision after trying sqrt(size_output_of_H) inputs.

In the HMAC paper, they actually assume that H(k, .) is weakly collision
resistant and that the compression function of H is a good fixed-length
input MAC, and prove the security of NMAC in relation to these
assumptions.

--Anton

Relevant Pages