How does the length of the plaintext affect the cipher strength?

Question

Let the block length 64-bit, 256-bit key, cipher text accordingly - 64 bits. What is the strength of the block cipher, if any unknown attacks, which could reduce its strength. We can only brute force.

Let $M=\{0,1\}^{64}$ be the plaintext space, $C=\{0,1\}^{64}$ be the ciphertext space and $K=\{0,1\}^{256}$ be the keyspace. Then:

$\forall m\in M\ \exists\ k_1,\dots,k_n\in K \colon E(m,k_1)=\dots=E(m,k_n)=c$.

That is, for fixed message and some keys.

How can we use this fact to reduce the cost of a brute force attack?

Answer 1

I'm still a little unsure what your question is, but I'll try and answer what I think you're asking. If it isn't, please clarify your question or comment below.

Let us assume that $E_k$ is an ideal block cipher$^{[1]}$, and so acts like a random permutation of $2^{64}$ elements.

Given $(m,c)\in M\times C$ find $k\in K$ such that $E(m,k)=c$. How long will this take?

In total there are $2^{64}!$ permutations of $2^{64}$ elements, but we are only interested in the ones that map $m$ to $c$. As such, we are actually looking at how many ways there are to permute the remaining elements, so there are $(2^{64}-1)!$ permutations. So, of the $2^{64}!$ permutations we expect $(2^{64}-1)!$ will map $m\to c$, meaning we expect that $\frac{(2^{64}-1)!}{2^{64}!}=2^{-64}$ of keys will be suitable. So, it should take around $2^{64}$ key guesses.

Given $(m,c)\in M\times C$, how many $k\in K$ are there such that $E(m,k)=c$

Since there are $2^{256}$ keys, and we expect to find a suitable $k$ with probability $2^{-64}$ trials, we expect there to be $2^{256-64}=2^{192}$ possible keys.

So, how many trials should it take to find the correct key?

The important thing to notice here is that, no matter how many trials you run, with just one plaintext-ciphertext pair there will still be lots of false positives, and you will have no way of knowing which is correct. The obvious solution to this is to take more $(m,c)$ pairs, but how many? Suppose we have $n$ distinct $(m,c)$-pairs. Then, a false-positive key must fix these $n$ points, leaving it a permutation of $|M|-n$ points. Following the same logic as above, that means the probability of hitting a false-positive key is $$P = \frac{(2^{64}-m)!}{2^{64}!} = \frac{1}{2^{64}\times (2^{64}-1)\times\cdots\times(2^{64}-m+1)} $$ We want $P\ll2^{256}$, since at this point we can reasonably assume that even in all $2^{256}$ keys there isn't a false positive. As such, $5$ pairs would be sufficient.

I leave it to the reader to consider how long such an attack would take$^{[2]}$.

---

1. The assumption on $E_k$ is an ideal cipher is important. For example, the function given below certainly cannot be modelled as a random permutation, but finding a preimage pair $(m,k)$ is trivial for any $c$. $$E(m,k)=\begin{cases} m & k=0 \\0 & k\neq0 \end{cases}$$

2. Hint: If $E(m_1,k)\neq c_1$, then we do not need to calculate $E(m_2,k)\stackrel{?}{=}c_2$. So, how many times do we calculate $E(m_2,k)$? How about $E(m_3,k)\ \dots$