Clarification on expected number of plaintext, ciphertext pairs needed to identify AES keys

Question

I'm aware of the many questions on this topic, but I'm still not sure what went wrong with my reasoning here below.

I'm assuming use of AES with key size $2^{256}$ and messages of size $2^{128}$, using ECB. When I tried computing the expected number of plaintext-ciphertext pairs required until key-identification, I reasoned as such:

For a single pair $(m,c)$:

$$\Pr_k[E_k(m)=c]=2^{-128}$$

For $n$ pairs (due to i.i.d):

$$\Pr_k\big[(E_k(m_1)=c_1) \wedge (E_k(m_2)=c_2) \wedge ... \wedge (E_k(m_n)=c_n)\big]=2^{-128n}$$

So we're looking for $n$ such that the expected number of keys that agree on all $n$ pairs is $1$, i.e.:

$$\frac{2^{256}}{2^{128n}}=1$$

So $n=2$.

This answer matches the other answers in related posts, but my problem is with the fact that if I take $n \to \infty$ (or even just a large $n$) I get $0$ expected matches (or less than $1$ for large $n$). So this doesn't seem correct.

I know that each key is very unlikely to be the key, which is ideal, but I was looking for a formal way to compute the expected number of keys that would match. Is there a way to fix this? Or reconcile my solution with the $n\to \infty$ issue?

Answer 1

Your calculation determines the probability that for random, uniformly sampled "input" blocks and "output" blocks, there is a key that could produce these matchings. However, if we know that the matched inputs and outputs are produced from a causal key, the expression is different.

In this latter scenario, for a well-designed block cipher, a good approximation for the number of keys that could produce the matching of $m$-pairs, given a block size of $b$ and a key size of $k$ is given by $$1+\mathrm{Poisson}\left(\frac{2^k-1}{2^{bm}}\right).$$ The initial 1 represents the causal key and the Poisson term represents the non-causal solutions. One can view this Poisson term as an approximation to a binomial expression where there are $2^k-1$ "independent" non-causal keys each of which has a $2^{-bm}$ chance of creating a matching by chance. The situation is slightly muddied by the modelling of the cipher as a random permutation rather than a random function, but this does not affect matters significantly at this level.

Note then that if one tries to exhaust a $k$-bit key using only $k$-bits of check then we expect to get very close to two possible solutions (you can check this for small key sizes). Further testing is then required to distinguish the causal key from any non-causal solutions. However, the number of non-causal solutions rapidly tends to zero as the bits of check outscale the key space.