Minimization of BITSLICED-representation of 4×4 s-Boxes based on ternary logic instruction

2023;
: pp. 103 - 113
1
Lviv Polytechnic National University, Lviv, Ukraine
2
Lviv Polytechnic National University, Lviv, Ukraine
3
Lviv Polytechnic National University, Ukraine, Department Information Security

The article is devoted to methods and tools for generating software-oriented bitsliced descriptions of bijective 4×4 S-Boxes with a reduced number of instructions based on a ternary logical instruction. Bitsliced descriptions generated by the proposed method make it possible to improve the performance and security of software implementations of crypto-algorithms using 4×4 S-Boxes on various processor architectures and when designing encryption hardware.

The paper develops a heuristic method of minimization using a ternary logical instruction, which is available in x86-64 processors with support AVX-512 instruction system extension and some GPU processors. Thanks to the combination of various heuristic techniques (preliminary calculations, exhaustive search to a certain depth, refining search) in the method, it was possible to reduce the number of gates in bitsliced descriptions of S-Boxes compared to other known methods. The corresponding software in the form of a utility in the Python language was developed and its operation was tested on 225 S-Boxes of various cryptoalgorithms. It was found that the developed method generates a bitsliced description with fewer ternary instructions in 91.1% of cases, compared to the best known method implemented in the sboxgates utility.

  1. E. Biham, “A fast new DES implementation in software,” in International Workshop on Fast Software Encryption, 1997, pp. 260–272. DOI: https://doi.org/10.1007/BFb0052352.
  2. E. Kasper and P. Schwabe, “Faster and timing-attack resistant AES-GCM,” in Proc. 11th International Workshop Cryptographic Hardware and Embedded Systems, 2009, pp. 1–17. DOI: https://doi.org/10.1007/978-3- 642-04138-9_1.
  3. A. Adomnicai and T. Peyrin, “Fixslicing AES-like ciphers: New bitsliced AES speed records on ARM-Cortex M and RISC-V,” IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(1), pp. 402–425. DOI: https://doi.org/10.46586/tches.v2021.i1.402-425.
  4. P. Schwabe and K. Stoffelen, “All the AES you need on Cortex-M3 and M4,” in International Conference on Selected Areas in Cryptography, 2016, pp. 180–194. DOI: https://doi.org/10.1007/978-3- 319-69453-5_10.
  5. J. Zhang, M. Ma, and P. Wang, “Fast implementation for SM4 cipher algorithm based on bit- slice technology,” in International Conference on Smart Computing and Communication, 2018, pp. 104– 113. DOI: https://doi.org/10.1007/978-3-030-05755-8_11.
  6. N. Nishikawa, H. Amano, and K. Iwai, “Implementation of bitsliced AES encryption on CUDA- enabled GPU,” in International Conference on Network and System Security, 2017, pp. 273–287. DOI: https://doi.org/10.1007/978-3-319-64701-2_20.
  7. S. Matsuda and S. Moriai, “Lightweight cryptography for the cloud: exploit the power of bitslice implementation,” in International Workshop on Cryptographic Hardware and Embedded Systems, 2012, pp. 408–425. DOI: https://doi.org/10.1007/978-3-642-33027-8_24.
  8. M. Kwan, “Reducing the Gate Count of Bitslice DES”, IACR Cryptology ePrint Archive, 2000 (51). Available from: http://fgrieu.free.fr/Mattew%20Kwan%20-%20Reducing%20the%20Gate% 20Count%20of%20Bitslice%20DES.pdf [Accessed: 03 October 2023]
  9. K. Stoffelen, "Optimizing S-Box Implementations for Several Criteria Using SAT Solvers", in Proc. 23rd International Conference on Fast Software Encryption, 2016, pp. 140-160. DOI: https://doi.org/10.1007/978-3-662- 52993-5_8.
  10. N. Courtois, T. Mourouzis, and D. Hulme, "Exact logic minimization and multiplicative complexity of concrete algebraic and cryptographic circuits", International Journal On Advances in Intelligent Systems, Vol. 6, No. 3 and 4, pp. 165–176, 2013.
  11. J. Jean, T. Peyrin, S. Sim, J. Tourteaux, “Optimizing Implementations of Lightweight Building Blocks”, IACR Transactions on Symmetric Cryptology, 2017(4), 130-168. DOI: https://doi.org/10.13154/tosc.v2017.i4.130-168.
  12. Z. Bao, J. Guo, S. Ling, and Y. Sasaki, “Peigen – a platform for evaluation, implementation, and generation of S-boxes,” IACR Transactions on Symmetric Cryptology, pp. 330–394, 2019. DOI: https://doi.org/10.13154/ tosc.v2019.i1.330-394.
  13. D. Mercadier, “Usuba, Optimizing Bitslicing Compiler”, PhD Thesis, Sorbonne University, France, p. 195, 2020.
  14. M. Dansarie, “sboxgates: A program for finding low gate count implementations of S-boxes”, Journal of Open Source Software, 6(62), 2021, pp. 1-3. DOI: https://doi.org/10.21105/joss.02946.
  15. Ya.  Sovyn,  “Bitsliced  4x4  S-Boxes  Ternary  Instruction  2023”,  2023.  [Online].  Available: https://drive.google.com/drive/folders/1o4GKjb1bIWzHf0H3KmvH--2CxiDNKQmb... [Accessed: 12 October 2023]