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

В статье освящена проблема анализа стойкости алгоритма шифрования Магма с использованием механизмов слайдовой атаки, показана возможность применения параллельных технологий для реализации поиска слайдовых пар. В ходе исследования получены экспериментальные данные скорости поиска слайдовой пары как для различного числа процессов, работающих на одной ЭВМ, так и для нескольких ЭВМ, работающих в локальной сети. По полученным данным построены и проанализированы графики зависимостей времени от числа процессов. Показано, что поиск слайдовой пары при использовании двух процессов занимает в 1,7 раза больше времени, чем аналогичное вычисление для четырех процессов. Как результат исследований - дана оценка эффективности описанного в статье подхода к поиску слайдовых пар, а также обозначены ориентиры дальнейшего направления развития описанного метода анализа.

Ключевые слова:криптография, слайдовая атака, слайдовая пара, параллельные вычисления, MPI, Магма, ГОСТ 28147-89.

С 2016 года в России в силу вступит новый криптографический стандарт ГОСТ Р 34.12-2015 "Информационная технология. Криптографическая защита информации. Блочные шифры" [1, с. 2]. На сегодняшний день известно, что в его состав войдут два алгоритма шифрования: ныне действующий стандарт шифрования ГОСТ 28147-89 (переименован в «Магма») и новый блочный алгоритм шифрования Кузнечик.

Магма представляет собой симметричный блочный алгоритм шифрования с размером блока входных данных 64 бита, секретным ключом 256 бит и 32 раундами шифрования. Подробнее ознакомиться с работой алгоритма шифрования данных Магма можно в [1, с. 9].

В связи с тем, что шифр «Магма» вошел в состав нового стандарта шифрования, его анализ является актуальной задачей. Исходя из того, что принцип работы шифра «Магма» аналогичен алгоритму работы ГОСТ 28147-89, анализ первого с точки зрения таких популярных методов атак как дифференциальный, линейный и алгебраический криптоанализ изучен достаточно глубоко, в то время как слайдовая атака применительно к данному шифру рассмотрена не так основательно в силу своего относительно недавнего появления. В связи с этим рассмотрение именно слайдовой атаки применительно к шифру «Магма» наиболее актуально.

Метод слайдовой атаки впервые был предложен А. Бирюковым и Д. Вагнером [2, с. 245; 3, с. 589] и основан на гомогенности рассматриваемого шифра. Идея заключается в том, что можно сопоставить один процесс зашифрования с другим таким образом, что один из процессов будет «отставать» от другого на один раунд. Для Магмы это теоретически возможно в 2³² случаях из 2²⁵⁶, когда для зашифрования данных будет использоваться один и тот же раундовый подключ, что возможно, так как в Магме отсутствует функция выработки раундовых подключей. Таким образом, помимо актуальности и современности слайдовой атаки, есть и практический аспект ее применения к шифру «Магма». Подробнее о применении слайдовой атаки можно прочесть в работе [6, с. 43].

Исходя из вышесказанного, целью нашей работы является разработка алгоритма поиска слайдовых пар применительно к алгоритму шифрования «Магма», а также оценка временных характеристик как процесса шифрования, так и самого поиска слайдовых пар.

Решение данных задач предполагает выполнение следующих этапов исследования:

1. Реализация алгоритма шифрования данных «Магма»;

2. Реализация параллельного алгоритма шифрования данных;

3. Разработка и реализация параллельного алгоритма поиска слайдовых пар.

В ходе исследования нами была рассмотрена задача поиска слайдовой пары для случая, когда в алгоритме шифрования Магма используется один и тот же раундовый подключ, который используется в каждом из 32 раундов шифрования. Поиск слайдовой пары путем полного перебора правой части парного текста представлен на рис. 1. Сначала необходимо зафиксировать один текст (входную 64-х битную последовательность) и левую часть парного текста, равную правой (исходной) части фиксированного текста. Правая часть парного текста определяется путем полного перебора. Затем обе входные последовательности для каждой перебираемой правой части парного текста шифруются с помощью блочного алгоритма шифрования Магма. После чего проверяется критерий правильности правой части (что позволяет определить, является ли исходная пара текстов слайдовой парой), а именно: левая часть шифр-текста, полученная для фиксированного текста, должна быть равна правой части шифр-текста, полученной для парного текста, в котором перебирается правая часть.

Рисунок 1. Схема поиска слайдовой пары

В результате был разработан и реализован алгоритм, состоящий из следующих шагов:

1. Зафиксировать один текст (входную 64-х битную последовательность) и левую часть парного текста, равную правой (исходной) части фиксированного текста.

2. Определить правую часть путем полного перебора ее возможных значений (от 0х00000000 до 0хffffffff).

3. Зашифровать фиксированный текст, а также парный текст (с перебираемой на текущем этапе правой частью).

