# Regarding matsui's Paper on Linear Cryptanalysis of DES

I am going through the the Paper by Matsui on Linear Cryptanalysis of DES. In that, he says

$NS_{5}(16,15)=12$

And then in the next paragraph he says considering the expansion and permutation phases the following equation holds good:

$X(15)\bigoplus F(X,K)[7,18,24,29]=k$

Can somebody help me understand this, because I can't find a relation between the first equation and the second one?

• Please find the paper at www.cs.bgu.ac.il/~crp042/Handouts/Matsui.pdf – Malice Jun 17 '12 at 20:56

## 1 Answer

Let us denote by $x = x_5x_4x_3x_2x_1x_0$, where $x_i \in \{0, 1\}$ the input of a DES S-box and by $y = y_3y_2y_1y_0$, with $y_i \in \{0, 1\}$ its output. Basically, $\mathrm{NS}_5(16, 15) = 12$ means that for S-box #5, the relation $x_4 = y_3 \oplus y_2 \oplus y_1 \oplus y_0$, where $y = S_5(x)$, holds with probability $\frac{\mathrm{NS}_5(16, 5)}{64} = \frac{12}{64} = \frac{1}{2}-\frac{5}{16}$, which is a fairly biased value (one would expect this value to be very close to $\frac{1}{2}$ in an ideal situation).

Starting from this observation, Matsui builds the 1-round linear approximation $X_{15} \oplus F(X, K)_7 \oplus F(X, K)_{18} \oplus F(X, K)_{24} \oplus F(X, K)_{29} = K_{22}$ that holds with the same probability $\frac{1}{2}-\frac{5}{16}$. Note that, for S-box #5, $x_4$ can be traced back to $X_{15} \oplus K_{22}$, taking into account the $\mathrm{EP}(.)$ transformation as well as the key-schedule algorithm, and $y_3y_2y_1y_0$ can be propagated to bits 7, 18, 24 and 29 of the output of the round function, this time taking into account the effect of the bit permutation $\mathrm{P}(.)$.

• Exactly . But I'm looking for is how did he manage the 1 round linear approximation from the $NS_{5}(16,15)$ equation . He did not describe that in the paper and nor can i find it anywhere on internet – Malice Jun 20 '12 at 12:04
• And please note that it's $NS_{5}(16,15)$ not $NS_{5}(16,5)$ . Typo . I've edited the Question – Malice Jun 20 '12 at 12:07
• I have corrected and expanded my answer, hope this is more clear for you now :-) – cryptopathe Jun 20 '12 at 15:52
• Oh My mistake . I's counting bits starting from left handside and was getting a differnt expression,should start counting from right hand side . Spent hours trying to find this .A bucketfull of thanks – Malice Jun 20 '12 at 17:33
• While expanding this Equation to a single round of DES, the Output of the function f is XORed with plain text . How does this equation we're talking about hold true because plain text is of random content but Matsui says this equation holds true $X_{2}[7,8,24,29]\bigoplus P_H[7,18,24,29]\bigoplus P_{L}=K_{1}$ – Malice Jun 20 '12 at 17:58