# Problems with Matsui's Linear Cryptanalysis on round reduced DES

I'm trying to understand the known plaintext attack that is briefly explained in the paper Linear Cryptanalysis Method for DES Cipher by Mitsuru Matsui. I've almost understood it (since I'm programming it and it's yielding good partial results) but there are some things I'm not understanding completely.

If I'm not mistaken, for the 4 round attack, Matsui uses a 3 round DES linear approximation, decrypts the final round and expresses that linear approximation using plaintext bits, ciphertext bits and the bits from the $$F(C_R,K_4)$$ being $$C_R$$ the right part of the ciphertext and $$K_4$$ the 4th subkey derived by the DES key schedule. This way, and since only one bit of $$F(C_R,K_4)$$ is used in the expression, only one S-Box affects it, so we can get those 6 bits using Algorithm 2. Furthermore we can get a 7th bit by the right part of the linear expression using Algorithm 2 too. Now we have 7 bits of the 56-bit key, and in order to get 7 more we do the same but instead of decrypting the last round we encrypt the first one, expressing the three remaining rounds with the same linear expression but this time using $$F(P_R, K_1)$$, and that gives us another 7 bits. The problems I'm having are:

1- If I haven't programmed it wrong, at least one bit of the key (after inversing the DES key schedule) is in both of the sets of 7 bits, so it gives us with only 13 (not 14) effective bits of the actual key. Where do I get the 14th bit Matsui says?

2- Even if I get 14 bits, how am I supposed to get the rest of the bits? In the paper he says that "It is easy to deduce the remaining key bits, and we omit the detail", but honestly I have no idea on how to do that beside the obvious way of bruteforcing the 42 bits, that I think it's completely unfeasible.

Any guidance would be welcome.

On 2: Since his attack complexity is larger than $$O(2^{42})$$ this brute force step is negligible, so acceptable. He actually improved his original attack to $$O(2^{43})$$ in a second paper.
Also $$2^{42}$$ encryptions is definitely doable even without special purpose hardware (see comment) these days. Even back then people railed against export restrictions which handicapped ciphers to 40 bits.
• Hi, thanks for your answer. What I did is using the best linear approximation (given by Matsui) of 3 round DES in order to get the key of a 4 round DES encrypted pairs of plaintext and ciphertext. The procedure I'm following is the one explained in section 6 of the paper but for the 3-round expression, getting the 6 bits associated to the first S-Box of $K_4$ and the same for $K_1$. Then, if I trace back those bits to the original key (reversing the DES KS) I get that they overlap, that is, there is a bit of the 6 first bits of $K_1$ that overlaps with one of the 6 first bits of $K_4$. – Cogito Mar 30 at 10:16
• $2^{42}$ executions of a block cipher most certainly do not need special hardware. Indeed, Pascal Junod's SAC 2001 paper On the Complexity of Matsui's Attack gives a runtime on the order of a week for running an attack of similar complexity on full DES on a then standard PC. – Polytropos Apr 1 at 19:44