1. CSN
  2. Всі випуски
  3. Випуск 7, Номер 2, 2025
  4. Підхід до побудови оптимізованих bitsliced-описів DES S-Boxes із мінімізованою логічною складністю

Підхід до побудови оптимізованих bitsliced-описів DES S-Boxes із мінімізованою логічною складністю

CSN.
2025;
Випуск 7, Номер 2
: cc. 206 - 216
https://doi.org/10.23939/csn2025.02.206
Автори:
  1. Я. Р. Совин
  2. М. М. Соколовський
  3. Т. І. Луковський
1
Національний університет «Львівська політехніка», кафедра захисту інформації, Україна
2
Національний університет «Львівська політехніка», кафедра захисту інформації, Україна
3
Національний університет «Львівська політехніка», кафедра захисту інформації, Україна

Наведено евристичний підхід до синтезу bitsliced-представлень таблиць підстановки (S-Boxes) розміром n ≥ 5, спрямований на мінімізацію числа типових процесорних логічних інструкцій (NOT, OR, XOR, AND, ANDN). Запропонований підхід забезпечує ефективну реалізацію таких представлень на широкому спектрі процесорних архітектур – від ресурсно обмежених 8/16/32-бітних мікроконтролерів до високопродуктивних 64-бітних процесорів архітектури x86, ARM та RISC-V, зокрема на платформах зі векторними розширеннями набору команд. Метод допускає адаптацію для генерації оптимізованих bitsliced-описів складних S-Boxes розміром 8×8, які є поширеними компонентами сучасних криптографічних алгоритмів. Згенеровані за допомогою запропонованого підходу bitsliced- описи можуть бути використані як для підвищення продуктивності, так і для посилення стійкості до атак через сторонні канали у програмних реалізаціях криптографічних примітивів, а також у прикладних задачах, пов’язаних із тестуванням безпеки паролів, зокрема в утилітах для перебору DES-based хешів Unix-паролів.
Розроблений евристичний підхід до мінімізації bitsliced-представлень комбінує низку оптимізаційних технік і дає змогу використовувати обчислення на GPU для прискорення пошуку; у підсумку він зменшує загальну кількість логічних вентилів/інструкцій порівняно з відомими підходами за прийнятних затратах часу. Зокрема, експериментальне застосування методу до S-блоків шифру DES продемонструвало середнє зниження кількості логічних інструкцій на 3,2% порівняно з найкращими наявними рішеннями.

bitslicing
S-Box
DES
криптографія
програмна реалізація
логічна мінімізація
продуктивність
  1. Biham, E. (1997). A fast new DES implementation in software. In: Biham, E. (eds) Fast Software Encryption. FSE 1997. LNCS, vol. 1267. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/BFb0052352.
  2. Käsper, E., Schwabe, P. (2009). Faster and Timing-Attack Resistant AES-GCM. In: Clavier, C., Gaj, K. (eds) Cryptographic Hardware and Embedded Systems. CHES 2009. LNCS, vol 5747. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-642-04138-9_1.
  3. Adomnicai, A., & Peyrin, T. (2020). Fixslicing AES-like ciphers. IACR Transactions on Cryptographic Hardware and Embedded Systems, 402–425. DOI: https://doi.org/10.46586/tches.v2021.i1.402- 425.
  4. Matsuda, S., Moriai, S. (2012). Lightweight Cryptography for the Cloud: Exploit the Power of Bitslice Implementation. In: Prouff, E., Schaumont, P. (eds) Cryptographic Hardware and Embedded Systems – CHES 2012. LNCS, vol 7428. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-642-33027- 8_24.
  5. Zhang, J., Ma, M., Wang, P. (2018). Fast Implementation for SM4 Cipher Algorithm Based on Bit- Slice Technology. In: Qiu, M. (eds) Smart Computing and Communication. SmartCom 2018. LNCS, vol. 11344. Springer, Cham. DOI: https://doi.org/10.1007/978-3-030-05755-8_11.
  6. Nishikawa, N., Amano, H., Iwai, K. (2017). Implementation of Bitsliced AES Encryption on CUDA-Enabled GPU. In: Yan, Z., Molva, R., Mazurczyk, W., Kantola, R. (eds) Network and System Security. NSS 2017. LNCS, vol. 10394. Springer, Cham. DOI: https://doi.org/10.1007/978-3-319-64701-2_20.
  7. Schwabe, P., Stoffelen, K. (2017). All the AES You Need on Cortex-M3 and M4. In: Avanzi, R., Heys, H. (eds) Selected Areas in Cryptography – SAC 2016. LNCS, vol. 10532. Springer, Cham. DOI: https://doi.org/10.1007/978-3-319-69453-5_10.
  8. Kwan, M. (2000). Reducing the Gate Count of Bitslice DES. IACR Cryptology ePrint Archive, 51. URL: https://eprint.iacr.org/2000/051.ps [Accessed: 23 May 2025].
  9. Dansarie, M. (2021). Sboxgates: A program for finding low gate count implementations of S-boxes. Journal of Open Source Software, 62(6), 1–3. DOI: https://doi.org/10.21105/joss.02946.
  10. Bitslice DES. URL: https://darkside.com.au/bitslice/ [Accessed: 23 May 2025].
  11. Совин, Я. Р., Опірський, І. Р., & Євенко, Д. А. (2021). Евристичний метод знаходження bitsliced-опису довільних  криптографічних S-Box. Захист інформації, 23(3), 184–194. DOI: https://doi.org/10.18372/2410-7840.23.16407.
  12. Sovyn, Y., Opirskyy, I., & Mykhaylova, O. (2023). Finding a Bit-Sliced Representation of 4×4 S-Boxes based on Typical Logic Processor Instructions. CQPC, 3504, 26–38. URL: https://ceur-ws.org/Vol- 3504/paper3.pdf. [Accessed: 23 May 2025].
  13. Sovyn, Y., Khoma, V., & Podpora, M. (2022). Bitsliced implementation of non-algebraic 8x8 cryptographic S-Boxes using x86-64 processor SIMD instructions. IEEE Transactions on Information Forensics and Security, 18, 491–500. DOI: https://doi.org/10.1109/TIFS.2022.3223782.
  14. Stoffelen, K. (2016). Optimizing S-Box Implementations for Several Criteria Using SAT Solvers. In: Peyrin, T. (eds) Fast Software Encryption. FSE 2016. LNCS, vol. 9783. Springer, Berlin, Heidelberg. DOI: https://doi.org/10.1007/978-3-662-52993-5_8.
  15. Bao, Z., Guo, J., Ling, S., & Sasaki, Y. (2019). Peigen – a platform for evaluation, implementation, and generation of S-boxes. Transactions on Symmetric Cryptology, 1, 330–394. DOI: https://doi.org/10.13154/tosc.v2019.i1.330-394.
  16. Jean, J., & Peyrin, T. (2017). Optimizing Implementations of Lightweight Building Blocks. Transactions on Symmetric Cryptology, 4, 130–168. DOI: https://doi.org/10.13154/tosc.v2017.i4.130-168.