Алгоритм шифрования магма реферат

Обновлено: 02.07.2024

Метод невозможных дифференциалов как криптоанализ блочных шифров, разработанный в 1998 г. Эли Бихамом, Эди Шамиров и Алексом Бирюковым. Его закономерности и идея. Описание симметричного блочного шифра Магма в новом российском стандарте шифрования.

Рубрика	Программирование, компьютеры и кибернетика
Вид	статья
Язык	русский
Дата добавления	24.03.2019
Размер файла	84,0 K

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

Анализ усеченного алгоритма Магма+ при помощи метода невозможных дифференциалов

Совсем недавно вступил в силу ГОСТ Р 34.12 2015 в нем описаны два алгоритма шифрования, Кузнечик с длиной текста n=128 и Магма с длиной текста равной n=64. Магма является изменённой версией ГОСТ 28147-89 с фиксированными блоками замены и нуждается во всестороннем анализе.

Метод невозможных дифференциалов - метод криптоанализа блочных шифров разработанный в 1998 году Эли Бихамом, Эди Шамиров и Алексом Бирюковым. Метод применялся к таким шифрам как IDEA, AES, Khufu и Khafre, Skipjack, MISTY и KASUMI, S-AES [1 - 5].

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

Симметричный блочный шифр Магма описан в новом российском стандарте шифрования ГОСТ Р 34.12 2015. Шифр построен на основе сети Фейстеля и имеет 32 раунда и раундовую функцию состоящую из трех преобразований: побитовый сдвиг на 11 позиций влево, замена при помощи S-блоков, и сложение по модулю 2. Но анализ будет проводится над измененным алгоритмом Магма, в котором операция сложения по модулю 2 заменена на побитовое сложение по модулю 2.

Для анализа необходимо посмотреть, как меняется разность двух текстов после прохождения F-блока. Будем рассматривать разности в полубайтах, а не в отдельных битах. В общем случае можно сказать, что разность в полубайте N после прохождения F-блока может дать разность в N+2 и N+3. Но для анализа будем использовать особенность, найденную Ищуковой Е.А и Калмыковым И.А в [7], в шестом S-блоке, суть которой заключается в том, что при разности ДА=9, после прохождения S-блока у разности ДС младший бит всегда будет равен 0. Это значит, что после прохождения F-блока, разность затронет 1 полубайт. Зная эти особенности можно построить дифференциальную схему для восьми раундов представленную на рисунке 1. На схема синий цвет - разность между текстами равна 9, красный цвет - неизвестно есть ли разность, черный цвет - разность есть, белый цвет - разности нет.

Рисунок 1. Схема для 8 раундов

дифференциал шифрование магма криптоанализ

Анализ будет проводится на алгоритме шифрования Магма, в котором операция сложения с подключом осуществляется по модулю 2 и усеченного до восьми раундов. Процесс отбрасывания неправильных ключей происходит следующим образом: тесты с разностями в первом полубайте левой половины и с разностью равной 9 в шестом полубайте правой половины шифруется, из них оставляются только те, которые после 8 раундов не имеют разности в шестом полубайте левой половины и третьем и четвёртом полубайте правой половины. Затем, начинается перебор ключей, перебирается только шестой полубайт ключа, остальной ключ можно зафиксировать. Мы заново шифруем оставшиеся тексты одним раундом, но те ключи, которые после этого раунда приводят к разности текстов только в шестом полубайте правой половины равную девяти являются неверными и отбрасываются.

АЛГОРИТМ ШИФРОВАНИЯ МАГМА: ОЦЕНКА КРИПТОСТОЙКОСТИ ШИФРА С ИСПОЛЬЗОВАНИЕМ ЛИНЕЙНОГО И СЛАЙДОВОГО МЕТОДОВ АНАЛИЗА

Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF

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

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

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

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

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

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

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

Отклонение определяет эффективность линейного статистического аналога. Чем отклонение больше, тем выше вероятность успешного проведения анализа. Фактически отклонение показывает насколько вероятность статистического аналога отдалена от значения р = 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 для первого раунда шифрования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть, исходный открытый фиксированный текст представляет собой следующую 64-х битовую последовательность: 0хfedcba9876543210, где 0хfedcba98 – левая часть, а 0х76543210 – правая часть фиксированного текста. При ключе шифрования К = 0хffeeddccffeeddccffeeddccffeeddccffeeddccffeeddcc ffeeddccffeeddcc слайдовой парой к данному фиксированному тексту будет являться следующая 64-х битовая последовательность: 0х7654321028da3b14. Проверим, так ли это. Зашифруем исходный фиксированный текст. Результат зашифрования представляет собой: 0хef04eacbbad969b9. Теперь зашифруем парный текст. Результат зашифрования представляет собой: 0xeb2e2421ef04eacb. Проверим критерии отбора слайдовых пар:

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

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

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

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

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

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

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

3. Бирюков А., Вагнер Д. Слайдовые атаки // Труды быстрого программного шифрования. – 1999. – № 1636. – С. 245-259.

