Мінімізація BITSLICED-представлення 4×4 S-Boxes на базі тернарної логічної інструкції

Я. Р. Совин; Володимир Васильович Хома; Іван Р. Опірський

Статтю присвячено методам і засобам для генерації програмноорієнтованих bitsliced-описів бієктивних 4×4 S-Boxes зі зменшеною кількістю інструкцій на базі тернарної логічної інструкції. Згенеровані запропонованим методом bitsliced-описи дають змогу покращити продуктивність та безпеку програмних імплементацій криптоалгоритмів, що використовують 4×4 S-Boxes на різноманітних процесорних архітектурах та при проектуванні апаратних засобів шифрування.

У роботі розроблено евристичний метод мінімізації, що використовує тернарну логічну інструкцію, яка доступна в х86-64 процесорах з підтримкою розширення системи команд AVX-512 та деяких GPU-процесорах. Завдяки поєднанню в методі різних евристичних технік (попередніх обчислень, вичерпному пошуку на певну глибину, уточнюючому пошуку) вдалося зменшити кількість вентилів у bitsliced-описах S-Boxes порівнюючи з іншими відомими методами. Розроблено відповідне програмне забезпечення у вигляді утиліти мовою Python і протестовано її роботу на 225 S-Boxes різноманітних криптоалгоритмів. Встановлено, що розроблений метод у 91.1% випадках генерує bitslicedопис із меншим числом тернарних інструкцій, порівнюючи з найкращим відомим на сьогодні методом, реалізованим в утиліті sboxgates.

bitslicing

тернарна логічна інструкція

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.
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.
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.
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.
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.
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.
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.
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]
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.
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.
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.
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.
D. Mercadier, “Usuba, Optimizing Bitslicing Compiler”, PhD Thesis, Sorbonne University, France, p. 195, 2020.
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.
Ya. Sovyn, “Bitsliced 4x4 S-Boxes Ternary Instruction 2023”, 2023. [Online]. Available: https://drive.google.com/drive/folders/1o4GKjb1bIWzHf0H3KmvH--2CxiDNKQmb... [Accessed: 12 October 2023]