Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
There seems to be something missing from your question. $\;$ –  Ricky Demer Nov 20 '13 at 21:30
    
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}$ –  Ricky Demer Nov 21 '13 at 10:36
    
@RickyDemer I am wondering, why do you always use LaTeX code to format your comments? They tend to display rather oddly for me. –  Thomas Nov 21 '13 at 10:47
    
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.) $\;\;\;$ –  Ricky Demer Nov 21 '13 at 10:50
    
Strength - cryptographic resistance of ciphers –  NiceTheo Nov 21 '13 at 11:04
show 1 more comment

1 Answer 1

up vote 2 down vote accepted

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$

share|improve this answer
    
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! –  figlesquidge Nov 21 '13 at 11:50
    
My question isn't so clear, but your answer exactly show what I want. –  NiceTheo Nov 21 '13 at 18:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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