СИНТЕЗ ПСЕВДО-ДИНАМИЧЕСКИХ ФУНКЦИЙ PD-sbox-ARX-32
Аннотация
Целью работы является разработка метода синтеза оптимальных псевдо-динамических
функций PD-sbox-ARX-32, размерностью 32 бита, в соответствие с противоречивыми требова-
ниями к криптографическим характеристикам, рассматриваемой структуры. Рассмотрены ме-
тоды синтеза классических sbox, в том числе с использованием эволюционного и генетического
методов. Представлены требования к криптографическим характеристикам, как к функциям
PD-sbox, так и к их составным элементам (классические sbox и ARX-функции). Предложен метод
синтеза псевдо-динамических функций PD-sbox-ARX-32, включающий два этапа: 1) эвристический
поиск структуры, соответствующей противоречивым требованиям к результирующим крипто-
графическим характеристикам, потребляемым программным и аппаратным ресурсам, а также
скорости работы представленной функции; 2) поиск оптимальных параметров основного эле-
мента PD-sbox-ARX-32 – ARX-функций, при помощи эволюционного метода, суть которого заклю-
чается в подборе значений циклических сдвигов в ARX-функциях. В результате получен набор че-
тырёх ARX-функций для псевдо-динамического преобразования PD-sbox-ARX-32, имеющего вес
линейных характеристик равный и разностных характеристик равный (при этом эмпи-
рический вес составляет ). Для определения весов криптографических характеристик в рабо-
те применены методы на основе использования SAT-решателей. Приведены выводы о том, что
подобранная структура 32-битной ARX-функции в составе PD-sbox позволяет обеспечить крити-
ческий путь (максимальное количество последовательных операций сложения по модулю ) в
четыре раза меньше чем 8-итерационная 32-битная Alzette-подобная структура, при двухкрат-
ном увеличении количества операций и при сопоставимых максимальных значениях весов разност-
ных и линейных характеристик. Аналогичный результат получается при сравнении 32-битной
ARX-функции с 8-итерационным 32-битным преобразованием из блочного криптоалгоритма
Speck32. Предложенный метод синтеза параметров 32-битной ARX-функции позволяет миними-
зировать количество затрачиваемых ассемблерных инструкций на операции циклического сдвига
при реализации на малоресурсных 8-битных микроконтроллерах AVR (например, ATmega328P).
Литература
Standard, in Computer, June 1977, Vol. 10, No. 6, pp. 74-84. DOI: 10.1109/C-M.1977.217750.
2. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Psevdo-dinamicheskie tablitsy podstanovki:
osnova sovremennykh simmetrichnykh kriptoalgoritmov [Pseudo-dynamic substitution tables: the basis
of modern symmetric cryptoalgorithms], Nauchnoe obozrenie [Scientific Review], 2014, No. 12,
pp. 162-166. Available at: http://www.sced.ru/ru/files/7_12_1_2014/7_12_1_2014.pdf.
3. Polikarpov S.V., Rumyantsev K.E., Prudnikov V.A. Vysokoproizvoditel'naya psevdosluchaynaya
funktsiya pCollapserARX256-32x2 [High-performance pseudorandom function pCollapserARX256-
32x2], XXIV nauchno-prakticheskaya konferentsiya «RusKripto’2022» [XXIV scientific and practical
conference "RusCrypto'2022"], 2022. Available at: https://ruscrypto.ru/resource/archive/rc2022/files/
02_polikarpov_rumyantsev_prudnikov.pdf.
4. Polikarpov S.V., Rumyantsev K.E., Prudnikov V.A. Issledovanie svoystv miniversii psevdo-sluchaynoy
funktsii pcollapser [Study of properties of miniversion of pseudo-random function pcollapser],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2022, No. 6 (230),
pp. 148-162. DOI: 10.18522/2311-3103-2022-6-148-162.
5. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Issledovanie lineynykh kharakteristik psevdodinamicheskikh
podstanovok [Study of linear characteristics of pseudo-dynamic substitutions],
Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 5 (166),
pp. 111-123. Available at: http://izv-tn.tti.sfedu.ru/wp-content/uploads/2015/5/11.pdf.
6. Polikarpov S., Rumyantsev K., Petrov D. Computationally efficient method for determining averaged
distribution of differentials for pseudo-dynamic substitutions, International Conference on Electrical,
Electronics, Materials and Applied Science, AIP Conf. Proc., 1952, eds. V. Rao, A. Ben, S. Bhukya.
Amer. Inst. Phys., 2018, UNSP 020091. DOI: 10.1063/1.5032053.
7. Beierle C. et al. Alzette: A 64-Bit ARX-box, In: Micciancio, D., Ristenpart, T. (eds), Advances in
Cryptology – CRYPTO 2020: Lecture Notes in Computer Science, 2020, Vol. 12172. Springer, Cham.
Available at: https://doi.org/10.1007/978-3-030-56877-1_15.
8. Dinu D., Corre Y.L., Khovratovich D. et al. Triathlon of lightweight block ciphers for the Internet of
things, J Cryptogr Eng., 2019, 9, pp. 283-302. Available at: https://doi.org/10.1007/s13389-018-0193-x.
9. Beierle C., Biryukov A., Cardoso dos Santos L., Großschädl J., Perrin L., Udovenko A., Velichkov V.,
& Wang Q. Lightweight AEAD and Hashing using the Sparkle Permutation Family, IACR Transactions
on Symmetric Cryptology, 2020, 2020(S1), pp. 208-261. Available at: https://doi.org/10.13154/
tosc.v2020.iS1.208-261.
10. Beierle С., Biryukov A., Cardoso dos Santos L. Schwaemm and Esch: Lightweight Authenticated Encryption
and Hashing using the Sparkle Permutation Family. University of Luxembourg, 2019. Available
at: https://sparkle-lwc.github.io/assets/sparkle-specification-latest.pdf.
11. Beyne T. A Geometric Approach to Linear Cryptanalysis, In: Tibouchi, M., Wang, H. (eds), Advances
in Cryptology – ASIACRYPT 2021: Lecture Notes in Computer Science, Vol. 13090. Springer, Cham,
2021. Available at: https://doi.org/10.1007/978-3-030-92062-3_2.
12. Ranea A., Rijmen V. Characteristic Automated Search of Cryptographic Algorithms for Distinguishing
Attacks (CASCADA), IET Information Security, 2022, 16 (6). DOI: 10.1049/ise2.12077. Available at:
https://eprint.iacr.org/2022/513.pdf.
13. Stachowiak S., Kurkowski M., & Soboń A. New results in SAT – cryptanalysis of the AES, 2022 IEEE
16th International Scientific Conference on Informatics (Informatics), 2022, pp. 280-286.
14. Bellini E., Piccoli A.D., Formenti M., Gérault D., Huynh P., Pelizzola S., Polese S., & Visconti A.
Differential Cryptanalysis with SAT, SMT, MILP, and CP: A Detailed Comparison for Bit-Oriented
Primitives, Cryptology and Network Security, 2023.
15. Shi J., Liu G., & Li C. SAT-Based Security Evaluation for WARP against Linear Cryptanalysis, IET
Information Security, 2023.
16. Collard Baudoin & Standaert François-Xavier. Experimenting linear cryptanalysis, Cryptology and
Information Security Series, 2011, 7. 10.3233/978-1-60750-844-1-1.
17. GOST 28147-89 Sistemy obrabotki informatsii. Zashchita kriptograficheskaya. Algoritm
kriptograficheskogo preobrazovaniya [GOST 28147-89 Information processing systems. Cryptographic
protection. Cryptographic transformation algorithm]. Moscow: Standartinform, 1990.
18. Matsui Mitsuru. Linear Cryptoanalysis Method for DES Cipher, Advances in Cryptology -
EUROCRYPT ’93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus,
Norway, May 23-27, 1993, Proceedings, 1993, pp. 386-397. DOI: http://dx.doi.org/10.1007/3-540-
48285-7_33.
19. Biham E., & Shamir A. Differential Cryptanalysis of the Data Encryption Standard. Springer: New
York, 1993.
20. Massacci F., Marraro L. Logical cryptanalysis as a SAT-problem: Encoding and analysis, In Journal
of Automated Reasoning, 2000, 24, pp. 165-203.
21. 8-bit Atmel Microcontroller with 128Kbytes In-System Programmable Flash, ATmega128, ATmega128L.
Rev. 2467X–AVR–06/11. 2011 Atmel Corporation. Available at: http://ww1.microchip.com/ downloads/
en/devicedoc/doc2467.pdf.
