FINDING BITSLICED REPRESENTATIONS OF LARGE S-BOXES BASED ON TERNARY LOGICAL INSTRUCTIONS

DOI: 10.31673/2409-7292.2025.017435

Abstract

The article is devoted to the search for heuristic methods for finding bitsliced descriptions of large S-Boxes (n ≥ 6) with
a reduced number of instructions based on the ternary logical instruction, which is available in x86-64 processors with support
for SIMD technology AVX-512 and some GPU processors. One ternary instruction allows you to replace several conventional
logical instructions and, therefore, increase the performance of cryptographic algorithms that use them. The bitsliced
descriptions generated by the proposed method allow you to improve the performance of software implementations of some
crypto algorithms and reduce their vulnerability to attacks via external channels. The work develops a heuristic method for
minimizing the most common 8×8 S-Boxes, in which, thanks to a combination of various techniques using GPU computing, it
was possible to reduce the number of gates in bitsliced descriptions compared to other known methods with an acceptable
duration of operation. The corresponding software was developed in the form of a Python utility and its operation was tested on
S-Boxes of various crypto algorithms. It was found that the developed method generates bitsliced descriptions with 15% fewer
ternary instructions, compared to the best-known method to date. Also, as a partial case, the application of the proposed method
to find bitsliced descriptions of S-Boxes of the DES cipher (6×4) was considered, where it was also possible to reduce the
number of instructions by 6% compared to the best existing result. These descriptions make it possible to increase the
performance of DES encryption and are used in utilities for selecting DES-based hashes of Unix passwords, in particular, the
popular password audit program John the Ripper.
Keywords: bitslicing, ternary logical instruction, 8×8 S-Box, DES S-Boxes, CPU, GPU logical minimization, software
implementation, sboxgates, performance.

References
1. Biham E. A fast new DES implementation in software. International Workshop on Fast Software Encryption.
1997. C. 260–272. URL: https://doi.org/10.1007/BFb0052352 (дата звернення: 19.02.2025).
2. Kasper E., Schwabe P. Faster and timing-attack resistant AES-GCM. CHES'09: Proceedings of the 11th
International Workshop Cryptographic Hardware and Embedded Systems. 2009. C. 1–17. URL:
https://doi.org/10.1007/978-3-642-04138-9_1 (дата звернення: 19.02.2025).
3. Fixslicing AES-like ciphers: New bitsliced AES speed records on ARM-Cortex M and RISC-V /
A. Adomnicai, T. Peyrin. IACR Transactions on Cryptographic Hardware and Embedded Systems. 2021, №1. С. 402–
425. URL: https://doi.org/10.46586/tches.v2021.i1.402-425 (дата звернення: 19.02.2025).
4. Schwabe P., Stoffelen K. All the AES you need on Cortex-M3 and M4. SAC'2016: Proceedings of the
International Conference on Selected Areas in Cryptography. 2016. C. 180–194. URL: https://doi.org/10.1007/978-3-
319-69453-5_10 (дата звернення: 19.02.2025).
5. Zhang J., Ma. M, and Wang P. Fast Implementation for SM4 Cipher Algorithm based on Bit-Slice Technology.
SmartCom'2018: Proceedings of the International Conference on Smart Computing and Communication. 2018, C. 104–
113. URL: https://doi.org/10.1007/978-3-030-05755-8_11 (дата звернення: 19.02.2025).
6. Nishikawa N., Amano H., and Iwai K. Implementation of bitsliced AES encryption on CUDA-enabled GPU.
NSS'2017: Proceedings of the International Conference on Network and System Security. 2017. C. 273–287. URL:
https://doi.org/10.1007/978-3-319-64701-2_20 (дата звернення: 19.02.2025).
7. Matsuda S., Moriai S. Lightweight cryptography for the cloud: exploit the power of bitslice implementation.
CHES'2012: Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems. 2012.
C. 408–425. URL: https://doi.org/10.1007/978-3-642-33027-8_24 (дата звернення: 19.02.2025).
8. Kwan M. Reducing the Gate Count of Bitslice DES. IACR Cryptology ePrint Archive. 2000(51). URL:
https://eprint.iacr.org/2000/051 (дата звернення 19.02.2025).
9. Bitslice DES. URL: https://darkside.com.au/bitslice/ (дата звернення 19.02.2025).
10. Bitsliced Implementation of Non-Algebraic 8×8 Cryptographic S-Boxes Using x86-64 Processor SIMD
Instructions /Y. Sovyn, V. Khoma, M. Podpora IEEE Transactions on Information Forensics and Security. 2023, № 18.
C. 491–500. URL: https://doi.org/10.28925/2663-4023.2020.7.131152 (дата звернення 19.02.2025).
11. Stoffelen K. Optimizing S-Box Implementations for Several Criteria Using SAT Solvers. FSE'2016:
Proceedings of the 23rd International Conference on Fast Software Encryption. 2016. C. 140-160. URL:
https://doi.org/10.1007/978-3-662-52993-5_8 (дата звернення 19.02.2025).
12. Optimizing Implementations of Lightweight Building Blocks / J. Jean, T. Peyrin. IACR Transactions on
Symmetric Cryptology. 2017, №4. С. 130–168. URL: https://doi.org/10.13154/tosc.v2017.i4.130-168 (дата звернення:
19.02.2025).
13. Peigen – a platform for evaluation, implementation, and generation of S-boxes / Z. Bao, J. Guo, S. Ling,
Y. Sasaki. IACR Transactions on Symmetric Cryptology. 2019, №1. С. 330–394. URL: https://doi.org/10.13154/
tosc.v2019.i1.330-394 (дата звернення: 19.02.2025).
14. Mercadier D. Usuba, Optimizing Bitslicing Compiler. PhD Thesis, Sorbonne University, France. 2020. C. 195.
URL: https://theses.hal.science/tel-03133456v2 (дата звернення: 19.02.2025).
15. Sboxgates: A program for finding low gate count implementations of S-boxes / Dansarie M. Journal of Open
Source Software. 2021. Т. 62, № 6. С. 1–3. URL: https://doi.org/10.21105/joss.02946 (дата звернення: 19.02.2025).