Fast Generation of DES-Like S-Boxes

Abstract

The Substitution Boxes (or S-boxes) are tabulated permutations given in the definition of different symmetric encryption methods. In particular, the Data Encryption Standard (DES) includes 8 S-boxes that have been analyzed in depth in the literature. Some of the design criteria used for the choice of these maps have been published. The generation of maps that satisfy these criteria is not a trivial task, in particular because some of them are not easy to find in a random sample. This is specially true for the criterion (S-4), that is satisfied by only a small set of permutations. In this paper this criterion is analyzed in depth and a generator of S-boxes that satisfy it is given. This generator is very effective and can generate a huge amount of S-boxes per second. Using them, other criteria can be analyzed and verified with higher probabilities.