What is more secure, a ciphertext encrypted with AES-256 or encrypted with 3 different AES-128 keys?

Question

Or better yet, is encrypting a block with 2 AES-128 keys just as secure as encrypting a block with 1 AES-256 key? By the way, I've only recently been learning cryptography stuff; I've made working prototypes in python for both RSA and AES and am familiar with (basically) how they work in general; just not the complex mathematical concepts and terms.

Although my intuition tells me that you cannot fully decrypt a message encrypted twice with two different keys without knowning both keys, that fact that I haven't heard of doing this makes me think it's been asked and answered to the negative and I'm just not seeing it. If AES is really fast, what's to stop paranoid people from going all the way up to 16-32 different keys? That is completely computationally viable for email and chat clients, maybe even other applications (I know nothing about computational complexity).

If I had to guess what would break this, I would say that for any known ciphertext encrypted with AES-128, there exists exactly one 128 bit key that will return the original plaintext from the recovered ciphertext. But I can't see a method for potentially figuring out what the original plaintext was, since that ciphertext could decrypt into any and all plaintexts still.

Answer 1

You have more than one question in your... question. user13741 already did answer the "is 2x AES-128 as secure as 1x AES-256?" part, so only a small summary: Plaintext is the message before it was encryptet, and ciphertext after it was encryptet. You can encrypt a known plaintext with all possible keys and save the result. Now you decrypt the ciphertext with all possible keys and look if the result is in the database of the first encryption task. If yes, you have found the two keys. The first task takes $2^{128}$ encryptions (for AES-128) and the second task takes $2^{128}$ decryptions. If you add them you get not $2^{256}$, but $2^{129}$. That attack is called Meet-in-the-middle attack. (But you need the space to store $2^{128} \times 128$ bit. That's more than you will ever be able to store, but still you have to consider this. Maybe a future attack will somehow reduces the security of AES in a way which will make this kind of attack feasible without storing over $10^{27}$ terabytes.)

In the title you ask about 3 different AES keys. Yes, this construct is more secure than AES-256. An attack on this (if AES is not broken) would take something like $2^{257}$ encryptions or decryptions, even more than on AES-256. Without the mentioned meet-in-the-middle attack you would even need $2^{384}$ to fully search the possible key space. This is the reason why Triple DES was used and not Double DES. DES with two keys would be enough in terms of the number of possible keys, but this attack makes it possible to reduce the amount of work to a nearly managable number. Not secure enough for most of the experts.

Why nobody (or at least not a high number of people) encrypt their message more than one time? There's no need for that. Even $2^{128}$ attemps are totally unfeasable. Even if the future of the world would depent on it and every government would need to break it. There are just too many possible keys. An attack on the person which knows the key or attacking the underlying protocol is much more promising.

Yes, you are right, there's exactly one key which results in the given plaintext for a given ciphertext (and the other way round). Also there's exactly one plaintext for every given plaintext and given key (and vice versa). This is true for AES-128, while AES-192 and AES-256 are slightly more complicated, but not much.

Now comes the big "but": All this only works if AES is fully secure. It is not. There exist some attacks which reduce the amount of security AES has. AES-256 is more "broken" than AES-128 and AES-192 (because the key setup is slightly different for AES-256 and it uses a bigger key size). Still, all three are (as we know it) still not really broken. The security margin is still quite high and the kind of attack is a pretty hard one. We don't have to panic, but for the future we should either change AES to make it more secure (Bruce Schneier suggests more rounds as fast and easy change) or take a look at some other ciphers like one of the other finalists of the AES process. If you really need to secure some highly risky data for 30 years against the NSA and other major organisations, than you should consider not using AES. For every normal person, AES is more than enough.)

Answer 2

Encrypting once with a 256-bit key is stronger than encrypting twice with two 128-bit keys.

This is because of the Meet in the middle Attack.

Encrypting once with a 256-bit key gives you 256 bits of security.

Encrypting twice with two 128-bit keys gives you 129 bits of security.