Compare AES-256 (type A) with double AES using two independent 128-bit keys (type B, built like double DES). How do the two fare against table look-up, exhaustive key search and meet-in-the-middle?
Table look-up and exhaustive key search cost about the same for both (a 256-bit key space). Meet-in-the-middle breaks double AES with about $2 \cdot 2^{128} = 2^{129}$ operations instead of $2^{256}$, while it gains nothing against AES-256.
| Attack | AES-256 (A) | Double AES-128 (B) |
|---|---|---|
| Table look-up | key space $2^{256}$ | key space $2^{256}$ |
| Exhaustive key search | $2^{256}$ | $2^{256}$ |
| Meet-in-the-middle | not applicable | $\approx 2^{129}$ operations (plus $2^{128}$ storage) |
Why meet-in-the-middle hits type B: with a known plaintext-ciphertext pair, encrypt $M$ under all $2^{128}$ values of $K_1$ and store the results, then decrypt $C$ under all $2^{128}$ values of $K_2$ and look for a match in the middle. That costs $2 \cdot 2^{128} = 2^{129}$ cipher operations, so double AES-128 is barely stronger than single AES-128.
Lesson: two keys of $k$ bits in a cascade do not give $2k$ bits of security. If you want a 256-bit level, use a cipher with a native 256-bit key. $2^{129}$ is still far out of reach, but you paid for twice the work and got almost nothing.