# Number of plaintext–ciphertext pairs needed to rule out false keys with a reasonable likelihood in AES

I am new to cryptography and I've got the following question from Understanding Cryptography:

Imagine that aliens — rather than abducting earthlings and performing strange experiments on them — drop a computer on planet Earth that is particularly suited for AES key searches. In fact, it is so powerful that we can search through 128, 192 and 256 key bits in a matter of days. Provide guidelines for the number of plaintext–ciphertext pairs the aliens need so that they can rule out false keys with a reasonable likelihood.

What I tried

I know that the expected number of keys that encrypt a plaintext $$x_1$$ to $$y_1$$ is $$2^{k-n}$$, where $$k$$ is the key length in bits, and $$n$$ is the size of a block in bits.

I also know that given $$\{(x_1, y_1), \dots, (x_t, y_t)\}$$ PT-CT pairs, the expected number of false keys which encrypt all plaintexts to the corresponding ciphertexts is $$2^{k-tn}$$.

Therefore, for AES-128, AES-192, and AES-256, I would expect that only two PT-CT pairs is sufficient, given that the expected number of false keys would be, respectively, $$2^{-128}$$, $$2^{-64}$$, $$2^0=1$$.

What the answer manual says The manual says that, for AES-128, only one pair is sufficient. This one I can see why, since the expected number of keys that map $$x_1$$ to $$y_1$$ one be $$\frac{2^{128}}{2^{128}}=1$$.

For AES-192, the manual says that "in order to find the correct key with a probability of 50 percent, we require $$2^{63}$$ pairs of plaintexts and ciphertexts". And for AES-256, also with 50% probability, $$2^{127}$$ PT-CT pairs are required.

I cannot see why such values are required for AES-192 and AES-256.

• You’re right; they’re wrong. – Daniel Shiu Apr 4 at 20:36
• This is a possible dupe Finding key of AES in ECB mode – kelalaka Apr 4 at 20:38
• Both you and they are wrong; The manual says that, for AES-128, only one pair is sufficient. This one I can see why, since the expected number of keys that map $x_1$ to $y_1$ one be $\frac{2^{128}}{2^{128}}=1$. $${}$$ What if the permutations selected by the two distinct random keys are fixing a random PT-CT pair? Then you will need at least two pairs (maybe there are more). Expected value doesn't guarantee what is exactly needed. If you want to find the actual value, you need to model AES as a PRP ( not proven) then talk about the probabilistic values. – kelalaka Apr 4 at 22:34