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

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.

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.$$