Cryptography
meet-in-the-middle-attack
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?

## Solution

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.