# How can DES have 6x4 S-Boxes and still be reversible?

Wouldn't data be lost when mapping 6-bit values to 4-bit values in DES's S-Boxes? If so, how can we reverse it so the correct output appears?

• This is probably a very interesting question, but I would try to make it more self-contained so that you can obtain a decent answer. Try to provide more background information. – Dave Clarke Oct 29 '10 at 13:01
• While Sadeq has an answer, it would still be useful to clarify the question. Firstly, what is an S-Box in DES ? – Suresh Venkat Oct 29 '10 at 17:16
• A Feistel-based cipher splits the input into two equal-length bit strings $L$ and $R$ (32 bits in DES) and then repeatedly applies the operation Sadeq describes below (in DES, it's iterated 16 times). In DES, an $S$-box is a 6-bit to 4-bit function which is a component of the implementation of $F$. The $S$-boxes had some interesting statistical properties, the purpose of which remained obscure for fifteen years. Many people suspected they made DES easier to break. Eventually, it was discovered these properties of the S-boxes made DES resistant to differential cryptanalysis. – Peter Shor Oct 29 '10 at 20:50
• @Suresh: Classic ciphers are divided into two types: Substitution ciphers (like Caesar), and permutation ciphers (like Columnar transposition). Later, it became evident that neither type provided enough security. Modern block ciphers make use of both transformations. In particular, they have P-boxes (=Permutation boxes), and S-boxes (=Substitution boxes). – M.S. Dousti Oct 30 '10 at 3:59
• @Suresh: I absolutely agree with you. While S-Boxes are famous for cryptographers, I believe the OP should ask the question in a way that it benefits everyone, not a small portion of the community. – M.S. Dousti Oct 30 '10 at 10:02

DES is a Feistel-based cipher. In such ciphers, the function $\rm F$ need not be invertible. Here's the reason:

In each round, the following operation is applied:

For $i =0,1,\dots,n$

$L_{i+1} = R_i$

$R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$

Decryption is performed as follows:

$R_{i} = L_{i+1}$

$L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$

As you can see, the decryption does not need $\rm F$ to be invertible. (Since the decryption does not need to compute $\rm F^{-1}$.)

See Chapter 5 of the textbook "Introduction to Modern Cryptography" by Katz and Lindell.

Without going into all the mathematical mumbo-jumbo about Feistel (which I don't yet 100% understand), if you look at this image from Wikipedia:

You can see that although the 8 s-boxes are indeed compressing 48 bits down to 32, only 32 bits of entropy are coming from the plaintext, therefore you can get the other 16 bits from the key when decrypting, which is the magic performed by previous mentioned Feistel functions.