How does the meet-in-the-middle attack work?

Question

How does the meet-in-the-middle attack work?

Navigation

#1 by (3 votes)

7

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

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

E(K, E(K, M))

Therefore, 3DES uses the format at least the E(K1, D(K2, E(K1, M))) format, using at least two 56-bit keys ( K1 and K2 ), you can also use three different keys. But researching it would still be vulnerable to this Meet-in-the-middle attack, but at a higher cost than "2DES", which would make it safe enough at the time.

Considering that E is encryption, D is decryption, K is key, M is message.

After all, what is meet-in-the-middle?

criptografia

asked by anonymous 31.07.2017 / 22:15

1 answer

How to integrate Jest and Flow How to create loop to issue an event in socket.io?

score 3 · Accepted Answer

The mathematics behind the attack is more complex than what I am here in the answer, but the principle on which it is based is simple.

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

Let's do a simple account: if there are n keys in a single step, I have to test n combinations possible to break a key in brute force. But if there are n keys in one step and m in another, my effort is to test combinations n , 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 DEC decryption function;
and the used keys of m and n ;

We have to:

The trick is to use algebra to play with the equation above:

(C) = DEC m (ENC m Home (first equation, decrypts both sides with m)

And right away:

DEC m (C) = ENC n (D)
(Cut an encryption with m followed by a decryption with m on the right side)

Did it make sense so far? You do not need to test 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 still can not figure it out, remember, you do not need to understand the intermediate encryption / decryption result to know that a key pair worked out;)

I do not even need to say what happens if the same key is used in both steps, right? : D

And that's why the name of the attack is encounter in the middle. You attack the algorithm on one side (with the cipher) and on 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've encrypted." 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 their keys. He can now guess the keys and decrypt everything else you have encrypted with those keys.

And lastly, that's why the industry went straight from DES to triple DES. When they were about to make a new algorithm they realized that dual DES would be very vulnerable to this type of attack. Triple is also, but it is less vulnerable (add one more step of encryption) - to the point that it has been accepted for a time as a good standard. I do not know how you are today.

Credit where it deserved, I took various information from wikipdia .