3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Your title and question body are asking 2 different questions. 3x128 would take 2.1X the time to encrypt, with 1.5X the key material, for a marginal increase in theoretical security. There is no practical MITM attack against a 128-bit block or key, and probably wont be for a long time. The answer to the storage question is "a crap load", aka, quadrillions of exabytes $\endgroup$ – Richie Frame Mar 13 '17 at 3:45
  • $\begingroup$ actually the question like this. 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? $\endgroup$ – Aizat Marzuki Mar 13 '17 at 4:34
  • $\begingroup$ isn't the question same crypto.stackexchange.com/questions/44669/… $\endgroup$ – khan Mar 13 '17 at 8:03
  • $\begingroup$ Our generic question on textbook MitM is Meet-in-the-middle with checking complexity, though it is in the context of DES and the answer needs adaptation. For techniques with feasibly much memory, there's Can cycle finding techniques reduce the memory usage of the MitM attack against 2DES, but it only comes with an arguably hairy answer of mine, that was not accepted. $\endgroup$ – fgrieu Mar 13 '17 at 9:01
2
$\begingroup$

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 2128 encryptions for building a dictionary, and an expected 2127 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⋅2127 AES-128 operations. That's so large as to be currently impossible: the realm of feasibility nowadays stops somewhere a 275 to 2100, 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 2128 words each 128-bit, that is 2135 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 4F2 with feature size F=10nm, thus we are talking 0.9⋅1021m3 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!

Computing that silly amount of RAM is pointless, because there is a well-known (but seldom taught) refinement of MitM that requires a feasible amount RAM, and only slightly 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 2b or even 23 b /2 encryptions.

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Depending on what you need to do, AES-256 may also be subject to some weaknesses. AES-192 and AES-256 have related key attacks that AES-128 do not have. A related question here crypto.stackexchange.com/questions/1549/… $\endgroup$ – user4982 Oct 5 '17 at 18:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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