... pls read this message with the edits below... missing "^" in exp and the word "WITHOUT"...still no coffee...
David Wagner wrote: > Ed Gerck wrote: > >Wei Dai wrote: > >> No matter how good the MAC design is, it's internal collision probability > >> is bounded by the inverse of the size of its internal state space. > > > >Actually, for any two (different) messages the internal collision probability > >is bounded by the inverse of the SQUARE of the size of the internal state space. > > No, I think Wei Dai had it right. SHA1-HMAC has a 160-bit internal state. > If you fix two messages, the probability that they give an internal collision > is 1/2^160. > > Maybe you are thinking of the birthday paradox. If you have 2^80 messages, > then there is a good probability that some pair of them collide. But this > is the square root of the size of the internal state space. And again, Wei > Dai's point holds: the only way to reduce the likelihood of internal collisions > is to increase the internal state space. > > In short, I think Wei Dai has it 100% correct. Thanks again. I should have had some coffee at that time...I meant SQUARE ROOT. As to the point you say is in question: "the only way to reduce the likelihood of internal collisions is to increase the internal state space." -- this is clearly true but is NOT what is in discussion here. The point is whether the only way to reduce the likelihood of attacks based on MAC collisions is to increase the internal state space. These statements are not equivalent. > >Not really. You can prevent internal collision attacks, for example, by using > >the envelope method (e.g., HMAC) to set up the MAC message. > > This is not accurate. The original van Oorschot and Preneel paper > describes an internal collision attack on MD5 with the envelope method. > Please note also that HMAC is different from the envelope method, but > there are internal collision attacks on HMAC as well. Once again, I > think Wei Dai was 100% correct here, as well. However, it was possible to reduce the likelihood of attacks based on MAC collisions WITHOUT increasing the internal state space. This is what I was trying to explain. More below... > You might want to consider reading some of the literature on internal > collision attacks before continuing this discussion too much further. > Maybe all will become clear then. It's always good to read more, and learn more. But what I'm saying is written in many such papers, including some that are written for a general audience: --------------- To attack MD5 [for example], attackers can choose any set of messages and work on these offline on a dedicated computing facility to find a collision. Because attackers know the hash algorithm and the default IV, attackers can generate the hash code for each of the messages that attackers generate. However, when attacking HMAC, attackers cannot generate message/code pairs offline because attackers do not know K. Therefore, attackers must observe a sequence of messages generated by HMAC under the same key and perform the attack on these known messages. For a hash code length of 128 bits, this requires 2^64 observed blocks (2^73 bits) generated using the same key. ------------------in Dr. Dobbs, April 1999. The point is clear: WITHOUT increasing the internal search space of MD5, MD5 is used in a way that vastly reduces the likelihood of attacks based on MAC collisions. Cheers, Ed Gerck --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
