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

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

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

Линейный метод анализа:

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

Метод линейного криптоанализа впервые предложен в начале 90-х годов XX века японским ученым М. Матсуи и основывается на том, что существует возможность замены нелинейной функции ее линейным аналогом. Существенным недостатком метода является необходимость в больших объемах данных, зашифрованных на одном и том же секретном ключе, что осложняет практическое применение к вскрытию шифра. Однако, для случая, когда в распоряжении криптоаналитика имеется некий черный ящик (устройство или программа), который позволяет выполнить шифрование любого числа текстов с помощью известного алгоритма шифрования на секретном ключе, не раскрывая при этом самого ключа, применение метода линейного криптоанализа становится вполне перспективным направлением анализа шифра.

Любой алгоритм шифрования в общем виде можно представить как некоторую функцию E, зависящую от входного сообщения Х, секретного ключа К и возвращающую шифрованное сообщение Y:

Y = E(X, K) (1)

Зная само преобразование Е и входное сообщение Х, нельзя однозначно сказать каким будет выходное сообщение Y. В данном случае нелинейность функции зависит от внутренних механизмов преобразования Е и секретного ключа К. М. Матсуи показал, что существует возможность представить функцию шифрования в виде системы уравнений, которые выполняются с некоторой вероятностью р. При этом для успешного проведения анализа вероятность уравнений р должна быть как можно дальше удалена от значения 0,5.

Так как уравнения, получаемые в ходе анализа криптоалгоритма, являются вероятностными, то их называют линейными статистическими аналогами. Линейным статистическим аналогом нелинейной функции шифрования (1) называется величина Q, равная сумме по модулю два скалярных произведений входного вектора Х, выходного вектора Y и вектора секретного ключа К соответственно с двоичными векторами , β и , имеющими хотя бы одну координату равную единице:

(2)

в том случае, если вероятность того, что Q=0 отлична от 0,5 (Р(Q=0)≠0,5).

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

 = |1 – 2р|, (3)

где р – вероятность, с которой выполняется линейный аналог.

Отклонение определяет эффективность линейного статистического аналога. Чем отклонение больше, тем выше вероятность успешного проведения анализа. Фактически отклонение показывает насколько вероятность статистического аналога отдалена от значения р = 0,5.

Для успешного применения метода линейного криптоанализа необходимо решить следующие задачи. Найти наиболее эффективные статистические линейные аналоги. При нахождении аналогов обратить внимание на то, что в них должно быть задействовано как можно больше битов искомого секретного ключа К. Получить статистические данные: необходимый объем пар текстов (открытый – закрытый текст), зашифрованных с помощью анализируемого алгоритма на одном и том же секретном ключе. Определить ключ (или некоторые биты ключа) путем анализа статистических данных с помощью линейных аналогов.

Первый шаг анализа заключается в нахождении эффективных статистических аналогов. Для алгоритмов шифрования, в которых все блоки заранее известны, этот шаг можно выполнить единожды, основываясь на анализе линейных свойств всех криптографических элементов шифра.

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

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

В ходе исследования нами была рассмотрена задача анализа блоков замены и выявления пары векторов , для которых вероятность того, что Q = 0, дает максимальное или близкое к максимальному отклонение.

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

Рисунок 1. Таблица вероятностей для первого блока замены

Полученные таблицы вероятностей для каждого блока замены были проанализированы. Так, например, для первого блока замены (рис. 1) можно выделить двадцать четыре вероятности, для которых отклонение наиболее близко к 1 и равно 0.5 (p = 0.75, p = 0.25), а также девяносто шесть вероятностей, для которых отклонение равно 0.25 (p = 0.375, p = 0.625).

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

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

В рамках исследования будем рассматривать один раунд алгоритма шифрования Магма и иметь в виду допущение, которое заключается в замене операции сложения по модулю на операцию сложения по модулю 2 (XOR). Таким образом, исследуемая упрощенная часть шифра (функция F) представлена на рис. 2.

Рисунок 2. Функция F для первого раунда шифрования

