I'm having trouble understanding the rationale for the answer to exercise 3 in chapter 3:
What is the primary limitation of the use of a MAC or message digest?

The primary limitation of a MAC or message digest is the amount of data that it is safe to feed into it. The data limitation exists because, beyond a certain size, the likelihood of different data computing to the same digest or MAC value becomes too high.

My understanding of cryptographic hashes is that it is not feasible to find two another message with the same hash. I don't see what feeding a large message into it has to do with increasing the likelihood of a collision.

Can you expand on this, or perhaps provide some reference?

Andy Neilson

How feasible it is to find a collision with a hash depends on the current technology and current knowledge. Finding a collision which is useful in the sense that it can be used to fool someone is harder again. None of this makes it impossible though.

One way to think about hashes and MAC's is as one way compression functions. The main point being that if a MAC is 16 bits long and all your documents are 64k bytes long it should be clear that reducing the entire set of bit strings possible in 524288 bits to a set of bit strings that only has 65536 members will result in a number of collisions. One set is vastly larger than the other.

Regards,

David

I understand that many large messages result in the same hash. I still don't think there is a reasonable justification for characterizing this as the primary limitation of the use of a MAC or message digest.

I have difficulty with the idea that compression of large space of message into a smaller space is really an issue. Given that in reality, that the hash size is 160-512 bits (and not 16), the "smaller" space is still 2^160 to 2^512, which is still very large.

Assuming that you are using brute force in an attempt to find a collision (and you can use messages of any length), on average, you still need to try something like 2^80 to 2^256 hashes before finding a collision. It seems to me that the likelihood of a collision is so low that the size of data is not really an issue.

More to the point, my complaint about this exercise question is that it doesn't really relate to anything that you say in chapter 3.

Andy

Chapter 3 discusses digests, MACs, and HMACs.

As page 73 mentions MACs do not have to be the block size of the cipher to be useful, but the size of any MAC or HMAC, or a reduction in size for the sake of a protocol must be considered in terms of the size of the actual messages being passed through the system. This has nothing to do with the fact that a couple of message digest algorithms have a bit size of 160 bits or that there are ones with a block size of 512 bits. The question at the end of the chapter is to enforce the idea that choice of MAC, HMAC, or digest size needs to be thought about as it changes the collision profile for the underlying algorithm. It's one of the reasons digest like SHA-512 were invented.

This is done in practice - for example SHA-384 is a reduction on SHA-512. 16 and 32 bit MACs are often employed, even though the underlying cipher or digest may have an output size which is much larger.

All digests have a limit on the size of data that should be put into them. This isn't to say there are not other considerations, but the safe input size is the first one you encounter.

Regards,

David