I'm trying to understand Matsui's linear attack on DES and I have something I don't understand in his paper. In his paper he say that:

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

and from that he say that:

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

My problem here are the indices 7,18,24,29 - where did they come from? They are supposed to be the output bits of S5 after the P box but those bits are 17, 32, 24, 26 if I take the P box from wikipedia. Why is that true?

  • $\begingroup$ I'm not sure (and hence this isn't an answer) but it might be the case that this is bit number i (with $i \in {7,18,24,29}$) of feistel function call for round 5. $\endgroup$
    – SEJPM
    Apr 28, 2015 at 16:18
  • $\begingroup$ Sorry RyArazi, can you please point me to the paper you're looking at? If not, would you mind including a picture of it here? Thanks! $\endgroup$
    – jkovba
    Apr 28, 2015 at 18:58
  • $\begingroup$ cs.bilkent.edu.tr/~selcuk/teaching/cs519/Matsui-LC.pdf Enjoy :) (look at page 5) $\endgroup$
    – RyArazi
    Apr 28, 2015 at 20:06

1 Answer 1


We need to get back to Matsui's notations.

X is represented as X[31].... X[0]

K is represented as K[47]......K[0]

In X[15] ⨁ F5(X,K)[7,18,24,29] = K[22]

X[15] is actually the round input before expansion E and is therefore the 4th bit of SBOX 5 with input bits of S5 being x[5]x[4]x[3]x[2]x[1]x[0]. X[15] = x[4] in practise and the key bit is the 23rd from right to left, hence K[22] because the first one is K[0].

Then F5(X,K) = P(S5(X, K)), for which we sum up the 4 output bits. The bits straight out of S5 are Y[15], Y[14], Y[13] and Y[12], with Y = Y[31]......Y[0] using Matsui's notation, Y is mine.

If we apply P to Y, P(Y[15]Y[14]Y[13]Y[12]) is the permuted output of S5 (that would be P(Y[17]Y[18]Y[19]Y[20]) in a "normal DES" representation from left to right) and becomes Z[24]Z[18]Z[7]Z[29] before expansion for the next round.

Hence the result: X[15] ⨁ Z[24] ⨁ Z[18] ⨁ Z[7] ⨁ Z[29] = K[22] or

X[15] ⨁ Z[7] ⨁ Z[18] ⨁ Z[24] ⨁ Z[29] = K[22] as presented by Matsui.

Note 1: X is the input of round R before expansion, Z is the input of round R+1 before expansion

Note 2: it looks like Matsui used the processor's bit order as opposed to standard DES notations


  • $\begingroup$ Please use Tex formatting $\endgroup$
    – hola
    Apr 16, 2018 at 11:32

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.