How does the Meet-in-the-Middle attack work?

Asked

Viewed 610 times

7

I was looking for the old 3DES and decided to search because there is no 2DES, I found little information, even because it did not "exist" in fact 2DES.

Although abbreviated also as MITM, it has no relation to the Man-in-the-Middle, commonly abbreviated in the same way, so I sought it is applicable whenever it is done:

E(K, E(K, M))

That is why 3DES uses the format at least the format of E(K1, D(K2, E(K1, M))), using at least two keys (K1 and K2) 56-bit, you can also use three different keys. However, searching for it would still be vulnerable to this Meet-in-the-Middle, but at a higher cost than "2DES", which would at the time be safe enough.

whereas E is encryption, D is decryption, K be key, M be the message.

After all, what is Meet-in-the-Middle?

cryptography
  • 2

    Dahora, man. I love to see that kind of question around here.

1 answer

3


The math behind the attack is more complex than what I’m going for here in the answer, but the principle on which it’s based is simple.

Algorithms such as "Double DES" and Triple DES have multiple encryption steps, with distinct keys. This increases security because the criminal element who wants to break your encryption has to brutalize more than one key.

Let’s make a simple account: if they exist n keys in a single step, I have to test n possible combinations to break a key in brute force. But if there are n keys in a step and m in another, my effort is to test n * m combinations, which can be a much larger number.

Only mathematically, if we call:

  • the original data of D;
  • the encrypted data of C;
  • the ENC encryption function;
  • the decryption function of DEC;
  • and the used keys of m and n;

We have to:

C = ENCm(ENCn(D))

The trickiness is in using algebra to play with the above equation:

DECm(C) = DECm(ENCm(ENCn(D)))
(first equation, decrypt both sides with m)

And right after:

DECm(C) = ENCn(D)
(Cuts an encryption with m followed by a decryption with m on the right side)

Did it make sense so far? You don’t need to test m * n combinations, you just need to test m + n... Which is much smaller. In fact, the more m and n grow, the greater the difference between the two forms.

If you haven’t noticed, remember, you don’t need to understand the result of the encryption/intermediate decryption to know that a key pair worked ;)

I don’t have to tell you what happens if the same key is used in both stages, right? D

And that’s why the name of the attack is rendezvous in the middle. You attack the algorithm on one side (with the cipher) and the other (with the original data), and in the middle you find the treasure.

Now you can say "ah, but the attacker may not have my original data, after all I encrypted it". Well, this is a use case. But think of the case where the attacker gets a sample of plain text and the result of encryption with his keys. He can now guess the keys and decrypt everything else you’ve encrypted with those keys.

And finally, that’s why the industry went straight from des to des triple. When they were about to make a new algorithm they realized that the double DES would be very vulnerable to this type of attack. So is the triple, but it’s less vulnerable (add another encryption step) - to the point that it’s been accepted for a while as a good standard. I don’t know how you are today.

Credit where credit is due, I pulled a lot of information from wikipdia.

Browser other questions tagged cryptography

You are not signed in. Login or sign up in order to post.