Updated Fri, 15 Jul 2022 18:50:04 GMT

Meet in the middle attack: Why would it be easier to get elements of one of the 2 sets?

This is from Bruce Schneier's Book Cryptography Engineering. In his description of Meet-in-the-Middle attack, he writes (Chap 2, Page 35)

A meet-in-the-middle attack is more flexible than a birthday attack. Lets look at it in a more abstract way. Suppose we have N possible values. The first set has P elements, the second has Q elements. There are PQ pairs of elements, and each pair has a chance of 1/N of matching. We expect a collision as soon as PQ/N is close to 1. The most efficient choice is P Q N. This is exactly the birthday bound again. The meet-in-the-middle attack provides extra flexibility. Sometimes it is easier to get elements for one of the sets than it is to get elements for the other set.

I don't understand the last line - why would it be easier to get elements for one of the sets? One of the sets is the set of transactions which you are snooping & the other set is the set of keys for which you have pre-computed the encrypted message for a header you expect at the start of the transaction. If this is right, then why would it be easier to get elements for one of the sets?


In many cases you are memory bound and you can't keep everything you compute in memory. So you can compute as much as fits in memory to get group A and then compute without storing in memory a potentially much larger group B. Checking for a collision is done efficiently because one group is in a hashset you have stored. The memory limit could be RAM limit so lookup is very fast but it could also be disk limit, you really can not store more data.