4. Проверить критерий отбора слайдовых пар: левая часть шифр-текста, полученная для фиксированного текста, должна быть равна правой части шифр-текста, полученной для парного текста, в котором перебирается правая часть. Перейти к шагу 2.

5. После полного перебора правой части парного текста сформировать результат о поиске слайдовых пар.

Рассмотрим пример слайдовой пары.

Пусть, исходный открытый фиксированный текст представляет собой следующую 64-х битовую последовательность: 0хfedcba9876543210, где 0хfedcba98 – левая часть, а 0х76543210 – правая часть фиксированного текста. При ключе шифрования К = 0хffeeddccffeeddccffeeddccff

eeddccffeeddccffeeddccffeeddccffeeddcc слайдовой парой к данному фиксированному тексту будет являться следующая 64-х битовая последовательность: 0х7654321028da3b14. Проверим, так ли это. Зашифруем исходный фиксированный текст. Результат зашифрования представляет собой: 0хef04eacbbad969b9. Теперь зашифруем парный текст. Результат зашифрования представляет собой: 0xeb2e2421ef04eacb. Проверим критерии отбора слайдовых пар:

1. Левая часть парного текста равна правой (исходной) части фиксированного текста (0х76543210).

2. Левая часть шифр-текста, полученная для фиксированного текста, равна правой части шифр-текста, полученной для парного текста (0хef04eacb).

После того, как слайдовая пара найдена, перед криптоаналитиком стоит задача поиска самого ключа шифрования. В связи с тем, что в нашем распоряжении имеются, по сути, два текста, шифрование одного из которых, «отстает» от шифрования другого ровно на один раунд, мы можем проанализировать вход функции F и ее выход (правая часть фиксированного текста и правая часть текста с перебираемой правой частью соответственно). Зная выход функции F, мы можем осуществить инверсную сдвиговую операцию (циклический сдвиг битов вправо на 11 разрядов). Затем, используя инверсные S-блоки, получить результат сложения по модулю 2³² с раундовым подключом. Зная этот результат и вход в функцию F, мы можем применить операцию вычитания по модулю 2³², и получить, таким образом, раундовый подключ.

Рассмотрим теперь реализацию параллельного алгоритма с использованием технологии MPI для поиска слайдовых пар текстов, необходимых для проведения слайдовой атаки на алгоритм шифрования Магма.

MPI – это интерфейс передачи сообщений (Message Passing Interface), ориентированный, в первую очередь, на разработку программ для систем с распределенной памятью. По сути, MPI представляет собой библиотеку функций и описания типов данных, предназначенную для распараллеливания программ, написанных на языках программирования Си и Фортран. Средства библиотеки MPI направлены на облегчение взаимодействия (которое сводится к обмену данными и синхронизации) процессов параллельной программы [6, с. 99].

Одним из достоинств программ, разработанных с использованием библиотеки MPI, является возможность их использования как на специально оборудованном кластере, так и на кластере, состоящем из обычных ПЭВМ, связанных между собой сетью [6, с. 99].

Пожалуй, самой распространенной реализацией MPI является MPICH. Данная реализация разработана исследователями из Аргонской национальной лаборатории США (Argonne National Laboratory, USA). Данная библиотека является свободно распространяемой [6, с. 100]. Важным достоинством использования данной реализации является тот факт, что существуют версии данной библиотеки для всех популярных операционных систем. Именно поэтому для выполнения поставленной задачи мы используем пакет MPICH.

Рассмотрим применимость данной технологии к параллельному поиску правых частей парных текстов. В начале работы программы осуществляется шифрование фиксированного текста. После того, как инициализирована библиотека MPI, выполняется функция определения числа процессов size и функция определения рангов (идентификаторов) myrank процесса.

MPI_Init(&argc, &argv);

MPI_Comm_rank(MPI_COMM_WORLD, &myrank);

MPI_Comm_size(MPI_COMM_WORLD, &size);

Затем каждый процесс получает свой диапазон для вычислений, а именно, правую часть парного фиксированному текста. Левая часть парного текста, как упоминалось нами ранее, равна правой части фиксированного текста. Правая часть парного текста программно определяется, как сумма ранга (идентификатора) процесса и числа процессов. Таким образом, правая часть парного текста будет перебираться параллельно всеми процессами в рамках своего диапазона. Тот факт, что каждый процесс имеет свой уникальный ранг, и то, что нумерация ранга начинается с нуля, обеспечит полный неповторяющийся для разных процессов перебор правой части. После того, как процесс обработал и проверил на «слайдовость» текущую правую часть, он увеличивает ее значение на количество процессов. Описанное выше программно реализовано следующим образом:

right_slaid = myrank;

while(right_slaid

Код для цитирования: Скопировать