# 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\bigoplus F_5(X,K)[7,18,24,29]=K$

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. – SEJPM Apr 28 '15 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! – jkovba Apr 28 '15 at 18:58
• cs.bilkent.edu.tr/~selcuk/teaching/cs519/Matsui-LC.pdf Enjoy :) (look at page 5) – RyArazi Apr 28 '15 at 20:06

We need to get back to Matsui's notations.

X is represented as X.... X

K is represented as K......K

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

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

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, Y, Y and Y, with Y = Y......Y using Matsui's notation, Y is mine.

If we apply P to Y, P(YYYY) is the permuted output of S5 (that would be P(YYYY) in a "normal DES" representation from left to right) and becomes ZZZZ before expansion for the next round.

Hence the result: X ⨁ Z ⨁ Z ⨁ Z ⨁ Z = K or

X ⨁ Z ⨁ Z ⨁ Z ⨁ Z = K 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

• Please use Tex formatting – yyyy0000 Apr 16 '18 at 11:32