Анализ совершенности и сильной нелинейности алгоритмов блочного шифрования

УДК 519.1 Б01 10.17223/2226308Х/11/23

АНАЛИЗ СОВЕРШЕННОСТИ И СИЛЬНОЙ НЕЛИНЕЙНОСТИ АЛГОРИТМОВ БЛОЧНОГО ШИФРОВАНИЯ

А. Р. Мифтахутдинова

Экспериментально исследованы характеристики итеративных алгоритмов блочного шифрования с раундовой подстановкой на базе регистров сдвига (обобщение петли Фейстеля) из классов Я(8, 32, 3), Я(15, 32, 5), Я(16, 32, 5), Я(32, 32, 9) и Я(33, 32,11), где К(и, 32, т) —класс автономных регистров сдвига длины п над множеством векторов У32 с т обратными связями (обобщение петли Фейстеля); п > т ^ 1; Уд — множество двоичных ^-мерных векторов. Исследованы показатели совершенности и сильной нелинейности, определяемые как наименьшее число раундов, после которого произведение раундовых подстановок является совершенным и сильно нелинейным соответственно. Даны эмпирические оценки этих характеристик для некоторых алгоритмов из указанных классов. С использованием результатов сделаны рекомендации по числу раундов шифрования.

Ключевые слова: сильная нелинейность, совершенность, экспонент графа.

К шифрующим подстановкам блочных алгоритмов предъявляется ряд требований, направленных на обеспечение криптографической стойкости шифра. В частности, подстановка должна быть сильно нелинейной (то есть все её координатные функции не должны являться аффинными [1, с. 125]) и совершенной (то есть каждый бит выходного вектора должен существенно зависеть от всех битов входного вектора).

Шифрующая подстановка итеративного Л-раундового алгоритма А блочного шифрования построена как произведение раундовых подстановок = р1... р^, где рг — подстановка ¿-го раунда, г = 1,...,Л. Показателем сильной нелинейности алгоритма А (обозначается еяп А) назовём наименьшее количество г раундов, при котором подстановка д(г) является сильно нелинейной; показателем совершенности алгоритма А (обозначается ерГ А) назовём наименьшее количество г раундов, при котором подстановка д(г) является совершенной, 1 < г ^ Л. Заметим, что данные характеристики у алгоритма А могут не существовать.

Если перемешивающие орграфы раундовых подстановок совпадают и равны Г(д), то величина ерГ А оценивается снизу экспонентом орграфа Г(д) (обозначается ехр Г(д)) [2, с. 101]. Величины еяп А и ерГ А оцениваются сверху с помощью лемм 1 и 2 соответственно.

Обозначим: I(х) —множество номеров единичных компонент вектора х Е "д; д^ — ]-я координатная функция подстановки д множества Уд, ] = 1,... , д. Непосредственно из определений линейности булевой функции и существенной зависимости от переменной следуют леммы 1 и 2 соответственно.

Лемма 1. Пусть для некоторой четвёрки векторов а,Ь, с, е из области определения раундовой подстановки д выполнено д(а ф с) ф д(а) ф д(Ь ф с) ф д(Ь) = е, тогда функция д^ является нелинейной для любого ] Е I(е).

Лемма 2. Пусть а и Ь — соседние по г-й координате векторы, г = 1,... , д, и для раундовой подстановки д выполнено д(а) ф д(Ь) = е, тогда функция д^(х1,... ,хд) существенно зависит от хг для любого ] Е I(е).

В ходе исследований были построены алгоритмы блочного шифрования с раундовой подстановкой на основе регистров сдвига из классов Я(8, 32, 3),Я(15, 32, 5),

Математические методы криптографии

75

R(16, 32, 5), R(32, 32, 9) и R(33, 32,11). Из экспериментально проверенных соображений минимизации экспонента перемешивающего орграфа расположение обратных связей взято равноудалённое или близкое к нему, то есть расстояние между соседними точками съёма близко к n/m.

Приведём для примера h-раундовый алгоритм 512-5 из класса R(16, 32, 5) (h — параметр). На i-м раунде шифрования реализуется подстановка g, зависящая от раундо-вых ключей ,... , q5 G V32. Обозначим через X = (X0,... , X15) входной блок раунда, Xk G V32, 0 ^ k ^ 15. При ключах q1,... , q5 раундовая подстановка множества V512 (рис. 1) задана формулой

g(Xo,...,Xi5) = (Xi,f (S,qi) Ш Х2,Хз ,X4 ,f (S,^) Ш X5, X6, X7, X8, f (S,) Ш X9,

X10, X11, f (S q4) Ш X12, X13, X14, f (S q5) Ш X15, X0) ,

