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 &quot;It is easy to deduce the remaining key bits, and we omit the detail&quot;, 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 1: I have not seen the 14 bit claim disputed. Can you provide more details about how what you did corresponds to his paper and what goes wrong?
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.