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


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[22]$

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

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

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}(.)$.

  • $\begingroup$ 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 $\endgroup$ – Malice Jun 20 '12 at 12:04
  • $\begingroup$ And please note that it's $NS_{5}(16,15)$ not $NS_{5}(16,5)$ . Typo . I've edited the Question $\endgroup$ – Malice Jun 20 '12 at 12:07
  • $\begingroup$ I have corrected and expanded my answer, hope this is more clear for you now :-) $\endgroup$ – cryptopathe Jun 20 '12 at 15:52
  • $\begingroup$ 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 $\endgroup$ – Malice Jun 20 '12 at 17:33
  • $\begingroup$ 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}[15]=K_{1}[22]$ $\endgroup$ – Malice Jun 20 '12 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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