We are given a variant of DESX, where $ENC(M)= DES_k(M \oplus k_1)$ (keys are 64bits). In DESX effective key length is $119-lb(M)$ according to wikipedia, but I have not found how this is calculated. I know that the effective key length should be less than that, but how do we find the exact length?
-
1$\begingroup$ 56 comes from the original key, 64 from the whitening key, -1 from the fact that we expect to find a key after half the time and I'd suspect the lb(M) to be caused by the mentioned "known-codebook attack" $\endgroup$ – SEJPM♦ Nov 27 '16 at 0:33
$\begingroup$
$\endgroup$
The security of this variant is no better than regular DES. To see this, consider an attacker with access to $\text{ENC}(M) = \text{DES}_k(M \oplus k_1)$ and $\text{DEC}(C) = \text{DES}^{-1}_k(C) \oplus k_1$, its inverse:
- Obtain one (or more) plaintext-ciphertext pair $M, C$;
- Iterate through all $2^{56}$ DES keys;
- For each candidate key $k$, obtain $k_1 = \text{DEC}(C) \oplus \text{DES}^{-1}_k(C) = M \oplus \text{DES}^{-1}_k(C)$;
- For the correct key $k$, $k_1$ is also correct. This can be confirmed by checking against a few known plaintext/ciphertext pairs.
DESX avoids these trivial attacks by making it impossible to obtain $k_1$ without knowing $k_2$, or vice-versa. Hence DESX's security for $56+64+64$ bits of key being only $2^{56 + 64}$ instead of $2^{56 + 64 + 64}$. The paper by Kilian and Rogaway goes into detail on this, but the gist of it is: iterate through $k$ and $k_1$, and get $k_2$ for free, as above.
