8
$\begingroup$

Standard meet-in-the-middle explanations show that you can perform a meet-in-the-middle attack on a repeated block cipher such as double-DES (performing DES twice in a row).

However, block ciphers themselves commonly consist of a number of rounds internally. Would it be possible to use a meet-in-the-middle attack on a single block encrypt?

In other words, will encryption / decryption meet a common middle state that allows us to see $\newcommand{\E}{\text{E}} \newcommand{\D}{\text{D}}$ $C = \E_k(M) = \E_{k''}(\E_{k'}(M))$ and $M = \D_k(C) = \D'_{k'}(\D''_{k''}(C))$ so that $S = \E'_{k'}(M) = \D''_{k''}(C)$ where $S$ is a middle state?


Related question: Understanding Meet-in-the-Middle attack on block ciphers.
Related Wikipedia page: Meet-in-the-middle attack with additional references to Multi-Dimensional Meet-in-the-Middle attacks on e.g. GOST.

$\endgroup$
1

2 Answers 2

7
+50
$\begingroup$

Meet-in-the-middle attacks can indeed be used for block cipher (but also hash function) cryptanalysis. As mentioned in the question, this goes back to Diffie and Hellman's analysis of DES. However, when applied to primitives, one typically uses more sophisticated techniques. Since the literature around this topic is very extensive, I won't go into the details of all techniques but I'll instead try to provide the main references.

The first four sections of this answer discuss variants of the classical MITM attack. These attacks are the most similar to the attack on 2DES that you refer to. Probably the most interesting aspect of classical MITM attacks is their low data complexity, which makes them attractive from a practical point of view. There are some exceptions to this, though (bicliques being the most notable).

The last section, however, argues that the general MITM idea is even more widespread in cryptanalysis. That is, many statistical attacks are supplemented with a phase that can reasonably be called a MITM step. A good example of this is the Demirici-Selçuk attack. Here, the data requirements are usually larger.

Basic MITM attack

The classical MITM attack is easy: one splits the cipher in two parts with independent keys, say $K_1$ and $K_2$. For each guess of $K_1$, compute the intermediate state by evaluating in the forward direction. Similarly, the intermediate states are computed for each guess of $K_2$ by evaluating in the backward direction. The candidate keys are those for which the intermediate states match.

The main issue with this simple approach is that, after a few rounds, it is likely that too many key bits must be guessed in order to obtain the intermediate state. (Leading to a blow up of time and memory requirements.) Of course, the key schedule plays an important role here. For example, MITM is typically useful in block ciphers with a small block size but a larger key size.

The basic MITM attack has been applied to DES itself (so not just 2DES), and several improvements have been introduced since. For example, you can take a look at Improved Meet-in-the-Middle Attacks on Reduced-Round DES by Dunkelman, Sekar and Preneel (INDOCRYPT 2007). Some dedicated tricks are used there; more advanced and generic variants are discussed below.

3-subset MITM

A common improvement over the basic attack was introduced by Bogdanov and Rechberger at SAC 2010. In these attacks, one splits the cipher into three parts. For each guess of the key bits that are involved in the second and third part, one matches the forward and backward guesses but this is done based on only part of the state (partial matching). This makes it possible to cover additional rounds in the middle part. The downside is that partial matching leads to more false-positives, so you end up with a larger list of key candidates.

The recent attacks on GIFT by Sasaki that I mentioned in the comments are based on this 3-subset technique. In addition, he uses the "splice-and-cut" and "initial structure" techniques that originated in preimage attacks on hash functions (see next section). That work uses MILP modelling to optimize such MITM attacks on GIFT. The reason I mention it is because the simple structure of GIFT makes it a good introduction to such attacks.

Influences from hash function cryptanalysis

The use of MITM techniques to find preimages of hash functions goes back a long time, at least since Lai and Massey (EUROCRYPT 1992) (and probably earlier). For example, this technique is used in Leurent's preimage attack on MD4 from FSE 2008.

Soon after, a number of improvements were proposed by Aoki and Sasaki. In particular:

  • The splice-and-cut technique, introduced at SAC 2008, with applications to MD4 and MD5.
  • Initial structures (as a generalization of local collisions) at EUROCRYPT 2009.

They also applied these techniques to reduced SHA-0 and SHA-1 at CRYPTO 2009. There are also several follow up works here, such as the additional improvements of Guo et al. with applications to SHA-2.

Generally speaking, this so called "splice-and-cut framework" led to major improvements in preimage attacks on hash functions. Of course, these attacks are about message recovery as opposed to key recovery. Nevertheless, the same principles can be applied to block ciphers.

The biclique, due to Khovratovich, Rechberger and Savelieva, is another tool that was initially introduced for preimage attacks. In these attacks, bicliques replace initial structures. Bicliques were also (famously) used for key-recovery attacks on full-round AES, see the ASIACRYPT paper by Bogdanov, Khovratovich and Rechberger.

Other variants

Other variants that are worth mentioning are multidimensional MITM attacks (as mentioned in the question, some information can be found on Wikipedia), all subkeys recovery and sieve-in-the-middle attacks.

The all subkeys recovery attack is a way to deal with more complex key schedules. This is due to Isobe and Shibutani.

A sieve-in-the-middle attack is a generic improvement due to Canteaut, Naya-Plasencia and Vayssière, CRYPTO 2013. The idea is to replace (partial) matching by a sieving process which discards invalid transitions for a middle S-box. The middle S-box can be a superbox, so you can gain e.g. 2 rounds in many ciphers.

MITM as a general idea (including Demirici-Selçuk)

The first/last round trick as used in linear and differential cryptanalysis is basically a kind of MITM attack. At least in some cases, the number of rounds for which partial subkeys are guessed can be quite large, so that one essentially divides the cipher in three parts and performs matching in the middle using e.g. a linear approximation. Of course, here, there are again a bunch of specialized techniques.

Usually, the most significant part in such attacks is finding the right statistical properties as opposed to the key guessing part. This sets them apart from the MITM attacks described above and hence they are not usually referred to as MITM attacks.

A good example of an attack that is universally referred to as a MITM attack, but which doesn't belong to one of the MITM attacks described in the above sections, is the Demirici-Selçuk attack.

The basic DS-MITM is an attack on the AES based a 5 round distinguisher. Note that this distinguisher is not really a (simple) square attack. Rather, it's an extension of a 4 round distinguisher due to Gilbert and Minier which in turn extends the classical integral/square distinguisher for 3 rounds of the AES. The 5 round distinguisher is extended to 7 or 8 rounds by partial key guessing. I won't go into the details (this should probably be a different question).

Just to give a glance of the importance of this attack, here's a brief chronological overview of follow-up research on this topic:

The DS-MITM attack also applies to other ciphers. For instance, this paper from ASIACRYPT 2018 uses constraint programming to automate the process with applications to several lightweight ciphers. Not all of the extensions (in particular differential enumeration) are automated though.

$\endgroup$
2
$\begingroup$

The Demirci-Selcuk attack on reduced round AES (from FSE 2008) uses the "Square distinguisher" on AES, if you are on Researchgate you can find a pdf, I have not seen any accessible versions. The authors state:

In this paper we provide a distinguisher on 5 inner rounds of AES. This dis- tinguisher relates a table entry of the fifth round to a table entry of the first round using 25 parameters that remain fixed throughout the attack. Using this distinguisher, we are able to attack up to 8 rounds of AES-256.

The square distinguisher is below (see also the question here):

Throughout this paper by an active entry, we mean an entry that takes all byte values between 0 and 255 exactly once over a given set of plaintexts. By a passive entry we mean an entry that is fixed to a constant byte value. Proposition 1 ([8]). Take a set of 256 plaintexts so that one entry in the plaintext table is active and all the other entries are passive. After applying three rounds of AES, the sum of each entry over the 256 ciphertexts is 0.

This five round distinguisher cant be used in practice to attack 10 rounds (plus this is AES 256 they are attacking) due to prohibitive computational complexity. So 7 rounds are attacked instead.

This work at Integer Linear Programming for Three-Subset Meet-in-the-Middle Attacks: Application to GIFT by Yu Sasaki at IWSEC 2018 seems to be what @Aleph is referring to, but I haven't found a non-paywalled link to it either.

$\endgroup$

Your Answer

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

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