0
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – Cogito
    Mar 30, 2021 at 10:16
  • 1
    $\begingroup$ $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. $\endgroup$
    – Polytropos
    Apr 1, 2021 at 19:44
  • $\begingroup$ But the idea behind Matsui's algorithm on round reduced DES (for example 3 or 4 rounds) is still bruteforcing the rest of the bits after you find 13-14 of them? I know that for the full round DES it is, but I wasn't sure about less rounds $\endgroup$
    – Cogito
    Apr 2, 2021 at 7:42
  • $\begingroup$ yes I believe so. you could try and construct a linear characteristic with enough bias involving the remaining bits, if it exists, I suppose. Maybe worth trying. $\endgroup$
    – kodlu
    Apr 2, 2021 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.