Meet-in-the-middle attack

A meet-in-the-middle attack is a generic cryptographic attack . It makes use of the fact that vulnerable cryptographic algorithms split up your key and only use part of the key during the calculation of the cipher in individual steps. A common example of this are encryption methods that use their actual encryption algorithm several times with different keys.

Procedure

In a cryptographic method that is not susceptible to this type of attack, plain text and a key are used as input for an algorithm and, for example, a cipher is calculated from them. If an attacker has a pair of plain text and cipher, he can only calculate the key (provided the method is not vulnerable to another attack) by using the brute force methodtried all possible keys and compared the result with the cipher. However, if the algorithm divides the key and calculates individual intermediate results with one key part each without making use of the other key parts, an attacker can calculate the parts of the key individually. The attacker benefits from the enormously reduced computing effort. If it attacks the parts of the process from both sides of the algorithm (i.e. from the plain text and backwards from the cipher) at the same time, one speaks of a meet-in-the-middle attack. It is therefore necessary that the intermediate steps can be reversed .

Be given and without loss of generality just and . For this purpose, an encryption method is given by: ${\ displaystyle K = (K_ {1}, K_ {2}, \ cdots, K_ {n})}$ ${\ displaystyle n}$ ${\ displaystyle | K_ {1} | = | K_ {2} | = \ dots = | K_ {n} |}$

${\ displaystyle \ operatorname {Enc} _ {K}: = \ operatorname {Enc} _ {K_ {n}} \ circ \ operatorname {Enc} _ {K_ {n-1}} \ circ \ cdots \ circ \ operatorname {Enc} _ {K_ {1}}}$

Then the attacker can calculate the first cipher for everyone with the plain text message . At the same time, it calculates the result of the last intermediate step for everyone with the cipher . The attacker then calculates the next intermediate steps from the calculated intermediate results until he has arrived at the same intermediate step from both sides. The attacker now has to temporarily save these ciphers, which he has calculated for everyone and for everyone , together with the relevant key part. This requires memory , as there are only options for key selection for both sets of ciphers . In these two sets there is exactly one pair of ciphers that match: This is the cipher that was generated by the partial keys which, taken together, transferred the original message into the original cipher . The secret key sought is therefore made up of the partial keys that were stored with the intermediate result found. ${\ displaystyle K_ {1}}$ ${\ displaystyle M}$ ${\ displaystyle C_ {1} = \ operatorname {Enc} _ {K_ {1}} (M)}$ ${\ displaystyle K_ {n}}$ ${\ displaystyle C}$ ${\ displaystyle C_ {n-1} = \ operatorname {Enc} _ {K_ {n}} ^ {- 1} (C)}$ ${\ displaystyle (K_ {1}, K_ {2}, \ cdots, K_ {n / 2})}$ ${\ displaystyle (K _ {{\ frac {n} {2}} + 1}, K _ {{\ frac {n} {2}} + 2}, \ cdots, K_ {n})}$ ${\ displaystyle 2 \ cdot 2 ^ {| {\ frac {K} {2}} |}}$ ${\ displaystyle \ prod _ {i = 1} ^ {\ frac {N} {2}} | K_ {i} |}$ ${\ displaystyle M}$ ${\ displaystyle C}$

The complexity of a conventional brute force attack is given by. However, the attack described only has to calculate ciphers and is therefore significantly faster. In addition, there is an increased memory requirement compared to the brute force method. This is why one speaks of a time-memory tradeoff . If the attacker waives the parallelization of the process, even a storage expenditure of is sufficient , since the second set of ciphers can be compared with the first, stored set during the calculation and therefore does not have to be saved. These details relate to the optimal case that it is straight and the partial keys are the same size. If this is not the case, only an approximately optimal reduction in computing and storage requirements can be achieved. ${\ displaystyle 2 ^ {| K |}}$ ${\ displaystyle 2 \ cdot 2 ^ {| {\ frac {K} {2}} |}}$ ${\ displaystyle 2 \ cdot 2 ^ {| {\ frac {K} {2}} |}}$ ${\ displaystyle 2 ^ {| {\ frac {K} {2}} |}}$ ${\ displaystyle n}$

Triple DES example

With Triple DES encryption , the original DES process is used three times in a row, but with different keys. Each message is a DES key encrypted, then by de encrypted and finally with encrypted: ${\ displaystyle M}$ ${\ displaystyle K_ {1}}$ ${\ displaystyle K_ {2}}$ ${\ displaystyle K_ {3}}$

{\ displaystyle \ operatorname {3DES} _ {(K_ {1}, K_ {2}, K_ {3})}: = \ operatorname {DES} _ {K_ {3}} \ circ \ operatorname {DES} _ { K_ {2}} ^ {- 1} \ circ \ operatorname {DES} _ {K_ {1}}}

Since the key length of DES is 56 bits, the Triple DES key space has elements. ${\ displaystyle 2 ^ {56} \ cdot 2 ^ {56} \ cdot 2 ^ {56} = 2 ^ {168}}$

With the meet-in-the-middle attack, however, two steps of the procedure can now be attacked individually and then compared with the third step, which is carried out backwards. An attacker leads first time and saves the results together with the used subkey. Then he calculates times and compares each with the stored cipher set. Once he finds a match, he can assemble the key. ${\ displaystyle 2 ^ {56}}$ ${\ displaystyle \ operatorname {DES} _ {K_ {3}} ^ {- 1} (C)}$ ${\ displaystyle 2 ^ {112}}$ ${\ displaystyle Z = \ operatorname {DES} _ {K_ {2}} ^ {- 1} \ circ \ operatorname {DES} _ {K_ {1}} (M)}$ ${\ displaystyle Z}$

The overall effort for finding the key is thus reduced to DES transformations. This is also the reason why double DES is not used, because the lack of a second transformation in the middle means that there is no additional work compared to DES when calculating the key. ${\ displaystyle 2 ^ {56} \ cdot 2 ^ {56} + 2 ^ {56} \ approx 2 ^ {112}}$

Individual evidence

↑ Manfred Lipp: VPN - virtual private networks . Pearson Deutschland GmbH, 2006, ISBN 978-3-8273-2252-4 , p. 125 .

[1] Manfred Lipp: VPN - virtual private networks . Pearson Deutschland GmbH, 2006, ISBN 978-3-8273-2252-4 , p. 125 .