Consider the use of double encryption applied to the AES algorithm with two 128-bit keys

Question

Actual Question below.

Consider the use of double encryption applied to the AES algorithm with two 128-bit keys. How much storage and computation would be required to execute a meet-in-the-middle attack?

Answer 1

Double encryption applied to the AES-128 algorithm and two random keys is theoretically breakable from 3 plaintext/ciphertext pairs by the generic Meet-in-the-Middle attack with 2¹²⁸ encryptions for building a dictionary, and an expected 2¹²⁷ attempts each requiring a about one decryption and two encryptions (the later is for checking an average of one candidate key pair). This totals to an expected 5⋅2¹²⁷ AES-128 operations. That's so large as to be currently impossible: the realm of feasibility nowadays stops somewhere a 2⁷⁵ to 2¹⁰⁰, with the later acknowledged good to 2020 by many authorities. Thus we have a margin like a thousand millions, which I guess is fine for a good two decades, save for fairies or imminent breakthrough in quantum computers making them useful for such tasks.

The amount of memory required for the schoolbook MitM attack is 2¹²⁸ words each 128-bit, that is 2¹³⁵ bits. Nowadays, a silicon wafer is seldom less than 80µm 50µm thick (these are used in Smart Cards, and obtained by milling normal wafers rather than by using ultra-thin wafers), a DRAM cell occupies an area of at least 4F² with feature size F=10nm, thus we are talking 0.9⋅10²¹m³ of silicon; that's 80% of the volume of earth, which contains only 15% silicon. Quick, make these wafers even thinner or (more realistically) start making 3D silicon that is not stacked wafers!

There is a well-known refinement of MitM that requires a feasible amount RAM, but more computation than the generic MitM. See Paul C. van Oorschot and Michael J. Wiener: Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, 1999).

Interestingly, it is not known any generic technique that uses moderate amount of RAM and breaks two-key triple encryption of some b-bit block cipher with cost commensurate to 2^b or even 2^3 b /2 encryptions.

Answer 2

fgrieu answered this in a footnote elsewhere:

---

Double AES with two 128 bit keys would be significantly slower than single AES with a 256 bit key (20 rounds versus 14). Also double AES-128 would theoretically be vulnerable to a Meet-in-the-Middle attack, when AES-256 is not.

---

So how much storage and computation a meet-in-the-middle attack would take doesn't matter as there is no real reason to be using double AES-128 (as it's slower and probably weaker than AES-256).