[Resource Topic] 2003/184: What do DES S-boxes Say to Each Other?

Welcome to the resource topic for 2003/184

Title:
What do DES S-boxes Say to Each Other ?

Authors: Nicolas T. Courtois, Guilhem Castagnos, Louis Goubin

Abstract:

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.
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 if they follow some yet unknown criteria.
Similarly, we also found that the s5DES 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 s5DES as a DES replacement.
This paper has probably no implications whatsoever on the security of DES.

ePrint: https://eprint.iacr.org/2003/184

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .