3
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ You’re right; they’re wrong. $\endgroup$ – Daniel Shiu Apr 4 at 20:36
  • $\begingroup$ This is a possible dupe Finding key of AES in ECB mode $\endgroup$ – kelalaka Apr 4 at 20:38
  • $\begingroup$ 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. $\endgroup$ – kelalaka Apr 4 at 22:34
1
$\begingroup$

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

That's because you have a correct understanding of the situation, and the answer manual is wrong.

Your analysis in "what I tried" is correct; there's not a whole lot I can add to it...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.