What do DES S-boxes Say to Each Other ?

Abstract

Abstract. 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 Davies-Murphy 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