4
$\begingroup$

I am revising for my exams and I have come across this question in a past paper and I am not confident about it at all.

Assuming that only the smallest permissible key and block sizes can be used I have derived the following:

Possible plaintext blocks: $2^{128}$

Possible ciphertext blocks: $2^{128}$

Possible mappings: $(2^{128})!$

Possible keys: $2^{128}$

My assumption is that it is true that you can find a key given a plaintext and ciphertext since there are significantly way more mappings than there are keys. But then again, are there even enough mappings for that to be possible?

I really feel like I am missing something important here. Are there any hints or suggestions you can give?

$\endgroup$
1
  • $\begingroup$ No! There are significantly more mappings than there are keys, so not every mapping has a key. Even for one-block pairs, there could be more than one key that produces the same ciphertext/plaintext pair, so that means some of them have zero keys. $\endgroup$ Commented Jan 15, 2018 at 4:40

2 Answers 2

4
$\begingroup$

The answer is no, such a key need not exist. Let the given plaintext/ciphertext pair be $P,C$ and let $n=2^{128}.$

How many permutations on $n$ points map $P$ to $C$? Clearly $(n-1)!.$ Thus, if we could uniformly sample all possible permutations, the probability that under a given permutation $P$ would map to $C$ is a tiny $$ \frac{(n-1)!}{n!}=\frac{1}{n}. $$

Since the AES keyspace also has size $n,$ the expected number of keys that would have this property is $n\times(1/n)=1,$ provided we assume AES perfectly samples the keyspace with respect to this arbitrary property $P\mapsto C.$ But there are no guarantees that it does so since it uses only 128 bits instead of $\log n!$ bits.

$\endgroup$
1
$\begingroup$

As you said, there are many more possible permutations than keys. So it may be that the permutations that contain the particular mapping are not selected by any key in the tiny amount of $2^{128}$ keys available.

$\endgroup$
2
  • $\begingroup$ So you would say that the answer is no, it is not always possible because the given mapping might not have been selected due to the difference in the number of keys to actual mappings? $\endgroup$
    – Matic
    Commented Jan 14, 2018 at 22:19
  • $\begingroup$ Yes, basically. $\endgroup$
    – Maarten Bodewes
    Commented Jan 14, 2018 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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