HEURISTIC METHOD OF FINDING A BITSLICED DESCRIPTION OF ARBITRARY CRYPTOGRAPHIC S-BOX

Abstract

Bitsliced approach to the implementation of block ciphers combines advantages such as potentially high speed, security and unpretentiousness to computing resources. The main problem in the transition to the bitsliced-description of the cipher is the representation of the S-Box with a minimum number of logical operations. Known methods of minimizing the logical description of the S-Box have a number of limitations, for example, work only with small S-Box, are slow or inefficient, which generally hinders the use of bitsliced-approach. The paper proposes a new heuristic method of bitsliced-description of arbitrary cryptographic S-Box and compares its efficiency with existing methods on the example of S-Box DES cipher. The proposed method is focused on software implementation in the logical basis AND, OR, XOR, NOT, which allows implementation using standard logical instructions on any 8/16/32/64-bit processors. The method uses a number of heuristic techniques, such as, fast algorithms for exhaustive search at shallow depth, flexible procedure for planning the search process, search in depth, etc., which together provide high efficiency and speed. This allows you to adapt it to minimize the 8×8 S-Box, which is very relevant today for many block ciphers, including the domestic cipher "Kalyna". The proposed approach to the bitsliced-description of arbitrary S-Box eliminates the limitations of the known methods of such representation, which restrained the use of the bitcliced-approach in improving software implementations of block ciphers for a wide range of processor architectures.