где S = Xo Ш X1 Ш X3 Ш X4 Ш X6 Ш X7 Ш X8 Ш X10 Ш X11 Ш X13 Ш X14; Ш — сложение по модулю 232. Функция f обратной связи совпадает с функцией алгоритма ГОСТ 28147-89.

Рис. 1. Раундовая подстановка алгоритма 512-5

Для оценки показателя сильной нелинейности алгоритма 512-5 генерируем наборы случайных 512-мерных векторов (аъ, съ), £ =1, 2,... , и при г = 2, 3,... , Н вычисляем 4г) = #(г)Ы Ф #(г)(Ь) Ф #(г)(а ф С) Ф д(г) (6ъ 0 с), е(г) е ^512. Если при некотором £ (из вероятностных соображений взято £ ^ 100) вектор е^ V ... V е(г) (покоординатная дизъюнкция) состоит только из единиц, то еяп А ^ г.

Для оценки показателя совершенности алгоритма генерируем наборы случайных 512-мерных векторов, соседних по координате ж^, и при г = 2, 3,... , Н вычисляем значение е(г) = д(г)(аъ) ф д(г)(6ъ), е(г) е ^512. Если при некотором £ ^ 100 результат по-

(г) (г)  < Г1П

координатной дизъюнкции векторов е! ,... , еъ для г = 1,..., 512 состоит только из единиц, то ерГ А ^ г.

С помощью данных экспериментов оцениваем минимальное число раундов, необходимое для обеспечения сильной нелинейности и совершенности алгоритма шифрования. Если при опробовании 100 наборов векторов условие сильной нелинейности или совершенности не выполняется, то делается вероятностный вывод об отсутствии свойства сильной нелинейности и совершенности соответственно.

Для каждого алгоритма — представителя указанных классов вида Я(п, 32, т) — проведено по 20 экспериментов, в ходе которых посчитан ехрГ(д) и получена оценка

показателей сильной нелинейности и совершенности (таблица). Во всех экспериментах полученные оценки совпали для каждого из рассмотренных блочных алгоритмов.

Оценки показателей сильной нелинейности и совершенности

n m expT(g) esn A epf A

8 3 4 3 7

15 5 4 3 7

16 5 7 4 8

32 9 7 4 8

33 11 4 3 6

Таким образом, при равноудалённом (или приблизительно равноудалённом) размещении обратных связей на регистре сдвига:

1) число раундов для достижения алгоритмом сильной нелинейности (еяп А) близко к величине п/т;

2) число раундов для достижения алгоритмом совершенности (ерГ А) не меньше 7 и не больше 27, где 7 = 2 ехр Г(д);

3) число раундов шифрования при синтезе шифров данного класса целесообразно установить не меньше 2ехрГ(д).

ЛИТЕРАТУРА

1. Фомичёв В. М., Мельников Д. А. Криптографические методы защиты информации. Ч. 1.

Математические аспекты: учебник для академического бакалавриата. М.: Юрайт, 2016.

209 с.

2. Фомичев В. М. Оценки экспонентов примитивных графов // Прикладная дискретная математика. 2011. №2(12). С. 101-112.

УДК 519.7 DOI 10.17223/2226308X/11/24

ПРОПОЗИЦИОНАЛЬНОЕ КОДИРОВАНИЕ ПРЯМЫХ И ОБРАТНЫХ РАУНДОВЫХ ПРЕОБРАЗОВАНИЙ В АТАКАХ НА НЕКОТОРЫЕ БЛОЧНЫЕ ШИФРЫ1

И. В. Отпущенников, А. А. Семёнов, О. С. Заикин

Описывается атака на блочные шифры, основанная на известной концепции «встреча посередине». В рамках предлагаемой атаки для решения уравнений криптоанализа используются алгоритмы решения проблемы булевой выполнимости. Основное нововведение заключается в том, что в пропозициональной кодировке шифра учитывается информация не только от прямых, но и от обратных раундовых преобразований. Для ряда сокращённых по числу раундов блочных шифров построены оценки трудоёмкости атак из класса «угадывай и определяй» с использованием нового принципа кодирования. В некоторых случаях новые атаки оказались в разы эффективнее аналогов, в которых используются стандартные методы кодирования.

Ключевые слова: блочный шифр, ГОСТ 28147-89, DES, PRESENT, криптоанализ, задача булевой выполнимости.

1 Работа поддержана грантом РНФ №16-11-10046. Дополнительно И. В. Отпущенников поддержан Ооветом по грантам при Президенте РФ (стипендия №СП-4751.2016.5).