1. CSN
  2. All Volumes and Issues
  3. Volume 4, Number 1, 2022
  4. Method and utility for minimizing bitsliced representations of 4×4 S-boxes

Method and utility for minimizing bitsliced representations of 4×4 S-boxes

CSN.
2022;
Volume 4, Number 1
: pp. 131 - 146
https://doi.org/10.23939/csn2022.01.131
Authors:
  1. Yaroslav R. Sovyn
  2. Volodymyr Khoma
  3. Ivan Opirskyy
1
Lviv Polytechnic National University, Lviv, Ukraine
2
Opole University of Technology
3
Lviv Polytechnic National University, Ukraine, Department Information Security

The article is devoted to methods and tools for generating bitsliced descriptions of bijective 4×4 S-Boxes with a reduced number of gates/instructions. Bitsliced descriptions generated by the proposed method make it possible to improve the security and performance of both software implementations of cryptoalgorithms using 4×4 S-Boxes on various processor architectures, as well as FPGA and ASIC based hardware.

The paper develops a heuristic method of minimization that uses standard logical instructions AND, OR, XOR, NOT, which are available in most 8/16/32/64-bit processors. Due to the combination of different heuristic techniques (preliminary calculations, exhaustive search to a certain depth, DFS algorithm, 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 is found that the developed method generates a bitsliced description with a smaller number of gates in 57 % of cases compared to the best known methods implemented in the LIGHTER/Peigen utilities.

bitslicing
4×4 S-Box
CPU
logical minimization
software implementation
speed
  1. Biham E. «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. Kasper E. and Schwabe P. «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. Adomnicai A. and Peyrin T. «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. Schwabe P. and Stoffelen K. «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. Zhang J., Ma M., and Wang P. «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. Nishikawa N., Amano H., and Iwai K., «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. Matsuda S.and Moriai S. «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. Kwan M. «Reducing the Gate Count of Bitslice DES”, IACR Cryptology ePrint Archive, 2000 (51). URL: http://fgrieu.free.fr/Mattew  %20Kwan   %20-   %20Reducing   %20the   %20Gate   %20Count   %20of   %20Bitslice%20DES.pdf [accessed: 24 October 2022].
  9. Dansarie M. «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.
  10. Stoffelen K. «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.
  11. Courtois N., Mourouzis T. and Hulme D. «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.
  12. Jean J., Peyrin T.,. Sim S, Tourteaux J. «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.
  13. Bao Z., Guo J., Ling S. and Sasaki Y. «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.
  14. Ya. Sovyn, «Bitsliced sbox», 2022. [Online]. URL: https://drive.google.com/drive/folders/ 1Ae5lXvzhBcVAEq3VaB8lZvFL-gy_B4ZH?usp=sharing [accessed: 24 October 2022].