4. Бирюков А., Вагнер Д. Расширенная слайдовая атака. Достижения в криптологии // Еврокрипт. – 2000. – № 1807. – С. 589-606.

5. Бабенко Л.К., Ищукова Е.А., Сидоров И.Д. Параллельные алгоритмы для решения задач защиты информации. – М.: Горячая линия Телеком, 2014. – 304 с.

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

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

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

Ранее был проведен анализ блоков замены для алгоритма шифрования Магма. С результатами анализа можно ознакомиться в работе [2]. В ней показано, как, используя линейные свойства S-блоков замены, строить статистические аналоги для одного раунда шифрования. В результате, для первого блока замены для пары векторов
(α, β) = (1101, 0001), получим линейный статистический аналог:

(1)

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

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

(2)

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

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

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

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

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

Слайдовая атака
с одним раундовым подключом

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

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

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

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

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

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

Рис. 3. Схема поиска слайдовой пары
для одного подключа

Для проведения эксперимента в локальную сеть были объединены девять ЭВМ (каждая из которых использует для вычислений два ядра), после чего был протестирован разработанный алгоритм. Результаты измерений времени поиска слайдовых пар для каждого из процессов представлены в таблице.

1. Бабенко Л.К. Ищукова Е.А. Сидоров И.Д. Параллельные алгоритмы для решения задач защиты информации. – М.: Горячая линия Телеком, 2014. – 304 с.

3. Ищукова Е.А. Разработка и исследование алгоритмов анализа стойкости блочных шифров методом дифференциального криптоанализа // Диссертация на соискание ученой степени кандидата технических наук. – Таганрог, 2007. – 207 с.

5. Biham E., Biryukov A., Shamir A. Cryptanalysis of Skipjack Reduced to 31 Rounds using Impossible Differentials // Advances in Cryptology – EUROCRYPT ‘99. Prague: Springer-Verlag. P. 12–23.

6. Biham E., Biryukov A., Shamir A. Miss in the Middle Attacks on IDEA, Khufu, and Khafre // 6th International Workshop on Fast Software Encryption (FSE 1999). Rome: Springer-Verlag. P. 124–138.

Алгоритм шифрования Магма представляет собой блочный алгоритм шифрования, построенный по схеме Фейстеля. Ранее этот шифр был известен как ГОСТ 28147-89. Однако с 1 января 2016 года он вошел в состав нового стандарта симметричного блочного шифрования ГОСТ Р.34.12 – 2015 под названием Магма [4]. Единственное отличие шифра Магма от шифра ГОСТ 28147-89 заключается в том, что теперь у этого шифра зафиксированы блоки замены. Магма преобразует 64-битовые блоки данных и использует при шифровании 256-битовый ключ, что сразу значительно повышает стойкость данного алгоритма к методу полного перебора. Ранее для алгоритма ГОСТ 28147-89 блоки замены не являлись фиксированным элементом и могли быть выбраны произвольным образом. Считается, что даже при выборе слабых блоков 32 раундов алгоритма шифрования ГОСТ будет достаточно для того, чтобы обеспечить требуемую стойкость. Известны блоки замены, которые использовались в приложении для Центрального Банка РФ, однако до сих пор нет каких-либо сведений об анализе алгоритма даже с имеющимися известными данными. Отдельно стоит отметить, что буквально два месяца назад в нашей стране был утвержден новый стандарт шифрования данных ГОСТ 34.12-2015, который вступает в силу с 1 января 2016 года. Данный стандарт содержит два алгоритма шифрования, одним из которых является алгоритм шифрования ГОСТ28147-89, для которого зафиксированы блоки замены. Ранее в диссертационной работе Е.А. Ищуковой рассматривались дифференциальные свойства для алгоритма шифрования ГОСТ 28147-89 как с известными блоками замены, так и с блоками замены, выбранными произвольным образом [3]. В настоящей работе мы в первую очередь рассмотрим блоки замены, выбранные для нового стандарта ГОСТ Р34.12-2015. После этого уделим особое внимание разработке универсального алгоритма поиска невозможных дифференциалов. В данной работе будет рассмотрен алгоритм Магма, в котором операция сложения по модулю 232 заменена на побитовое сложение по модулю 2. Однако при этом будут рассмотрены дифференциальные свойства операции сложения по модулю 232 и рассмотрен способ перехода от операции сложения по модулю 2 к операции сложения по модулю 232.

На рис. 1 представлены общая схема алгоритма шифрования и содержимое функции F.

Рис. 1. Общая схема шифрования и содержимое функции F

Как отмечалось выше, шифр Магма имеет фиксированный вид блоков замены, приведенный в табл. 1.

В рамках Summer of Hack 2019 в Digital Security я разбирался с атакой по энергопотреблению и работал с ChipWhisperer.

Что это?

Анализ энергопотребления — это один из видов атак по сторонним каналам. То есть атак, использующих информацию, которая появляется в результате физической реализации системы.

Какая информация может быть полезна атакующему:

