ИССЛЕДОВАНИЕ СВОЙСТВ МИНИВЕРСИИ ПСЕВДО-СЛУЧАЙНОЙ ФУНКЦИИ PCOLLAPSER
Аннотация
Целью работы является оценка криптографических свойств семейства псевдо-
случайных функций (PRF) pCollapser на основе исследования свойств её миниверсии
mini_pCollapser_12x12 при использования фиксированных подстановок с предельно низкими
криптографическими свойствами. В качестве элемента сравнения использована минивер-
сия типовой функции на основе SP-сети, содержащая аналогичное количество фиксиро-
ванных подстановок и имеющая аналогичную размерность входа/выхода, равную 12 битам.
Для достижения поставленной цели решались следующие задачи: – определение структу-
ры исследуемых функций и количества раундов; – определение модели формирования фик-
сированных подстановок с предельно низкими криптографическими свойствами; – генера-
ция наборов 6-битовых фиксированных подстановок с предельно низкими криптографиче-
скими свойствами; – включение в исследуемые функции полученных подстановок и опреде-
ление основных криптографических свойств функций – максимальное значение преоблада-
ния для отдельных значений ключей и максимальное усреднённое по всему множеству клю-
чей значение преобладания, максимальное и максимальное усреднённое по всему множест-
ву ключей значение в таблице распределения разностей, алгебраическая степень и алгеб-
раический иммунитет; – анализ полученных результатов. В работе представлены две мо-
дели формирования фиксированных подстановок с предельно низкими криптографическими
свойствами – на основе перемешивания значений ячеек в предварительно заполненной таб-
лице и на основе простейшей ARX-функции (состоящей из операций сложения по модулю,
циклического сдвига и исключающего ИЛИ). Использование фиксированных подстановок с
предельно низкой нелинейностью позволяет оценить, насколько сложной (нелинейной) яв-
ляется исследуемая функция и какой минимальный уровень нелинейности необходим для
эффективного разрушения статистических зависимостей между входными/выходными
данными. Кроме этого, становится ясным возможность применения в качестве нелиней-
ных элементов ARX-функций, зачастую обладающих спорными и явно низкими криптогра-
фическими свойствами, но позволяющих создавать высокоскоростные программные и ап-
паратные реализации. Определено, что миниверсия PRF pCollapser, в отличии от типовой
функции на основе SP-сети, позволяет получить из набора ARX-функций с предельно низ-
кими криптографическими свойствами, качественную нелинейную функцию, учитывая то,
что других нелинейных элементов в pCollapser не представлено. Полученные результаты
отражают наличие принципиальной разницы между PRF pCollapser и типовой PRF на базе
SP-сети, а также подтверждают правильность концепции псевдо-динамических подста-
новок PD-sbox и состоящей из них функции pCollapser в целом.
Литература
funktsiya PCOLLAPSER, obespechivayushchaya ekstremal'nyy parallelizm obrabotki
informatsii [A pseudo-random PCOLLAPSER function that provides extreme parallelism of
information processing], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2019, No. 5 (207), pp. 88-99. DOI: 10.23683/2311-3103-2019-5-8.
2. Raphael Chung-Wei Phan. Mini Advanced Encryption Standard (Mini-AES): A Testbed for
Cryptanalysis Students, Cryptologia, XXVI (4). Swinburne Sarawak Institute of Technology,
2002, pp. 283-306. Available at: https://doi.org/10.1080/0161-110291890948.
3. Bara Hitapuru, Santi Indarjani. Square attack on Mini-AES and Simplified AES using all
variants of active nibble position, AIP Conference Proceedings, 1729, 020007, 2016. Available
at: https://doi.org/10.1063/1.4946910.
4. Bizaki H.K., Mansoori S.D. and Falahati A. Linear Cryptanalysis on Second Round Mini-
AES, 2006 2nd International Conference on Information & Communication Technologies,
2006, pp. 1958-1962. DOI: 10.1109/ICTTA.2006.1684690.
5. Asadini Dwi Ajeng Gemellia, Santi Indarjani. Differential attack on mini-AES, AIP Conference
Proceedings. 1450, 222, 2012. Available at: https://doi.org/10.1063/1.4724144.
6. Sundari Tianingrum, Santi Indarjani. Algebraic attack on Mini-AES algorithm, AIP Conference
Proceedings. 1729, 020003, 2016. Available at: https://doi.org/10.1063/1.4946906.
7. Liu X. When Mini-AES Meets Machine Learning: Practice and Experience, 2020 IEEE International
Symposium on Systems Engineering (ISSE), 2020, pp. 1-5. DOI: 10.1109/ISSE49799.
2020.9272227.
8. Data Encryption Standard (DES). National Institute of Standards and Technology. FIPS Publication,
46-3, 1999.
9. Polikarpov S.V., Rumyantsev K.E., Kozhevnikov A.A. Issledovanie lineynykh kharakteristik
psevdo-dinamicheskikh podstanovok [Investigation of linear characteristics of pseudodynamic
substitutions], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2015, No. 5 (166), pp. 111-123. Available at: http://izv-tn.tti.sfedu.ru/wpcontent/
uploads/2015/5/11.pdf.
10. 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.
11. Kozhevnikov A.A., Polikarpov S.V., Rumyantsev K.E. On differential properties of a symmetric
cryptoalgorithm based on pseudo-dynamic substitutions, Matematicheskie voprosy kriptografii [Mathematical
Issues of Cryptography], 2016, 7:2, pp. 91-102. DOI: https://doi.org/10.4213/mvk186.
12. Biryukov Alex and Léo Perrin. State of the Art in Lightweight Symmetric Cryptography, IACR
Cryptol. ePrint Arch., 2017. (2017): 511.
13. Howard M. Heys. Key Dependency of Differentials: Experiments in the Differential Cryptanalysis
of Block Ciphers Using Small S-boxes, Cryptology ePrint Archive, Paper 2020/1349.
2020. Available at: https://eprint.iacr.org/2020/1349.
14. Nir Y., Langley A. ChaCha20 and Poly1305 for IETF Protocols. RFC 8439. 2018. ISSN: 2070-
1721.
15. Biham Eli, Shamir Adi. Differential Cryptanalysis of DES-like Cryptosystems, J. Cryptology,
1991, Vol. 4, No. 1, pp. 3-72. DOI: http://dx.doi.org/10.1007/BF00630563.
16. 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.
17. Zhenzhen Bao and Jian Guo and San Ling and Yu Sasaki. SoK: Peigen – a Platform for Evaluation,
Implementation, and Generation of S-boxes, Cryptology ePrint Archive, Paper
2019/209, 2019.
18. Adrián Ranea and Vincent Rijmen. Characteristic Automated Search of Cryptographic Algorithms
for Distinguishing Attacks (CASCADA), Cryptology ePrint Archive, Paper 2022/513,
2022. DOI: 10.1049/ise2.12077. https://eprint.iacr.org/2022/513
19. Frederik Armknecht, Claude Carlet, Philippe Gaborit, Simon Künzli, Willi Meier, and Olivier
Ruatta. Efficient computation of algebraic immunity for algebraic and fast algebraic attacks,
In Proceedings of the 24th annual international conference on The Theory and Applications of
Cryptographic Techniques (EUROCRYPT'06). Springer-Verlag, Berlin, Heidelberg, pp. 147-
164. Available at: https://doi.org/10.1007/11761679_10
20. Eichlseder M. et al. An Algebraic Attack on Ciphers with Low-Degree Round Functions: Application
to Full MiMC. In: Moriai, S., Wang, H. (eds), Advances in Cryptology – ASIACRYPT
2020. ASIACRYPT 2020: Lecture Notes in Computer Science, Vol. 12491. Springer, Cham,
2020. Available at: https://doi.org/10.1007/978-3-030-64837-4_16.
