The paper is devoted to the development of a method for generating bit-slicedbioactive descriptions of 4×4 S-Boxes with a reduced number of logic gates. The bit-sliced descriptions generated by the proposed method can improve the performance and security of software implementations of crypto algorithms using develops a heuristic method for finding a bit-sliced representation that uses 8/16/32/64-bit processors. Due to the combination of various heuristic techniques in the method (previous calculations, exhaustive search to a certain depth, IDDFS algorithm, refinement search), it was possible to reduce the number of gates in SBoxes bit-sliced descriptions compared to other known methods. It has been established that the developed method, in 57% of cases, generates a bit-sliced description with fewer gates compared to the best-known methods implemented in the LIGHTER/Peigen utilities if the standard set of processor logical instructions (AND, OR, XOR, NOT) is used. If the processor additionally supports the AND-NOT instruction, then in 54% of cases, it is also possible to generate a bit-sliced description with a smaller number of gates. Bit slicing, 4×4 S-Box, processor instructions, logical minimization.
The current problem of information protection
is to ensure sufficiently high performance of
cryptographic algorithms (CA) for a wide class of
microprocessor architectures
used in various
applied tasks [
To ensure the high performance of crypto algorithms, various approaches to their software implementation are used: the creation of listed tables operations, (Lookup
Tables,
LUT)
for integration of hardware certain crypto accelerators into the processor (for example, AES-NI in x86 processors), application of SIMD technology. 2, AVX-512 in x86-64 CPU), etc. However, disadvantages consistently these
approaches and
limitations
be
implemented in
have
and
several
cannot
a specific
processors
processor, especially
in
low-end
focused on IoT and embedded systems, which are
characterized by limited resources and computing
capabilities [
Bit slicing [
2023 Copyright for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
implementation (if hardware crypto accelerators
are not used) for various types of processor
architectures [
The main idea of Bitslicing is to convert СA
into a sequence of bit logical operations AND,
XOR, OR, NOT, etc. Each such logical operation
can be represented in processors by a
corresponding instruction, in hardware—by a
corresponding gate. The high speed of software
Bitslicing is achieved since the CPU processes
many cipher elements (bytes, blocks) in parallel,
using fast logical instructions and easier execution
of some operations (for example, bit
permutations, shifts, etc.). The absence of
references to precomputed tables in memory and
cache and the use of simple logical instructions
makes bit-sliced implementations invulnerable to
timing and cache attacks and at the same time
complicates attacks through third-party channels
[
To get the maximum speed, you need to
minimize the number of logical operations
included in the bit-sliced description of the crypto
algorithm. Most cryptographic operations
produce an unambiguous description when going
to a bit-sliced description, or don’t give much
room for minimization except for non-linear
transformations. In СA, nonlinear replacement
operations are given in the form n×m LUT tables,
so-called S-Boxes, preferably having size 4×4 (n
= 4) or 8×8 (n = 8) bit. Tables of 4×4 bits are
characteristic of both lightweight
cryptoalgorithms specially designed for efficient
implementation on resource-limited processors
(e.g. block ciphers PRINCE, LED, Piccolo, hash
functions PHOTON, Spongent) and
generalpurpose crypto algorithms (e.g. block symmetric
ciphers Serpent, Twofish, hash functions
BLAKE, Whirlpool) [
The main problem with the bit-sliced implementation of the CA is to represent the SBox with the minimum possible number of logic gates/instructions. This problem is NP-complete and admits an exact solution only for very simple cases (n ≤ 3 and some n = 4). Therefore, most modern methods and utilities for generating bitsliced descriptions of S-Boxes use heuristic approaches. Given the number of gates, this does not guarantee that the resulting solution is optimal. However, they provide a much better result compared to the universal methods for minimizing logical functions (for example, the Karnaugh map method or the Quine-McCluskey method of simple implicants). Therefore, the problem of finding the optimal bit-sliced representation even for small S-Boxes (4×4) is far from being solved, which requires the search for new heuristic approaches, one of which is presented in our work.
The most difficult stage in the bit-sliced implementation, which largely determines the speed in general, is the logical representation of tables of non-linear substitution of S-Boxes. In the case of hardware implementation, logic gates (Gate Equivalent, GE) {AND, OR, XOR, NOT} act as the logical basis, in software bit-sliced implementation, the gates are replaced by corresponding instructions that are present in most processor architectures. Therefore, in the future, we will use the concepts of valve and instruction as synonyms. It should be noted that some processors do not have the NOT instruction, which is emulated by the XOR instruction. Since the logic instructions of the processor mainly process two operands, the logic elements must also be two-input (Fig. 1) so that one can unambiguously pass from the logical representation to the software one.
CPU instruction and t2, t1, t0 t0
AND
t2 t1 t2 C=Ct1od&et0; Figure 1: The transition from logical to programmatic bit-sliced representation
The bit-sliced approach to cryptographic
representation was first proposed by E. Biham in
[
In [
Lac
a selector combining the functions of five variables. To find the representation of functions of five variables with the minimum number of gates, brute force is used, and the gates are found in the previous steps. Depending on the order in which the search will be performed, there are 6! available options for input variables and 4! options for output variables. This gives a total of 17280 search options, among which the option with the minimum number of gates is selected. As a result, the average number of gates for a bitsliced description of one DES S-Box has decreased from 100 to 56.
M. Kwan’s algorithm with some
improvements is implemented in the form of the
sboxgates utility, which generates a bit-sliced
description for arbitrary S-Boxes up to 8×8
inclusive [
SAT-Solvers programs can be used to minimize S-Boxes. These programs are designed to effectively solve the feasibility problem of Boolean formulas (SATisfiability problem, SAT). The object of the SAT problem is a Boolean formula consisting only of constants (0/1), variables, AND, OR, and NOT operations. The problem is as follows: can all variables be assigned the values False and True so that the formula becomes True? Specialized SAT-Solvers programs, built on efficient solution algorithms, accept a set of equations as input and output the result in the form of SAT if a solution is found and UNSAT if no solution is found. To find a logic circuit with a given number of gates, you can form an equation where the variables specify all possible connections between gates and operations and try to solve them with the help of SAT-Solvers. The advantage of this approach is that if a solution with n gates (SAT) is found and UNSAT is obtained for n – 1 gates, then we are guaranteed to have found the minimum possible bit-sliced description.
In [
Data in Table 1 should be interpreted as follows. For example, for the S-Box of the Piccolo cipher, it was possible to find a bit-sliced representation of ten gates with the help of SATSolvers and to prove that the representation from BGC = 9 does not exist (UNSAT) and, therefore, BGC(Piccolo) = 10. For the S-Box of the Rectangle cipher, it was not possible to represent from BGC = 12, which means that there is no solution with BGC = 10 or 11. For the Minalpher cipher, it was not possible to find bit-sliced descriptions at all, but it was only possible to prove that solutions from BGC = 10 do not exist.
So, the problem with SAT-Solvers is that they don’t always find solutions for “heavy” S-Boxes, such as Minalpher, which may require more than 12–13 gates. For relatively simple S-Boxes with 11–13 gates, SAT-Solvers cannot always prove that the found representation is minimal, as can be seen in the Rectangle example. In addition, the disadvantage of this method is poor scalability: the SAT approach only works for small S-Boxes, up to 5×5 in size, however, for 8×8 S-Boxes, this approach cannot be implemented in terms of computational complexity.
In [
This approach is characterized by all the shortcomings of the previously considered approach: finding the Multiplicative Complexity is also an NP-complete problem that can be solved with the help of SAT-Solvers for relatively simple S-Boxes, poor scalability. In addition, although the solution at each of the two steps is optimal, this does not guarantee that the overall solution is also optimal.
[
The paper [
Generating an optimized bit-sliced CA
implementation requires a significant amount of
time to write and debug code and requires a good
knowledge of processor architecture, low-level
tools, and optimization techniques at the hardware
and software levels. Therefore, in [
The purpose of this paper is to present a method for generating a bit-sliced description of 4×4 S-Boxes, which provides better results compared to existing ones, which will increase the speed and security of hardware and software implementations of a wide range of cryptographic algorithms using S-Boxes of a given type.
Features of S-Boxes representation for bitsliced implementation
In the CA specifications, S-Boxes are preferably defined as LUT. For example, the 4×4 S-Box of the PRESENT cipher has the form shown in Table 2. In Bit-sliced, LUT-Tables are considered logical functions given by truth tables. For example, the S-Box PRESENT cipher will look shown in Table 3.
So, a compact representation of the S-Box in the form of a truth table will look like: S(x) = y, where x = {x0, x1, x2, x3} = {0xff00, 0xf0f0, 0xcccc, 0xaaaa} is input bit-sliced variables, y = {y0, y1, y2, y3} = {0x0ed9, 0x3687, 0xa74c, 0x659a} – the output bit-sliced variables that define a specific substitution table, and the 16-bit numbers that specify x and y will be called vectors.
We are looking at the bit-sliced representation of the S-Box for two typical sets of logical instructions, which are most commonly used in processor command systems:
● Standard set (STD), consisting of instructions NOT, AND, OR, XOR. This instruction set is supported by almost any 8/16/32/64-bit processor and is universal.
● The extended set (EXT), in addition to the instructions of the standard set (NOT, AND, OR, XOR), additionally contains the AND-NOT ( c = a & b ) instruction, which is present in some processors, for example, with the x86-64 or ARM architecture.
The task of searching for a bit-sliced S-Box representation by the BGC criterion can be formulated as follows: given four base vectors base = {x0, x1, x2, x3}, y previous calculations ou need to find the vectors y = {y0, y1, y2, y3} using the minimum number of logical instructions from the given set of STD or EXT.
At the precalculation stage, certain data is found and stored once, which is then repeatedly used in our bit-sliced description search algorithm. This data is of two types:
1. For each 16-bit vector V, BGC (V) is a minimal number of GE valves required to represent it, the so-called “complexity” of the vector.
Since vectors are represented by 16-bit numbers, there are 65536 vectors in total, four of them are base vectors base = {x0–x3} and two are logical constants const = {0x0000, 0xffff} for which BGC is 0, so there are 65530 vectors whose complexity needs to be estimated. In Table 4 shows the found distribution of vectors by their BGC value for the STD and EXT instruction sets. As seen in Table 4, the maximum complexity is 8, which means that any 16-bit vector can be represented with at most 8 gates. This gives an upper bound for the bit-sliced complexity of an arbitrary S-Box described by four vectors y0–y3, equal to 32 gates.
2. Building LUT tables to represent all graphs at a given depth.
Furthermore, LUT tables were built containing all possible combinations that can be formed using a given number of ge operations from the STD/EXT instruction set. These sequences of vectors we shall call called graphs. Tables are formed by sequentially using the GEN_TABLE function, which takes an n×m table as input and returns nnew×(m + 1) table containing all possible combinations formed by a given set of instructions from input table rows.
LUT tables is used in the search algorithm to speed up the selection of candidate graphs in the first step. Thus, for the set of instructions STD, a table q5 was built containing all possible 118491958 graphs to a depth of 6 instructions (ge = 6), and for the set EXT, a table q4 was built containing 21832210 graphs to a depth of 5 instructions (ge = 5). Further construction of the listed tables is impractical since it will require too much memory.
The obtained step-by-step results are presented in the Table 5.
At the top level of the search algorithm, iterates over all values у0-у3, generates each of them from the listed LUT table of the matrix of candidate graphs gri = FIRST_STEP(yi), and passes them to the depth-first search algorithm FIND_BS(gri). The FIND_BS depth-first search algorithm finds the remaining values in an attempt to use a minimum of gates and returns the constructed augmented graph matrices gr0–gr3. From the results obtained, graphs with the minimum BGC value are selected (Fig. 2).
Thus, the search algorithm performs four iterations, starting from different values у. Note this initial value for уstart. At the stage gri = FIRST_STEP(уstart), using the LUT-table q, a matrix of graphs gri, is generated, containing all possible graphs with vector уstar at a certain gate depth dstart. Depending on which BGC group the u-start vector belongs to, heuristically selected dstart values are presented in Table 6 in order to ensure acceptable calculation time and amount of required memory.
y0 y1 y2 y3
STEP_0 STEP_0 STEP_0 STEP_0 gr0 gr1 gr2 gr3
FIND_BS FIND_BS FIND_BS FIND_BS gr0 gr1 gr2 gr3
MIN_BGC grmin
Depending on which BGC group the u-start vector belongs to, heuristically selected d-start values are presented in the Table 6 in order to ensure acceptable calculation time and amount of required memory. If, for example, bgc(y0) = 1, then the graph matrix gr0 after FIRST_STEP will contain all graphs with a length of 6 gates (dstart = 6) in which the vector у0 occurs.
Further, all graphs of the candidate in gri are sorted into three groups: gr_1y, gr_2y, gr_3y with the same number of vectors in each group graph are 1, 2, and 3, respectively. Note this number y_find. Further, the search is carried out for each non-empty group separately in accordance with Fig. 3.
FIND_BS
FIND_NEXT gr0
FIND_NEXT gr
gr gr
ESTIMATE_DEPTH dmin GEN_DEPTH y_find += 1 y_find == 4 Yes gr dstart gr gr_1y y_find = 1 gr_2y y_find = 2 gr_3y y_find = 3
The FIND_NEXT algorithm searches уі, ui one by one until all four values у0-у3 are found. The graph matrix gr is given as an input in the form of an n×m table, each row of which contains y_find values from the set {у0–у3}. Each row of the table stores m vectors explicitly and vectors х0–х3 implicitly.
First, the minimum distance dmin is estimated for group gr, at which the nearest unfound value уx is located among all graphs ESTIMATE_DEPTH. For this, the fast FAST_FIND function of comprehensive forward search to a given depth of 1/2/3/4 steps has been developed. The search and selection of options are carried out using the algorithm of depth-first search with iterative deepening—Iterative Deepening Depth-First Search (IDDFS).
If in the set gr at all search depths (1/2/3/4) not a single value ух is found (dmin ≥ 5), then a step forward is made and a new table of size nnew×(m + 1), is generated from the table gr using the GEN_TABLE function, after which the search is repeated, etc. (Fig. 4). After the estimate dmin ≤ 4 is found, using the GEN_DEPTH algorithm, the transition is made from the set of graphs from y_find = n_y to the set of graphs from y_find = n_y + 1.
gr
FAST_FIND gr = GEN_TABLE(gr)
ESTIMATE_DEPTH gr dmin dmin < 5
No
Yes gr, dmin
For each of the gr groups, the graphs are selected to find the values of dmin and for the grmin group, run ahead gr = GEN_TABLE(grmin). For the generated set gr, the graphs with the known values d = dmin – 1 are selected again, for them to fight ahead and so far, until d becomes equal to 0. After that, only those graphs are selected into the group, to avenge n_y + 1 value y. These steps are repeated until all the у values are found.
The FIND_BS algorithm at each step estimates the minimum distance dmin, at which the nearest value of уx is located, and generates the corresponding graphs. As shown in Fig. 5 this route starts with graphs containing ya, generated using FIRST_STEP, from which the nearest value yb is located at a distance of dab gates then we go to yс located at the minimum distance dbc from yb and at the distance dcd we find the last vector yd.
However, the movement with minimal steps along the trajectory from the vector ya to yd does not always give the optimal result in general (although this is the case in most cases). There may be a situation where the choice of the minimum value of d in the first steps leads to large values of d in the following steps and, as a result, to a non-optimal logical representation. For example, let's assume that in the first step we got dab = 1, in the second dbc = 4, and in the third dcd = 3, that is, the route will be a total of 8 gates (Fig. 5), but it is possible that if in the first step, we followed a different route and graphs with dab = 2 were selected, then in the second step we could find the value of ус with dbc = 3 and in the third yd with dcd = 2, and we would get a shorter total route with 7 valves. Consequently, the second route resulted in a bit-sliced representation with a lower BGC value.
ya dab=1
yb ya yb dbc=4 yc yc dcd=3 yd yd dab=2 dbc=3 dcd=2 Figure 5: Finding the bit-sliced description for different routes
In order to take into account different possible routes in the search algorithm, refining searches are carried out according to the scheme presented in Fig. 6. If we have a set of graphs containing 3 out of 4 possible values of y, then the search for the fourth value is always carried out at the minimum possible depth dmin (SEARCH_3Y). For graphs with two values in у (y_find = 2), the third value is searched for by two routes: dmin and dmin + 1, after which the SEARCH_3Y search is applied to the found graphs with y_find = 3. For graphs with one value in у (y_find = 1), the search for the second value takes place along three routes: dmin, dmin + 1 and dmin + 2, after which the SEARCH_2Y search is applied to the found graphs with y_find = 2. 3.2
The method proposed in the work was implemented in the Python language, and to ensure speed, the main data processing functions are implemented based on the numpy and pyopencl libraries. gr_3y y_find = 3 (ya, yb, yc) dmin yd
gr_2y y_find = 2 (ya, yb) dmin yc dmin+1 yc -SEARCH_3Y SEARCH_3Y
gr_1y y_find = 1 (ya)
SEARCH_1Y dmin yb dmin+1 yb dmin+2 yb
SEARCH_2Y SEARCH_2Y SEARCH_2Y
To evaluate our algorithm, 225 4×4 S-Boxes
of various cryptographic algorithms were taken.
We used the open-source projects LIGHTER and
PEIGEN to obtain a BGC score for selected
SBoxes and compare it with our results. Bit-sliced
descriptions of S-Boxes obtained by our method
are available at the link [
The results are presented in Table 7. Column data in the table should be interpreted as follows:
LUT is a tabular representation of the S-Box, where the line ‘0123456789abcdef’ should be understood as S(x) = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
BSL representation of S-Box in bit-sliced format. The line ‘0ed9_3687_a74c_659a’ should be understood as follows: y0 = 0x0ed9, y1 = 0x3687, y2 = 0xa74c, y3 = 0x659a.
CY is BGC of vectors у0–y3. The line ‘6285’ should be interpreted as: BGC(y0) = 6, BGC(y1) = 2, BGC(y2) = 8, BGC(y3) = 5.
R is the results, contain the BGC value obtained using the method described in the article.
L/P contains the BGC value obtained using the
LIGHTER/PEIGEN utilities [
S-Boxes that have a higher BGC value compared to the one obtained by our method are marked in red, and those that have the same BGC value as our results are marked in yellow. S-Box Piccolo Piccolo-1
Lac
Prost Rectangle Rectangle-1 Minalpher
SKINNY TWINE
PRINCE Lucifer_S0 Lucifer_S1 PRESENT PRESENT-1
JH_S0
JH_S1 Iceberg_S0 Iceberg_S1
Luffa Noekeon Hb1_S0 Hb1_S1 Hb1_S2 Hb1_S3 Hb1_S0-1 Hb1_S1-1 Hb1_S2-1 Hb1_S3-1 Hb2_S0
LUT
STD R
In general, as the results in Table 7, our method showed better results than the LIGHTER/PEIGEN utilities for both the STD and EXT instruction sets. It provides a bit-sliced description with fewer gates for 129 S-Boxes out of 225 (57.3%) using the standard processor logic instruction set and for 123 S-Boxes out of 225 (54.7%) using the extended instruction set. The total number of gates for the bit-sliced description of all 225 S-Boxes in our method is less by 5.0% and 4.3% for the STD and EXT instruction sets, respectively.
The LIGHTER/PEIGEN utilities did not generate a bit-sliced description with fewer instructions for any S-Box than obtained by our method, and the maximum difference in the number of instructions for an S-Box description is 3 and 2 for the STD and EXT sets, respectively.
It should also be noted that the developed method for ‘simple’ S-Boxes (BGC ≤ 12) generates the smallest possible description indicating the same results as those obtained using SAT-Solvers.
The paper presents a method for generating a bit-sliced description of arbitrary 4×4 bijective SBoxes, focused on software implementations on any 8/16/32/64-bit processors that support AND, OR, XOR, NOT, AND-NOT instructions. To date, the method proposed in the paper is the most effective method known to us according to the BGC criterion, which is confirmed by the research results presented in the work. The method combines heuristic techniques at various stages of searching a bit-sliced representation, in particular: recalculation, exhaustive search to a depth of up to four gates, IDDFS algorithm for searching and cutting options, and refining search. If necessary, the developed approach can be adapted to support additional logical instructions.