0
$\begingroup$

I read it once on a page (I don't remember the link and I coundn't find it) that said about a cascade of AES with two 256-bits keys and that it provides 384-bits of security. Maybe not 512-bits of strength because of AES-256 block size of 128-bits.

This left me doubts.

Let's suppose I encrypt something two times using CBC mode and two different keys.

An adversary cannot determine a block encrypted with the first layer of encryption because is XORed with the preceding block and the preceding block is encrypted with the second layer of encryption. This could render the encryption immune to Meet-in-the-middle attacks, am I right or not?

$\endgroup$
3
  • 1
    $\begingroup$ If you don't find the previous answer helpful, why should one write another? You should indicate what is not clear or why did the answer was not helpful. The answer is yes similar to previous. The previous block is the IV so MiTM attack is possible with a known-plaintext attack. Also, you should support your claim by providing the page. $\endgroup$
    – kelalaka
    Commented Feb 4, 2022 at 12:44
  • $\begingroup$ @kelalaka Sorry, I don't remember the link of the page and I searched for it but I cannot find it. How can I mark the answer useful? Sorry, I don't find this resource here in the question page. $\endgroup$ Commented Feb 4, 2022 at 23:46
  • $\begingroup$ One can upvote an answer if it is useful/correct/etc. Asker can accept an answer if the answer satisfies them (check mark under the up/down vote). So others can see that the questions have satisfactory. Downvote if wrong and indicate it with a comment. $\endgroup$
    – kelalaka
    Commented Feb 5, 2022 at 22:46

1 Answer 1

2
$\begingroup$

If the IVs for both encrypted layers are transmitted in the clear, then there's a generic known-plaintext key recovery attack that works on (essentially) any encryption mode and allows the two keys to be recovered using about $3 \lceil k \mathbin/ b \rceil \cdot 2^k$ block en/decryptions, $2k \cdot 2^k$ bits of memory and $O(k \cdot 2^k)$ non-cipher computation time on average, where $k$ and $b$ are the key and block sizes of the cipher in bits (i.e. $k = b = 128$ for AES-128 or $k = 256$, $b = 128$ for AES-256). It simply goes like this:

  1. Decrypt the first $\lceil k \mathbin/ b \rceil$ blocks of the ciphertext with each of the $2^k$ possible outer keys and the known outer IV. For each key, take the first $k$ bits of the resulting plaintext (if $k$ isn't already a multiple of $b$, which it always is for AES), append the key, and store the combined $2k$-bit string in a list.

  2. Sort the list. (This takes $O(n \log n)$ time for an $n$-element list, where $n = 2^k$ in this case.)

  3. Attempt to encrypt the first $\lceil k \mathbin/ b \rceil$ blocks of the known plaintext using each of the $2^k$ possible inner keys and the known inner IV. For each key, look up the first $k$ bits of the resulting plaintext in the list (using a binary search, which takes $O(\log n)$ time) to get a list of possible outer keys this inner key could match. (The average number of candidate matches you'll find per inner key is one, although of course some keys will have no matches and some will have several.) If there are any matches, encrypt one more block of the known plaintext with the inner key and decrypt one more block of the ciphertext with each matching outer key to see if they still match. If they do (which you'd expect to happen after testing half of the inner keys on average), you almost certainly have the right key pair.

A generic brute force key-recovery attack on a single layer encryption, of course, takes about $\frac12 \lceil k \mathbin/ b \rceil \cdot 2^k$ block en/decryptions on average. Thus (at least if we ignore the memory costs and only count block cipher operations) double encryption with known IVs is only (at most) $6$ times harder to break on average than single encryption, for (only!) about $\log_2 6 ≈ 2.6$ extra bits of security. Which, just to be clear, is absolutely negligible.

(Admittedly, the memory cost of this attack is not necessarily negligible, but there are also various time–memory tradeoffs that can be made to reduce it.)


Note that the generic meet-in-the-middle attack described above depends on the inner IV being available to the attacker in plain. If it's not, but is instead also encrypted with the outer key, then the attack won't work without modifications.

Of course, a trivial solution would be to simply brute force all possible values of the 128-bit inner IV in step 2. For double AES-256, this will allow the double encryption to be broken in about $2^{128} \times 2^{256} = 2^{384}$ AES encryptions, which is still less than the $2^{512}$ encryptions one would expect from the key length.

$\endgroup$
1
  • $\begingroup$ You went to full mode, which I need to update, then, too. :) $\endgroup$
    – kelalaka
    Commented Feb 4, 2022 at 18:55

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.