1
$\begingroup$

The following key enhancement to DES was proposed in order to increase the complexity of finding the keys by exhaustive search.

$$\text{DES}^V_{k,k_1}(M)=\text{DES}_k(M)\oplus k_1$$

where the keys’ lengths are $|k|=56$ and $|k_1|=64$ ($k_1$ has the same length as the block length). Show that this proposal do not increase the complexity of breaking the crypto-system using brute-force key search. That is, show how to break these schemes using on the order of $2^{56}\ \text{DES}$ encryptions/decryptions.

You may assume that you have a moderate number of plaintext-ciphertext pairs, $C_i=\text{DES}^V_{k,k_1}(M_i)$.

Let $r$ be the number of pairs indexed from $1$ to $r$.

I define $\forall\ l\in\{0,1\}^{56},\ i\in\{1,\dots,r\}:\text{K}(l,i) = \text{DES}_l(M_i)\oplus C_i$.

My proposal for an adversary is:

for every l of size 56:
     for i = 1,...,n:
          compute K(l, i)
     if for all i != j : K(l,i) == K(l,j)
          return <l,K(l,1)> as the keys of the cryptosystem

It is true that if in some iteration $l=k$ before returning, all the $\text{K}(l,i)$ will be equal to $k_1$ (from the definition of the new crypto-system), so we will return $k,k_1$ as the keys.

But, I think that it is possible that for some $l\neq k$ the $\text{if}$ in the second $\text{for}$ loop will be satisfied since we are checking only a small amount of messages. In such a case if we meet $l$ before meeting $k$ the return of the algorithm will be false.

question

Is it possible to break the crypto-system deterministically with the given complexity, or we must allow some error probability?

$\endgroup$
2
$\begingroup$

Is it possible to break the crypto-system deterministically with the given complexity, or we must allow some error probability?

If we model DES as a random permutation, there is always some probability of either deriving the wrong key, or finding multiple ones.

If we have $n$ plaintext/ciphertext pairs, there is a nonzero probability that there exists a second spurious key that just happens to map each plaintext to the corresponding ciphertext. If our brute force search stops at the first key it finds, it might stop at the wrong one. If our brute force search keeps on going after the first key it finds, it'll find the second one (and hence report multiple).

Now, the actual probability of this happening is tiny; if $n=2$, then the probability in your example would be about $2^{-8}$ (which is small, but not neglicable), however if $n=3$ (which the term "moderate" would appear that we have at least this many), the probability drops to about $2^{-72}$.

In addition, attackers typically aren't that concerned about a small probability of failure. When we protect data, we want to succeed (in this case, be secure) with overwhelming probability; but that's not the case for the attacker...

$\endgroup$
  • $\begingroup$ Thank you. But how do you compute these probabilities? Can you please elaborate more on the probabilities, or just give an intuition. $\endgroup$ – Don Fanucci Nov 19 '17 at 21:13
  • 1
    $\begingroup$ @TrueTopologist: well, on an incorrect key, $K$ acts as a random function. Hence, if we have 2 keys, the probability that $K(l, 1) = K(l, 2)$ is the probability that two random 64 bit numbers are the same; $2^{-64}$. There are $2^{56}-1$ incorrect keys, hence the expectation is $2^{-64}(2^{56}-1) \approx. 2^{-8}$. This isn't precisely correct ($K$ isn't precisely a random function, as the idealization of DES is a random permutation; in addition, the expectation isn't the same as the probability that at least 1 incorrect key validates), but it's close... $\endgroup$ – poncho Nov 19 '17 at 23:08

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.