weakness of a DES enhancement

Question

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?

Answer 1

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