ПОИСК СЛАБЫХ КЛЮЧЕЙ ДЛЯ АЛГОРИТМА ШИФРОВАНИЯ КУЗНЕЧИК - Студенческий научный форум

VIII Международная студенческая научная конференция Студенческий научный форум - 2016

ПОИСК СЛАБЫХ КЛЮЧЕЙ ДЛЯ АЛГОРИТМА ШИФРОВАНИЯ КУЗНЕЧИК

Красовский А.В. 1, Ищукова Е.А. 1
1Южный Федеральный Университет
 Комментарии
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
В статье приведён теоретически возможный метод поиска периодических подключей для алгоритма шифрования Кузнечик. Такой способ возможен в случае использования слайдовой атаки на шифр. Основой данного описания является математически обоснованные зависимости с простой логикой.

Ключевые слова: Кузнечик, атака, поиск, секретный ключ, раундовый подключ.

Кузнечик – это современный алгоритм шифрования и изучение его параметров, характеристик, устойчивости является важной задачей исследования. Данный шифр построен на основе преобразования SP-сети с 9 раундами и конечным/начальным отбеливанием в зависимости от шифровании/дешифровании. Такое кол-во изменений существенно усложняет задачу для статических методов криптоанализа т.к. усилия атакующего с каждым раундом растут экспоненциально в результате чего применение методов независимых от количества раундов является оправданным решением.

Имея описанную специфику и свойство задачи исследования можно сказать, что метод криптоанализа "скользящей атаки"(Slide Attacks) предложенный А.Бирюковым и Д.Вагнером в 1999 г. применим и приемлем.

Сама слайдовая атака проходит следующим образом. Мы получаем 2n/2 пар открытый–закрытый текст (Pi, Ci), и ищем среди них слайдовые пары [1]. Согласно парадоксу дней рождений, мы ожидаем найти хотя бы одну пару индексов i, i’, такую, что F(Pi) = Pi’ и F(Ci) = Ci’ одновременно выполняются для некоторого ключа. После того, как слайдовая пара найдена, мы можем найти некоторые биты подключа. В том случае, если раундовая функция слабая, мы можем найти весь подключ данного раунда. Для нахождения оставшихся битов секретного ключа необходимо определить следующую слайдовую пару, и с ее помощью провести анализ. Таким образом, достаточно найти всего несколько слайдовых пар для полного определения битов секретного ключа, что и является задачей, стоящей перед криптоаналитиком.

Рассмотрим периодичность формирования подключей. Если рассматривать Кузнечик как гомогенный шифр, то можно получить данные о возможной периодичности подключей. Эту информацию можно рассмотреть, уделив внимание особенности F функций выработки раундовых подключей, где прохождение раунда условными значениями L0 и R0 порождает новые значения L1 и R1. Это отображение обладает свойством биекции, из-за чего при изменении раундовых условий значения L0 и R0 будут порождать иные значения L2 и R2. Раундовой деформацией может служить раундовая константа (рис.1).

Рис.1. – Биекция F функции.

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

Длина периода = 1. Такая выработка является нарушающей принципы работы F функции и недоступна для рассмотрения в рамках слайдовой атаки, т.к. имеются изменения раундовых условий для отрезков Y1, Y2, Y3, Y4 (рис.2).

Рис.2 – Схема с периодом 1

Длина периода = 2. Такая выработка является нарушающей принципы работы F функции и недоступна для рассмотрения в рамках слайдовой атаки, т.к. имеются изменения раундовых условий для отрезков Y1, Y2, Y3, Y4 (рис.3).

Рис.3 – Схема с периодом 2

Длина периода = 3. Такая выработка является нарушающей принципы работы F функции и недоступна для рассмотрения в рамках слайдовой атаки, т.к. имеются изменения раундовых условий для отрезков Y1, Y4 (рис.4).

Рис.4 – Схема с периодом 3

Длина периода = 4. Такая выработка является нарушающей принципы работы F функции и недоступна для рассмотрения в рамках слайдовой атаки, т.к. имеются изменения раундовых условий для отрезков Y1, Y3 и Y2, Y4(рис.5).

Рис. 5 – Схема с периодом 4

Длина периода = 5. Такая выработка не нарушает принципы работы F функции и доступна для рассмотрения в рамках слайдовой атаки т.к. не имеется изменений раундовых условий (рис.6).

Рис.6 – Схема с периодом 5

Все остальные длины периода не вмещаются по количеству ключей и создают неполные циклы, а из имеющихся можно полноценно использовать только период длиной 5 (рис.6).

Рассмотрим возможные способы получения циклических ключей. Основной задачей при использовании слайдовой атаки является нахождение удовлетворяющих условий для возможного использования повторяющихся ключей. Такой поиск можно подкрепить математическими выражениями, описывающими процесс выработки подключей. Так один раунд преобразования можно записать в виде:

Используя описанные формулы в пределах четырёх раундов с возможностью нахождения изначальных параметров (правой части) в конце (повтор), то можно обнаружить строго математическую зависимость между левой и правой частями в виде:

, где – это преобразование обратное , – это константы соответствующих раундов от начала в рамках четырёх раундов (рис.7).

Рис. 7. – Схема четырёх раундов с повтором

Повтор в один раунд приведен на рис. 8, повтор в два раунда приведен на рис. 9.

Следует сказать, что последние две схемы следует использовать осторожно, т.к в повторе двух раундов левая часть представляет собой константу, а в повторе одного раунда левая и правая равна.

Рис.8. – Схема одного раундов с повтором

Рис.9 – Схема двух раундов с повтором

Если брать схемы в длину >= 5 то возникает проблема длины и сложности решения уравнений, из-за чего строгих зависимостей установить, вероятно, нельзя, но можно достаточно просто описать условия выбора правой части, так при повторе в пределах пяти раундов имеем:

где - это константы соответствующих раундов от начала в рамках четырёх раундов

Такое уравнение доступно, если строить прохождения через раунды значений в соответствии с повтором в четыре раунда, как самого наглядного и неограниченного по применению. Ключевым соответствием схем может служить зависимость значений после начала и перед окончанием от одинаковых параметров, т.е(рис.10):

Рис.10 – Схема пяти раундов с повтором

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

Иным способом нахождения ключей, которые могут давать необходимые повторы, может служить перебор входных значений и соответствующих им выходных значений.

Работа выполнена при поддержке гранта РФФИ № 15-37-20007-мол-а-вед.

Библиографический список.

  1. Бабенко Л.К. Ищукова Е.А. Современные алгоритмы блочного шифрования и методы их анализа // Москва, «Гелиос АРВ», 2006. 376 с.

  2. Бабенко Е.А., Ищукова Е.А Применение слайдовой атаки для анализа симметричных блочных шифров // Научный альманах. Технические науки. – ООО «Консалтинговая компания ЮКОМ». - 2015. № 7 (9). С. 596-606.

  3. Бабенко Л.К., Ищукова Е.А., Алексеев Д.М. Разработка и реализация алгоритма поиска слайдовых пар для алгоритма шифрования Магма с использованием технологии MPI // // Научный вестник. Технические науки. – ООО «Консалтинговая компания ЮКОМ». - 2015. №1.

  4. Ищукова Е.А. Разработка алгоритмов оценки стойкости проектного стандарта шифрования ГОСТ с помощью метода слайдового анализа // Научный журнал «Современные наукоемкие технологии». - Издательский Дом «Академия Естествознания». - №12(2). – 2015. – С. 239 – 244.

Просмотров работы: 791