Efficient Construction of Bitsliced DES S-Boxes With Reduced Logical Complexity

This paper presents a heuristic approach to the synthesis of bitsliced representations of S-Boxes of size n ≥ 5, aimed at minimizing the number of typical processor logic instructions (NOT, OR, XOR, AND, ANDN). The proposed approach provides efficient implementation of such representations on a wide range of processor architectures – from resource-constrained 8/16/32-bit microcontrollers to high-performance 64-bit processors of the x86, ARM and RISC-V architectures, in particular on platforms with vector extensions of the instruction set. The method allows adaptation to generate optimized bitsliced descriptions of complex 8×8 S-Boxes, which are common components of modern cryptographic algorithms. The bitsliced descriptions generated using the proposed approach can be used both to improve performance and to increase resistance to attacks through side channels in software implementations of cryptographic primitives, as well as in applied tasks related to password security testing, in particular in utilities for brute- forcing DES-based hashes of Unix passwords.

The developed heuristic approach to minimization of bitsliced representations combines a number of optimization techniques and allows the use of GPU calculations to accelerate the search; as a result, it reduces the total number of logic gates/instructions compared to known approaches with acceptable time costs. In particular, experimental application of the method to S-blocks of the DES cipher demonstrated an average reduction in the number of logical instructions by 3.2 % compared to the best existing solutions.