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?

  • $\begingroup$ There seems to be something missing from your question. $\;$ $\endgroup$
    – user991
    Commented Nov 20, 2013 at 21:30
  • $\begingroup$ You seem to be missing my point. $\:$ Your second sentence should have something corresponding to $\hspace{.56 in}$ the last part of "if x, which is likely, then y", although it doesn't actually need to use the word "then". $\hspace{.42 in}$ "What is the strength of the block cipher, if any unknown attacks, which could reduce its strength", $\:$ ... . $\hspace{.38 in}$ $\endgroup$
    – user991
    Commented Nov 21, 2013 at 10:36
  • $\begingroup$ @RickyDemer I am wondering, why do you always use LaTeX code to format your comments? They tend to display rather oddly for me. $\endgroup$
    – Thomas
    Commented Nov 21, 2013 at 10:47
  • $\begingroup$ I try to line-up the lines and space-out the sentences. $\;$ (For some reason, it occasionally changes how they render a few minutes after I post them.) $\;\;\;$ $\endgroup$
    – user991
    Commented Nov 21, 2013 at 10:50
  • $\begingroup$ Strength - cryptographic resistance of ciphers $\endgroup$
    – NiceTheo
    Commented Nov 21, 2013 at 11:04

1 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$

  • $\begingroup$ Please feel free to correct minor errors - if you find a major one you're welcome to put a big warning at the top of the answer. I won't be offended and it should stop anyone else following my errors! $\endgroup$ Commented Nov 21, 2013 at 11:50
  • $\begingroup$ My question isn't so clear, but your answer exactly show what I want. $\endgroup$
    – NiceTheo
    Commented Nov 21, 2013 at 18:12

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.