3
$\begingroup$

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

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

Improve this question
$\endgroup$
1
  • $\begingroup$ Please find the paper at www.cs.bgu.ac.il/~crp042/Handouts/Matsui.pdf $\endgroup$
    – Malice
    Commented Jun 17, 2012 at 20:56

1 Answer 1

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • $\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
    Commented Jun 20, 2012 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
    Commented Jun 20, 2012 at 12:07
  • $\begingroup$ I have corrected and expanded my answer, hope this is more clear for you now :-) $\endgroup$
    – cryptopathe
    Commented Jun 20, 2012 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
    Commented Jun 20, 2012 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
    Commented Jun 20, 2012 at 17:58

Your Answer

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

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