2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Your title says 3 AES-128 keys, the body says 2. Which one are you talking about? $\endgroup$ Nov 5, 2014 at 16:25
  • $\begingroup$ I can see how that was unclear. I was essentially asking if using two 128 keys is the same as one 256 key, or three 128 keys was better than one 256 key. I understand it now that using two 128 keys is basically the same as a 129 bit key, since (2 ^ 128) * 2 = 2^129. $\endgroup$ Nov 5, 2014 at 19:23

2 Answers 2

4
$\begingroup$

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.)

$\endgroup$
9
  • $\begingroup$ Thank you. I'm very new here (this was my first post) so sorry if I didn't format correctly or follow guidelines. $\endgroup$ Nov 5, 2014 at 19:12
  • 2
    $\begingroup$ I STRONGLY disagree with the claim that AES is broken, including AES-256. Some weaknesses have been found for RELATED-KEY ATTACKS, but these have no affect whatsoever on its intended use as a block cipher (pseudorandom permutation). If you want to use AES as an ideal cipher (e.g., to construct a hash function or something else), then this is a problem. But, you shouldn't really be doing that anyway. $\endgroup$ Jul 8, 2015 at 20:14
  • 1
    $\begingroup$ @YehudaLindell: As far as my understanding for "broken in the academic sense" goes, it means that there's a faster way to get the key than pure brute force. (Not including rubber hose attacks or something like that.) Even if you don't count related-key attacks, there's still the bicliques attack: blog.agilebits.com/2011/08/18/aes-encryption-isnt-cracked $\endgroup$
    – Nova
    Jul 9, 2015 at 9:27
  • 1
    $\begingroup$ @YehudaLindell: It's about broken "in the academical sense". That doesn't mean that it is insecure to use AES. In fact, it appears to be still secure for practical purpose (at least as far we know). Technical there's a faster way than brute force to break AES, but that way is still not possible to do in the real world. $\endgroup$
    – Nova
    Jul 9, 2015 at 23:21
  • 1
    $\begingroup$ There are not 2^128 protons in the universe. I wonder how the meet in the middle can be executed. $\endgroup$
    – Joshua
    Dec 22, 2015 at 23:52
3
$\begingroup$

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.

$\endgroup$

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.