Help with linear approximation of DES(I don't understand some part of it )

Question

I will make a presentation about Linear approximation (Matsui's paper 1993 Linear Cryptanalysis Method for DES Cipher ) of DES and I don't understand some parts of it.

Here my questions :

1. In the linear approximation of $S$ boxes we had lemma 1 and it says $NS(a,b)$ is even

   I saw the topic about lemma 1 but I don't understand the explanation either :(

2. On the Same page as lemma 1 we have table 1. I understand the idea of the table and bias etc. but in the table, if we add the values in every row we get 0. I cannot understand the reason for it.

(I have an idea :For example when we add all rows for α=16 we have $$\mathtt{X4=8Y3\oplus8Y2\oplus8Y1\oplus8Y0}$$ and since we multiply with 8 to each bit in the right side we have 0 in the right side so probability of x4 being 0 is 1/2 therefore we had 0 bias)

3. For breaking 16 round DES we are using algorithm 2 but I cannot understand how we get 14 key bits?

4. We are saying the only nonlinear part of the DES is S boxes. By saying linear or nonlinear what we mean is like linearity in functions in mathematics?

5. In algorithm 2 we are applying algorithm for each key candidate. I understand the algorithm but ı don't understand how are we finding these candidate keys.If we are trying all possible candidates then this will make process very long.

And what advantages or disadvantages this nonlinearity give us?

Answer 1

1. Definition: $$NS_a(\alpha,\beta) = \# \{x| 0 \leq x < 64, (\oplus_{s=0}^{5}(x[s] \bullet \alpha[s])) = (\oplus_{t=0}^{3}(S_{a}(x)[t] \bullet \beta[t]))\}$$

Here, $x$ is your input to the S-box, and $S_a(x)$ is the output of the corresponding S-box. $\alpha$ and $\beta$ are the masks. Then, $NS_a(\alpha,\beta)$ is the number of coincidences that exor of input bits masked by $\alpha$ and exor of output bits masked by $\beta$. Take a look at the following example, where $\alpha = 16$ and $\beta = 15$, namely, $\alpha = 010000$ and $\beta = 1111$, and input is $x=011100$ where we consider fifth S-box: $$011100 \xrightarrow{\text{5'th S-box}} 1110$$ $$\oplus_{s=0}^{5}(x[s] \bullet \alpha[s]) = x[4] \bullet \alpha[4] = 1$$ since $\bullet$ is the bitwise 'and' operation, $x \bullet 0 = 0$ and $0 \oplus x = x$. $$\oplus_{t=0}^{3}(S_{a}(x)[t] \bullet \beta[t]) = (S_{a}(x)[1] \bullet \beta[1])\oplus(S_{a}(x)[2] \bullet \beta[2])\oplus(S_{a}(x)[3] \bullet \beta[3]) = 1$$ Then, we increment $NS_a(16,15)$ by 1. If you repeat this for all possible inputs(i.e. $0 \leq x < 64$), $NS_a(16,15)$ turns out to be 12 indeed.

So, we keep $\alpha$ constant while we go through each 64 possible input. Since each input bit would be '1' 32 times, and '0' 32 times, this idea sums up to the fact we would always have 32 1's and 32 0's on the left hand side of the equation. Another way to convince, is just ordering the inputs in Gray code order, and omitting every non-masked bit, and since Gray codes toggle 1 bit at a time, our exor would change for each input, thus we would have 32-32 distribution on the left hand side of the equation. For the right hand side of the equation, the same holds, and we would have 32 zeros and 32 ones. Here, think S-boxes as boxes assigning 32 zeros and 32 ones on the left hand side to 32 zeros and 32 ones on the right hand side, and further assume all zeros are assigned to ones and all ones are assigned to zeros. Then, we slightly change our Sbox, to assign a zero to another zero, which is basically swapping 2 outputs of the Sbox, to align two zeros; which then would imply two ones are also assigned to each other. This is somehow a cumbersome way of explaining it, but when I studied Matsui's attack, I convinced myself this way.

In other words, we have 32 inputs with odd number of 1's and 32 with even number of 1's in it's binary representation. , Then, we have 32 zeros, and 32 ones on the left hand side of the equation. Since for each S-box, there are

2. I think I have an intuitive way to see this, but I should have a look at my notes, I'll try to edit this section as soon as possible.

3. Actually, we get 7 key bits, then reverse the process, i.e. begin decrypting the ciphertext in the reverse order, with reordering round keys and using the same structure to obtain 7 more bits. Here, when we reverse the whole scheme, we obtain another best expression with different masks on plaintext and ciphertext for some specific expressions, -not all of them, as far as I know-, where we can express their characteristic by just changing plaintexts to ciphertexts and ciphertexts to plaintexts in the given linear approximation of DES. So, how to obtain 7 key bits? From algorithm 1, or any n-round expression Matsui gave for an n-round DES, we can obtain 1 bit of information directly. If we introduce (n-1)-round best expression to an n-round DES, as you probably noticed, we are left with an expression in terms of plaintext, ciphertext and $F(X,K)$. making use of the term $F(X,K)$, -note each round key is 48 bits, which is 6 key bits effecting an S-box-, we can recover these 6 key bits. Algorithm 2 is the algorithm for searching these 6 key bits. When you recover 7 bits using Algorithms 1 and 2, just reverse the order, and starting from the ciphertext, start decrypting, and apply the analysis algorithm again to recover another 7 bits.

4. I'm not a mathematician, so I'd rather not talk about "linearity/nonlinearity" in the sense of functions in mathematics, but keep in mind that the linearity of S-boxes add confusion, thus strenghtens it's security, while P-boxes add diffusion, which makes key bits and plaintext bits get in each other as fast and as well as possible.

Note: I'm not an experienced cryptographer, but I'm reading and studying these basic attacks nowadays, if I'm mistaken, I'm sorry.