How to calculate the complexity of a meet-in-the-middle attack in terms of the key size k (Use big-O notation)

Question

I dont understand this question at all what is it trying to tell me:

The meet-in-the-middle attack means that two successive encryptions using two different k bit keys do not give the security against a brute-force attack that you would expect from a 2k bit key. Blockquote

(a)

Consider the situation when using two successive AES encryptions. Calculate the complexity of a meet-in-the-middle attack in terms of the key size k (Use big-O notation). Assume that a 2-DES attack required you to build tables containing the “middle” values. Making simple assumptions, what is the size of these two tables? Show your working. Blockquote

(b)

In the meet-in-the-middle attack, if we built the tables first and then looked for matches, we would have another high complexity problem. For each of the table 1 entries, compare with all the table 2 entries; this algorithm has complexity of O(22k). Explain how the matching could be done while building the tables, resulting in the total complexity remaining at O(2k+1).

Answer 1

The meet-in-the-middle attack means that two successive encryptions using two different k bit keys do not give the security against a brute-force attack that you would expect from a 2k bit key.

Consider the case where you take your plaintext, encrypt it once with a $k$-bit key, and then encrypt it a second time with a second $k$-bit key.

You used a total of $2k$ bits of key; however this can be attacked with less effort than by simply trying all possible combinations of the $2k$ bits of key.

Blocks (a) and (b) try to talk about the complexity of how it is done; however they assume that you know the basic technique. If you don't, well, that's probably what's confusing you (and block (a) talking about AES at one point and DES at another may well add to the confusion).

The basic attack is fairly simple; go through all possible values of the first $k$-bit key, and generate all possible first stage encryptions; go through all possible values of the second $k$-bit key, and decrypt the known ciphertext with that key, generating what had to be input to the second stage. For the correct guess, the output of the first encryption had to be the input to the second, and so look for a match. This is known as the 'meet-in-the-middle' attack; where you attack the cipher from both sides (and meet in the middle).