время выполнения криптопреобразований;
энергопотребление;
электромагнитные поля;
шум и т.д.

Атака по энергопотреблению считается наиболее универсальной.

Почему работает?

В основе микропроцессоров, микроконтроллеров, RAM и многих других логических схем лежит технология КМОП (CMOS). Потребляемая мощность КМОП-схем состоит из двух составляющих: статической и динамической. Статическое энергопотребление очень мало, что является одной из причин монополизации технологии. Динамическая мощность обусловлена переключением транзисторов и зависит от обрабатываемых данных и выполняемых операций. Поскольку статическая составляющая в основном постоянна, изменение общей мощности обусловлено исключительно динамической мощностью и, следовательно, общее энергопотребление может быть использовано для анализа.

Инструментарий

ChipWhisperer, я использовал версию с 2 частями:

ChipWhisperer – это набор инструментов с открытым исходным кодом для исследования безопасности embedded устройств. Он позволяет проводить анализ энергопотребления и атаки на основе ошибок.

Плата обойдется в $250. Разработчики позиционируют ее как революционное решение, ведь подобные комплексы, по заявлению создателей, стоят от $30k. Устройство состоит из 2 плат: целевой и платы захвата.

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

У ChipWhisperer есть отличная вики, небольшие лабы для освоения, а к 5 версии даже сделали хорошую документацию по API. Трассы снимаются с подключенного устройства с помощью их ПО и записываются как NumPy массив.

Для начала необходимо написать прошивку для целевого устройства. В рамках лаб рассматриваются шифры AES, DES, TEA. Для них есть уже готовые прошивки и настройки для снятия трасс (количество отсчетов для снятия, смещение, частоту АЦП и др.). Для самостоятельного исследования настройки придется подбирать экспериментально.

Как уже сказано выше, можно спровоцировать сбой целевой платы: вызывая неисправности тактового сигнала, пропускать инструкции и извлекать секретную информацию.

В больших комплексах для снятия трасс используют осциллограф.

Анализ

Существует несколько основных методов анализа:

простой анализ мощности(SPA);
дифференциальный анализ мощности(DPA);
корреляционный анализ мощности(CPA).

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

Или можно увидеть раунды шифрования на трассах. Для получения ключа данных мало, но можно предположить, какой алгоритм выполняется. На рисунке отчетливо видно 10 раундов AES.

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

В основе корреляционного анализа – статистический аппарат для определения секретного ключа шифрования. Иногда его выделяют в отдельный тип, иногда относят к DPA. Этот метод требует меньшего количества трасс, чем DPA, я использовал его для анализа мощности. Расскажу о нем подробнее.

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

Одна из моделей мощности, которая может быть использована – модель веса Хэмминга. Вес Хэмминга – это количество ненулевых значений в двоичном представлении. Предположение этой модели в том, что количество битов, устанавливаемых в регистре, будет коррелировать с потребляемой устройством энергией. Сам вес Хэмминга используется в дальнейшем как условная единица энергии. Также используется модель расстояния Хэмминга — количество различных битов в 2 значениях.

Для сравнения модели веса Хэмминга и реального энергопотребления используется линейный коэффициент Пирсона. Он показывает линейную зависимость одной величины от другой. При правильно построенной модели данный коэффициент будет стремиться к 1.

Обобщенный алгоритм CPA состоит из следующих основных шагов:

В итоге ключ восстанавливается последовательно, по небольшим частям. Если атакуем один байт ключа за раз, то используем 2 8 попыток для каждого ключа. Например, если ковырять AES — 128, то общее количество попыток для 16 байт ключа будет 2 12 , что намного лучше, чем бить в упор 2 128 .

Анализ шифра Магма

Магма – это шифр, который определен в ГОСТ Р 34.12-2015, по факту тот же самый ГОСТ 28147-89, только в профиль. Шифруемый блок проходит 32 раунда, в которых происходят некоторые преобразования. Ключ состоит из 256 бит, каждый раундовый ключ представляет собой часть исходного.

Анализировать полученные данные будем с помощью метода CPA.

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

Вычисление модели энергопотребления для последнего байта ключа:

где функция leak, просто возвращает выход S-box последнего байта.

Рассчитываем линейный коэффициент Пирсона для моделируемого и реального значения по формуле:

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

Таким образом анализируется каждый байт раундового ключа.

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

В процессе решения поставленной задачи возникает несколько нюансов. В отличие от шифров AES, DES, Кузнечик, сложение раундового ключа с открытым текстом происходит по модулю 2 32 . Сложение младших битов влияет на старшие, в отличие от XORa. При расчете каждого следующего подключа приходится учитывать результаты прошлого. Аналогично и с раундовыми ключами. Данные очень чувствительны. При неправильном расчете одного из значений дальнейший расчет всего ключа будет неправильным.

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

Учитывая все вышесказанное, на выходе имеем следующий скрипт для анализа трасс энергопотребления для шифра Магма:

Выводы

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

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

Читайте также: