Компонентная алгебраическая иммунность S-блоков, использующихся в некоторых блочных шифрах | ПДМ. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/21

Компонентная алгебраическая иммунность S-блоков, использующихся в некоторых блочных шифрах

Установлено точное значение компонентной алгебраической иммунности S-бло-ков, которые используются в работе известных блочных шифров. Получено, что такие шифры, как DES, CAST-256, KASAMI, PRESENT не обладают максимальной иммунностью и потенциально являются менее стойкими к алгебраическому криптоанализу.

Component algebraic immunity of s-boxes used in some block ciphers.pdf Известно, что любой шифр можно представить в виде системы булевых уравнений, которые описывают его работу. Данная система строится на основе известного алгоритма шифрования и позволяет связать между собой биты открытого текста, ключа и шифротекста. Решение систем булевых уравнений в общем случае является NP-трудной задачей. Существуют различные алгоритмы решения таких систем, но большинство из них решают только линейные системы либо нелинейные при достаточно низком значении степени уравнений, трудоёмкость нахождения решения в таком случае слишком велика. Подробнее с методами решения систем булевых уравнений можно ознакомиться в [1]. В 2003 г. N. Courtois и W. Meier [2] предложили новый метод криптоанализа шифров, который был назван алгебраическим криптоанализом. Основная его идея заключается в процессе линеаризации булевых систем уравнений и сведении их к уравнениям меньшей степени, решение которых - менее сложная задача. Появление нового вида атаки привело к необходимости исследования свойств булевых функций, наличие которых позволяет затруднить применение данного критоанализа. В 2004 г. W. Meier, E. Pasalic и C. Carlet [3] ввели понятие алгебраической иммунности AI(f) для булевых функций. В частности, было установлено, что высокая алгебраическая иммунность позволяет противостоять алгебраическим атакам. Алгебраической иммуностью AI(f) булевой функции f : Zn ^ Z2 называется минимальное число d, такое, что существует булева функция g степени d, не тождественно равная нулю, для которой fg = 0 или (f ф 1)g = 0. Данное понятие различными способами обобщено на векторный случай. Одним из наиболее естественных обобщений является понятие компонентной алгебраической иммунности, введённое C. Carlet [4]. Компонентной алгебраической иммунностью AIcomp(F) векторной булевой функции F : Zn ^ Z^ называется минимальная алгебраическая иммунность компонентных функций b • F (b Е Z^, b = 0), т. е. Alcomp(F) = min{AI(b • F) : b Е Z™ b = 0}, где b • F = bf ф ... ф bmfm. Наличие высокой компонентной алгебраической иммунности способствует наилучшему противостоянию различным методам алгебраических атак. В [5] установлено, что в случае нечётного n если векторная булева функция обладает максимальной компонентной алгебраической иммунностью, то она является сбалансированной, и построены примеры функций с максимальной компонентной иммунностью для малых значений n, m. Основу блочных шифров составляют S-блоки, которые и являются векторными булевыми функциями. В данной работе проведён анализ компонентной алгебраической иммунности S-блоков, использующихся в различных блочных шифрах. Ниже приведена таблица, в которой указан год создания шифра, его название, размер S-блока, значение компонентной алгебраической иммунности и максимально возможное значение компонентной алгебраической иммунности при данных параметрах n,m. Будем обозначать через n ^ m векторную булеву функцию (S-блок), действующий из Zn в Zm. Год Шифр Размер блока AIcomp(F ) Max 1977 DES 6 ^ 4 2 3 1989 ГОСТ 28147-89 4 ^ 4 2 2 1996 CAST-256 8 ^ 32 2 4 1997 SQUARE 8 ^ 8 2 4 1998 CRYPTON 8 ^ 8 4 4 1998 AES 8 ^ 8 4 4 1998 KASAMI 7 ^ 7 3 4 2006 SM4 8 ^ 8 4 4 2007 PRESENT 4 ^ 4 1 2 2013 FIDES 6 ^ 6 3 3 2015 KUZNYECHIK 8 ^ 8 4 4 Видно, что далеко не все шифры обладают максимальной компонентной алгебраической иммунностью. Такие шифры потенциально являются менее стойкими к алгебраическому криптоанализу.

Ключевые слова

векторная булева функция, компонентная алгебраическая иммунность, S-блоки, DES, AES, PRESENT, KUZNYECHIK, component algebraic immunity, vector Boolean function, S-box, DES, AES, PRESENT, KUZNYECHIK

Авторы

ФИООрганизацияДополнительноE-mail
Покрасенко Денис ПавловичНовосибирский государственный университет студент механико-математического факультетаpokrasenko.d.p@gmail.com
Всего: 1

Ссылки

Агибалов Г. П. Методы решения систем полиномиальных уравнений над конечным полем // Вестник Томского государственного университета. Приложение. 2006. № 17. С. 4-9.
Courtois N. and Meier W. Algebraic attacks on stream ciphers with linear feedback // Eurocrypt 2003. LNCS. 2003. V. 2656. P. 345-359.
Meier W., Pasalic E., and Carlet C. Algebraic attacks and decomposition of Boolean functions // Eurocrypt 2004. LNCS. 2004. V.3027. P. 474-491.
Carlet C. On the algebraic immunities and higher order nonlinearities of vectorial Boolean functions // Enhancing Cryptographic Primitives with Techniques from Error Correcting Codes. Amsterdam: IOS Press, 2009. P. 104-116.
Покрасенко Д. П. О максимальной компонентной алгебраической иммунности векторных булевых функций // Дискретный анализ и исследование операций. 2016. Т. 23. №2. С.88-99.
 Компонентная алгебраическая иммунность S-блоков, использующихся в некоторых блочных шифрах | ПДМ. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/21

Компонентная алгебраическая иммунность S-блоков, использующихся в некоторых блочных шифрах | ПДМ. Приложение. 2017. № 10. DOI: 10.17223/2226308X/10/21