[Math] Is it possible to guess an AES key from a series of messages encrypted with that key

cryptography

I was wondering if it is practically achievable to guess an AES key from a large number of short messages encrypted with that key, the attacker knowing the exact content of every message.
Suppose the messages are very short (one block), and quite many (about 100.000).

If such a cryptographic mechanism is weak, how can it be enforced (sticking with AES)? Maybe a mechanism of salting implemented with, suppose, 10 different algorithm variants and the no. of the variant written into every message?

Thank you in advance for your opinions.

Best Answer

No, it is not possible to recover an AES key from even a very large number of known plaintext-ciphertext pairs. In fact, this is one requirement of defining a "strong block cipher".

To be more precise, "There is no publicly-known way to extract the key with non-trivial probability, given any number of plaintext-ciphertext pairs, in a practical amount of time using a practical amount of computing resources."

In fact, in order to be considered "good", AES must defend against even stronger attacks than the one you mention. For example, even if you get to choose the plaintexts and you are then given the ciphertexts under some hidden key, you still should not be able to recover the key (this is called a "chosen plaintext attack").

Even if you get to choose plaintexts (and are given the corresponding ciphertexts), and can choose ciphertexts (and are given the corresponding plaintexts), you should still not be able to recover the key. This is called a "chosen ciphertext attack".

The "gold standard" for block ciphers, however, is none of these. It's an even more demanding test called "indistinguishability" and it can be stated several ways. I'll informally give the one usually called IND-CPA.

Suppose there are two black boxes that look externally the same (both take 128 bits in and output 128 bits out), but internally one is AES under a randomly-chosen (but hidden) key. The other maps its 128-bit input to a random 128-bit output, but is careful to never map two different inputs to the same output (ie, it's an invertible function, but that's the only restriction).

With this setup in place, consider an attacker (aka an "adversary") that is allowed to query either box with 128-bit strings of her choice. For each query, she receives a 128-bit response which is either the AES-encryption or a random string.

In order for AES to be considered a "strong" block cipher, no adversary that runs in "reasonable" time using "reasonable" resources should be able to tell which black-box is which with better than a .5+$\epsilon$ probability, where $\epsilon$ is a "small" positive number.

Notice that the goal is not key-recovery here: though recovering the key would certainly suffice, the adversary has a much easier goal here. She needs to simply tell which box is which and she wins.

It is believed that AES enjoys IND-CPA, but there is no proof of this. In fact, there is likely to never be a proof. So we assume it to be true, much as we assume factoring the product of two large primes is intractible. The good news is that, after these unsettling assumptions around the cryptographic primitives, everything built upon them (modes of operation, MAC schemes, signatures, SSL, SSH, voting, crypto-cash, etc) can be proven secure under the assumption that the primitives are secure.

Related Question