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