Extended Analysis of DES S-boxes

For more than three decades, the Data Encryption Standard (DES) was one the most widely used cryptographic algorithms. It is still the dominating block cipher for banking applications. The DES was designed by IBM, verified by NSA and published by the National Bureau of Standards as a US Federal Information Processing Standard (FIPS) in 1977. The algorithm itself was fully public but the complete design criteria were only revealed by Coppersmith in 1994. He states that the IBM team was aware of differential cryptanalysis; the DES S-boxes are chosen to satisfy eight design criteria in order to resist this powerful attack. In their 1982 book, Meyer and Matyas state that the DES S-boxes were chosen so that they can be implemented with a minimum number of logic circuits. They mention that for an early design, in which not all of the design criteria are satisfied, the number of minterms varies between 40 and 48. However, for the final design the number of minterms is either 52 or 53, which is the smallest possible number that satisfies all the design criteria. Our research attempts to validate the IBM claims by generating a large number of candidate DES S-boxes satisfying specific criteria and by evaluating their number of minterms.