Re: HMAC -NMAC security

From: Anton Stiglic (stiglic_at_cs.mcgill.ca)
Date: 07/02/03

  • Next message: John Schutkeker: "Re: Statistical Moments of Finite Bitstream" 
    Date: Wed, 2 Jul 2003 12:19:02 -0400

    "whoami" <whoami7878@yahoo.com> wrote in message
    news:9bd74c94.0307010034.56a84a30@posting.google.com...
    > > [..]
    > > >
    > > >
    > > > 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.
    > >
    >
    > Ok. Suppose that the size of the output of H is 160. This means that
    > the attacker needs to try 2^80 messages. Now in the HMAC case, if I
    > give the result of the inner function, how many trials does the
    > attacker needs to find a collision with good probability?

    If I have an oracle that takes as input any message m and always gives me
    the
    answer to the inner function calculation, i.e. H(Kinner, m), then I will
    need
    to send it about 2^80 messages in order to find (with good probability ) two
    different messages m1 and m2, such that H(Kinner, m1) = H(Kinner, m2).
    A collision in the inner hash computation will automatically translate into
    a
    collision in the whole HMAC calculation, since if H(Kinner, m1)=H(Kinner,
    m2),
    you also have that
       H(Koutter, H(Kinner, m1)) = H(Koutter, H(Kinner, m2))

    Same thing applies if I have an oracle that takes any message m and gives
    me the answer to the HMAC computation on m, i.e. H(Koutter, H(Kinner, m)).

    So I dont' think I understand Mark Wooding's last point:
    >* Keeping the intermediate value $H(K_2 \cat x)$ secret makes it
    > harder for an adversary to know whether he's found a collision.

    The way I see it, if there is a collision in the intermediate value, you'll
    see it in the whole HMAC value, so I don't see how not knowing the
    indermediate value makes things more difficult (except possibibly if you
    are trying to guess the key K).

    Note that the type of attack I described with the oracle is not of the type
    that
    you can do offline, see for example this post by David Wagner:
    http://groups.google.ca/groups?q=g:thl4072053967d&dq=&hl=en&lr=&ie=UTF-8&oe=UTF-8&selm=anl29h%2415rl%241%40agate.berkeley.edu

    --Anton

    --Anton

  • Next message: John Schutkeker: "Re: Statistical Moments of Finite Bitstream"

    Relevant Pages

    • Re: Hash Function problem
      ... It depends what do you call _fast_ hash function. ... I just want the risk of collision to be lower than, ... use the full 160 bits out of MD5 or SHA-1. ... decrease the input cardinality or raise hashcode output bits number. ...
      (comp.programming)
    • Re: MD5 To Be Considered Harmful Someday
      ... creating a HMAC-MD5 collision, ... variant of the HMAC design, where the payload is actually double-hashed ... HMAC-SHA1 is collision resistant in a way that HMAC-MD5 can't be. ... let me be the first to admit the HMAC attack is ...
      (sci.crypt)
    • Re: keys and counters
      ... how many times can the counter be incremented before there is a collision in the hash, that is what i am asking. ... A hash function operated in such a counter mode as you suggest does not have this property - if I can guess or discover the input to the first block then I will know all the other blocks. ... You might think that some attacks are unreasonable/infeasible but do you really know what is possible to the world's largest employer of mathematicians, who have had for many years the world's largest computer budget and unlimited access to 60 plus years of classified research or what is possible for any of the other multi-billion dollar "smaller" big brothers?. ...
      (sci.crypt)
    • Re: Question about tcp hash function tcp_hashfn()
      ... TCP implementation in Linux. ... efficient hash function. ... on the length of the collision list. ... at startup further reducing the size of collision lists. ...
      (Linux-Kernel)
    • Re: MD5 and SHA-0 collisions
      ... > I guess I was really asking whether there are any real systems that use ... Basically HMAC is being used as an indexable family of unkeyed hash ... it shouldn't be hard to prove that if H is collision ... resistant then HMAC-H is also collision resistant even if the key is ...
      (sci.crypt)
    • Quantcast