Getting the s-box input from its output in differential cryptanalysis on DES

Question

If we try to get K4 using differential cryptanalysis on 4-variant DES, how can we get the input of a certain S-box if we know it's output?

This seems hard to do since the substitution operation is non-invertable for DES.

Answer 1

In DES cryptanalysis this is in general achieved by trying all 4 possible preimages for the given S-box output.

In particular, for S-box $S_i$ a 6-bit input (say $b_1b_2 ... b_6$) produces a 4-bit output $a_1a_2a_3a_4$. The s-boxes can then be written as a 2-dimensional array of size 4x16. The input bits $b_1b_6$ determine the row of the s-box table and the input bits $b_2b_3b_4b_5$ determine the column. The value of the output corresponding to the 6-bit input is the value at cell $S_i[b_1b_6][b_2b_3b_4b_5]$.

Therefore, given an output $a_1a_2a_3a_4$ there are exactly 4 possible inputs corresponding to this output, one in each row of the array corresponding to S-box $S_i.$

If additional information is available - such as Hamming weights within some side channel attacks - this can be done more efficiently.