On Tue, 22 Oct 2002, Wei Dai wrote:
>On Tue, Oct 22, 2002 at 11:09:41AM -0700, bear wrote: >> Reviewing his files, Bob >> finds that he has a January 21 document and a September 30 >> document which have the same MAC. >> >> What does Bob do now? How does this get Bob the ability to >> create something Alice didn't sign, but which has a valid MAC >> from Alice's key? > >Call the Jan 21 document x, and the Sept 30 document y. Now Bob knows >MAC_Alice(x | z) = MAC_Alice(y | z) for all z, because the internal states >of the MAC after processing x and y are the same and therefore will remain >equal given identical suffixes. So he can get a MAC on x | z and >it's also a valid MAC for y | z, which Alice didn't sign. This applies >for CBC-MAC, DMAC, HMAC, and any another MAC that is not randomized or >maintains state (for example a counter) from message to message. This is interesting, but there are two easy ways to prevent it: 1) First, it doesn't work unless the MAC algorithm is sequentially linear (ie, unless its internal state never depends on nonlinear interactions between earlier and later parts of the message). Sequential linearity, for this reason, seems like a very bad property for a MAC algorithm to have. 2) Second, it only works if the MAC generated discloses the *entire* internal state of the MAC algorithm -- which it should not, any more than any other pseudorandom number generated should disclose the entire internal state of the PRNG that generated it. The MAC algorithm should have *FAR* more internal state than the number of bits disclosed in the MAC. If the algorithm has N bits of internal state and the MAC is M bits where M < N, and the algorithm is secure, then the attacker cannot determine with a better than 1/((N-M)^2) probability that the MAC algorithm's internal state is in fact the same after each of two messages that generate identical MACs. And these are both very basic points, and ought to be easy things for MAC designers to avoid. So, if I found a MAC algorithm that were subject to the attack you describe, I would cheerfully toss it out with the morning trash as a Bad Idea. Bear --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]