5
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ Please use Tex formatting $\endgroup$ – xxx--- Apr 16 '18 at 11:32

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.