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

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.

| improve this answer | |

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.