# weakness of a DES enhancement

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?

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}$.
• @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... – poncho Nov 19 '17 at 23:08