ЗНАХОДЖЕННЯ BITSLICED-ПРЕДСТАВЛЕННЯ ВЕЛИКИХ S-BOXES НА БАЗІ ТЕРНАРНОЇ ЛОГІЧНОЇ ІНСТРУКЦІЇ

DOI: 10.31673/2409-7292.2025.017435

Анотація

Статтю присвячено пошуку евристичних методів знаходження bitsliced-описів великих S-Boxes (n ≥ 6) зі
зменшеною кількістю інструкцій на базі тернарної логічної інструкції, яка є доступною в х86-64 процесорах з
підтримкою SIMD-технології AVX-512 та деяких GPU-процесорах. Одна тернарна інструкція дає змогу замінити
декілька звичайних логічних інструкцій і отже збільшити продуктивність криптографічних алгоритмів, що їх
використовують. Згенеровані запропонованим методом bitsliced-описи дають змогу покращити швидкодію
програмних імплементацій деяких криптоалгоритмів та зменшити їх вразливості до атак по стороннім каналам.
У роботі розроблено евристичний метод мінімізації найпоширеніших 8×8 S-Boxes, в якому завдяки поєднанню
різних технік з використанням GPU-обчислень вдалося зменшити кількість вентилів у bitsliced-описах
порівнюючи з іншими відомими методами при прийнятній тривалості роботи. Розроблено відповідне програмне
забезпечення у вигляді утиліти мовою Python і протестовано її роботу на S-Boxes різноманітних
криптоалгоритмів. Встановлено, що розроблений метод генерує bitsliced-описи з на 15% меншим числом
тернарних інструкцій, порівнюючи з найкращим відомим на сьогодні методом. Також як частковий випадок
розглянуто застосування запропонованого методу для знаходження bitsliced-описів S-Boxes шифру DES (6×4), де
також вдалося на 6% зменшити кількість інструкцій порівняно з найкращим існуючим результатом. Ці описи
дають можливість збільшити швидкодію DES-шифрування і використовуються в утилітах підбору DES-based
хешів Unix-паролів, зокрема, популярній програмі аудиту паролів John The Ripper.
Ключові слова: bitslicing, тернарна логічна інструкція, 8×8 S-Box, DES S-Boxes, CPU, GPU логічна
мінімізація, програмна імплементація, sboxgates, швидкодія.

Список використаних джерел
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).