# Matsui's Linear attack on DES P box

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?

• 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. Commented Apr 28, 2015 at 16:18
• 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! Commented Apr 28, 2015 at 18:58
• cs.bilkent.edu.tr/~selcuk/teaching/cs519/Matsui-LC.pdf Enjoy :) (look at page 5) Commented Apr 28, 2015 at 20:06

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

Kiss