2
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ How can $n$ go to $\infty$? You cannot have an infinite number of plaintext / ciphertext pairs and there will be permutations that are not valid for any key, i.e. yes, precisely zero keys would match. The number of possible permutations is way larger than the number of keys. Quite often the solution for these kind of questions is to look at what the parts of the equation represent, rather than staring or rearranging the equations themselves. $\endgroup$
    – Maarten Bodewes
    Sep 15 at 11:59
  • 1
    $\begingroup$ If you have $n$ element then you have $n!$ permutations where AES expect to select uniformly $2^{128}, 2^{192}, \text{ or } , 2^{256}$ of them, respect to key size. If you have $n-1$ element since one is fixed then you have $(n-1)!$ of them. So $1/n$ of the permutations doesn't fix the element. Are you sure that your first argument is correct? $\endgroup$
    – kelalaka
    Sep 15 at 20:30
  • $\begingroup$ @kelalaka Right, I think maybe the independence assumption is wrong: given that $k$ maps $m_1$ to $c_1$, the probability that it maps $m_2$ to $c_2$ is slightly larger, since $m_2$ cannot map to $c_1$ (decryption would be ambiguous). But how, then, do we formally show it takes just two pairs of messages? Birthday paradox? $\endgroup$
    – Anon
    Sep 16 at 6:34
  • $\begingroup$ Nice question. It's not the keysize but the size of the keyspace that is $2^{256}$. Similar comment applies for message space. $\endgroup$
    – kodlu
    Sep 20 at 6:35

1 Answer 1

2
$\begingroup$

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.

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