What do DES S-boxes Say to Each Other ?
The DES encryption standard resisted rather well to some 20 years of massive worldwide cryptanalysis effort. DES S-boxes also haven’t an obvious algebraic structure that could lead to algebraic attacks. For all these reasons, DES is not only very widely implemented and used today, but triple DES and other derived schemes will probably still be around in ten or twenty years from now. We suggest that, if an algorithm is so widely used, its security should still be under scrutiny, and not taken for granted. In this paper we study the S-boxes of DES. Many properties of these are already known, yet usually they concern one particular S-box. This comes from the known design criteria on DES, that strongly suggest that S-boxes have been chosen independently of each other. On the contrary, we are interested in properties of DES S-boxes that concern a subset of two or more DES S-boxes. For example we study the properties related to DaviesMurphy attacks on DES, recall the known uniformity criteria to resist this attack, and discuss a stronger criterion that would allow to resist a larger class of attacks. More generally we study many different properties, in particular related to linear cryptanalysis and algebraic attacks. The interesting question is to know if there are any interesting properties that hold for subsets of S-boxes bigger than 2. Such a property has already been shown by Shamir at Crypto’85 (and independently discovered by Franklin), but Coppersmith et al. explained that it was rather due to the known S-box design criteria. Our simulations confirm this, but not totally. We also present several new properties of similar flavour. These properties come from a new type of algebraic attack on block ciphers that we introduce. What we find is not easily explained by the known S-box design criteria, and the question should be asked if the S-boxes of DES are related to each other, or they follow some yet unknown criteria. Similarly, we also found that the sDES S-boxes have an unexpected common structure that can be exploited in a certain type of generalised linear attack. This fact substantially decreases the credibility of sDES as a DES replacement. This paper has probably no implications whatsoever on the security of DES.