1
$\begingroup$

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. Let’s 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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.