SYNTHESIS OF PSEUDO-DYNAMIC FUNCTIONS PD-sbox-ARX-32
Abstract
The aim of the work is to develop a method for synthesizing optimal pseudo-dynamic functions
PD-sbox-ARX-32, 32-bit in size, in accordance with conflicting requirements for cryptographic characteristics
of the considered structure. The methods for synthesizing classical sbox’es are considered, including
those using evolutionary and genetic methods. The requirements for cryptographic characteristics are
presented, both for the PD-sbox functions and for their constituent elements (classical sbox and ARX functions).
A method for synthesizing pseudo-dynamic functions PD-sbox-ARX-32 is proposed, including two
stages: 1) heuristic search for a structure corresponding to conflicting requirements for the resulting cryptographic
characteristics, consumed software and hardware resources, as well as the speed of operation of the
presented function; 2) search for optimal parameters of the main element of PD-sbox-ARX-32 – ARX functions,
using the evolutionary method, the essence of which is to select the values of cyclic shifts in ARX functions.
As a result, a set of four ARX functions was obtained for the pseudo-dynamic transformation of PDsbox-
ARX-32, having the weight of linear characteristics equal to and difference characteristics equal
to (in this case the empirical weight is ). To determine the weights of cryptographic characteristics,
methods based on the use of SAT solvers were used in the work. The paper concludes that the selected
structure of the 32-bit ARX function in the PD-sbox allows for a critical path (maximum number of sequential
addition operations modulo ) that is four times smaller than that of the 8-iteration 32-bit
Alzette-like structure, with a twofold increase in the number of operations and comparable maximum values
of the weights of the difference and linear characteristics. A similar result is obtained when comparing
the 32-bit ARX function with the 8-iteration 32-bit transformation from the Speck32 block cryptographic
algorithm. The proposed method for synthesizing the parameters of the 32-bit ARX function allows for
minimizing the number of assembler instructions spent on cyclic shift operations when implemented on
low-resource 8-bit microcontrollers AVR (for example ATmega328P).
References
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.