Рассмотрим первый раунд шифрования. На вход алгоритма шифрования поступает 64-х битовое сообщение X, состоящее из двух равных частей. На вход функции F первого раунда шифрования поступает 32-х битовая правая часть входного сообщения . Последовательность входных битов складывается по модулю 2 с первым раундовым подключом (в соответствии с принципом выработки раундовых подключей для шифра Магма первый подключ содержит первые 32 бита исходного секретного ключа K). После сложения с подключом данные разбиваются на группы по 4 бита и поступают на вход соответствующих блоков замены. На рис. 2 показано побитовое представление данных при их прохождении через функцию F первого раунда шифрования. Для того, чтобы определить, какие биты будут получены на выходе каждого из блоков замены, необходимо к последовательности применить операцию циклического сдвига вправо на 11 разрядов.

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

В соответствии с таблицей анализа для первого блока замены (рис. 1) было выявлено несколько пар векторов , для которых вероятность того, что Q = 0, дает максимальное или близкое к максимальному отклонение. Рассмотрим одну из таких пар , для которой .

Для первого блока замены входным сообщением Х является последовательность из четырех битов ; ключ содержит фрагмент из четырех битов ; выходное сообщение содержит в себе биты . С учетом этого раскроем скалярные произведения в формуле :

.

Подставив в вышеприведенную формулу значение векторов , получим линейный статистический аналог:

, (4)

для которого вероятность того, что Q = 0, равна 0,25.

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

Таким образом, мы рассмотрели способы определения линейных статистических аналогов для одного раунда шифрования. Однако для проведения анализа алгоритма шифрования этого не достаточно, так как во всех аналогах в левой части присутствуют неизвестные элементы, а именно значения Y.

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

Рассмотрим один из вариантов объединения линейных аналогов. Для этого возьмем линейный аналог, полученный для первого раунда шифрования. В нем присутствует бит . Обратимся к рис. 3, из которого видно, что сообщение можно получить, сложив по модулю два левую часть входного сообщения X и сообщение B, поступающее на вход функции F второго раунда шифрования. Таким образом, бит можно представить как:

(5)

Рисунок 3. Обозначения входов и выходов трех раундов шифра Магма

Теперь обратимся к третьему раунду шифрования и построим еще один линейный аналог с использованием той же пары векторов , которая была использована для построения первого аналога. Для этого подробно рассмотрим прохождение битов сообщения через функцию F третьего раунда шифрования (рис. 4).

Рисунок 4. Функция F для третьего раунда шифрования

Рассмотрим третий раунд шифрования. На вход функции F третьего раунда шифрования поступает 32-х битовая правая часть выходного сообщения . Последовательность складывается по модулю 2 с третьим раундовым подключом (в соответствии с принципом выработки раундовых подключей для шифра Магма третий подключ содержит 65 – 96 биты исходного секретного ключа K). После сложения с подключом данные разбиваются на группы по 4 бита и поступают на вход соответствующих блоков замены. На рис. 4 показано побитовое представление данных при их прохождении через функцию F третьего раунда шифрования. Для того, чтобы определить, какие биты будут получены на выходе каждого из блоков замены, необходимо к последовательности применить операцию циклического сдвига вправо на 11 разрядов.

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

, (6)

для которого вероятность того, что Q = 0, равна 0,25.

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

(7)

Путем сложения можем объединить аналоги (4) и (6)

(8)

Подставив в формулу (8) формулы (5) и (7), получим:

(9)

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

(10)

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

Слайдовый метод анализа:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть, исходный открытый фиксированный текст представляет собой следующую 64-х битовую последовательность: 0хfedcba9876543210, где 0хfedcba98 – левая часть, а 0х76543210 – правая часть фиксированного текста. При ключе шифрования К = 0хffeeddccffeeddccffeeddccffeeddccffeeddccffeeddcc ffeeddccffeeddcc слайдовой парой к данному фиксированному тексту будет являться следующая 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, является возможность их использования как на специально оборудованном кластере, так и на кластере, состоящем из обычных ПЭВМ, связанных между собой сетью [3, с. 99].

Пожалуй, самой распространенной реализацией MPI является MPICH. Данная реализация разработана исследователями из Аргонской национальной лаборатории США (Argonne National Laboratory, USA). Данная библиотека является свободно распространяемой [3, с. 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

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