6
$\begingroup$

I have a question that I can't answer:

A plain text has been encrypted 3 times in a DES method with 3 different keys 56 bit each, after it the text was encrypted for the forth time using a AES method using a 128 bit key, an attacker is planning to decrypt the text using meet in the middle method, how many encryptions and decryption approximately he need to do.

  1. $2^{56}$
  2. $2^{112}$
  3. $2^{128}$
  4. $2^{168}$
  5. $2^{184}$
  6. $2^{240}$
  7. $2^{296}$
Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ I don't like this question. There is no way you can perform the encryption in the first place because the block sizes don't match. I presume that the answer is $2^{168}$ because that's the number of block encrypts required for DES EEE, and the number of AES decrypts is negligible compared to that (and you probably cannot split it any further because AES + single DES decrypt is a higher number than that). $\endgroup$
    – Maarten Bodewes ♦
    Jun 27, 2019 at 11:46

2 Answers 2

Reset to default
-1
$\begingroup$

Assuming this is ECB mode encryption, the workload of a known-plaintext meet-in-the-middle attack will depend strongly on the plaintext here.

If the plaintext contains some non-identical 128 bit blocks that partly coincide on a DES-block, the adversary can reverse the final AES encryption with $2^{128}$ AES decryptions work factor. They can then execute a standard meet-in-the-middle attack on 3DES using parallel collision search (easy compared to the preceding step). See van Oorschot/Wiener for details on the techniques used.

If the plaintext consists only of non-identical 64-bit blocks, the adversary can use the same idea (look for collisions of 64-bit blocks in the ciphertext after AES decryption) to at least rule out some AES keys. They should be able to rule out the vast majority of AES keys when the size of all encrypted plaintexts significantly exceeds the birthday bound for a 64-bit block cipher.

If the plaintext is short and does not contain repetitions of DES blocks that are not also repetitions of AES blocks, there may be no better idea than to perform a meet in the middle attack between 3DES and AES using parallel collision search. This should be doable in time about $\approx 2^{212}/(\sqrt{w} m)$ on a machine with $2w$ AES blocks of memory and $m$ processors (see again the parallel collision search paper).

Improve this answer
$\endgroup$
-2
$\begingroup$

I believe the the MITM attack for 3DES is $2^{112}$, so if MITM attack is between the 3DES and the 4th AES, the most expensive brute force attack between the two is the AES one, which is $2^{128}$.

So all it takes is $2^{128}$ encryptions / decryptions.

Note that I am trying to learn this myself too!

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ Not quite: the MITM attack for 3DES assumes the attacker has corresponding plaintext and ciphertext blocks; with an AES at the end, he doesn't have the ciphertext block after then 3DES $\endgroup$
    – poncho
    Nov 21, 2017 at 14:52
  • $\begingroup$ I am thinking this is similar to MITM for 2DES, where the adversary has the cipher text at the end as well as in between the 2DES, and the attack involves a lookup table of all possible keys. $\endgroup$
    – pip
    Nov 21, 2017 at 14:59
  • $\begingroup$ @poncho I think I get your point now. I need 2^128 to get the cipter text at the end of the 3DES (inv AES), and another 2^112 to do the MITM on the 3DES itself. $\endgroup$
    – pip
    Nov 21, 2017 at 15:42
  • 2
    $\begingroup$ It's a bit tougher than that; even with $2^{128}$ work, you won't have any way to determine which AES-decryption is the correct one, and so throwing $2^{128}$ work will yield $2^{128}$ possible 3DES ciphertexts, not the 1 that MITM assumes... $\endgroup$
    – poncho
    Nov 21, 2017 at 15:52
  • $\begingroup$ I believe the point to establish the theoretical number of encryption/descriptions need for this attack, instead of how practical the attack will be. I think $2^{110}$ is already consider secure. $\endgroup$
    – pip
    Nov 21, 2017 at 18:26

Your Answer

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

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