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

В данной работе в разделе 1 описан шифр Кузнечик, в разделе 2 говорится о используемых свойствах шифра, в разделе 3 описан DFА и детали его применения, в разделе 4 описывается алгоритм применения DFA к Кузнечику.

Раздел 1. Структура шифра Кузнечик.

ГОСТ 34.12-2015 “Кузнечик” является блочным симметричным шифром. Он реализован в соответствии с SP сетью, где процесс дешифрования обратен шифрованию. Вход/выход и промежуточные значения имеют размерность 128 бит, ключ имеет размерность 256 бит. Далее все незатронутые детали описания шифра являются не важными для DFA и приведены в [1].

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

Блоки замены имеют входную/выходную размерность 128 бит. Обозначим логическое разбиение 128-ми битного текста на 16 байт как , . Схематичное представление блоков приведено на рисунке 1.

Рисунок 1. Блоки .

Блок имеет размерность входа/выхода 128/8 бит соответственно. Выход генерируется в соответствии с уравнением . Умножение у сложение происходят в поле , где .

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

Блок имеют размерность входа/выхода 128 бит. Они используют соответственно последовательно 16 раз.

Процесс шифрования/дешифрования отображаются формулой (1) соответственно. Обозначим как закрытый текст и как открытый текс, тогда шифрования/дешифрования можно представить:

Ключ шифра имеет размерность 256 бит, а подключ 128 бит. Генерируется 10 подключей для 9 раундов и заключающего блока. Для выработки подключей используется 32 постоянных продекларированных в стандарте значений .

Раздел 2. Свойства шифра Кузнечик.

Основным свойством шифра Кузнечик для DFA является дифференциальное свойство (ДС) блока, а так же блока. Данное положение обусловлено характером метода. DFA предполагает сравнение промежуточных значений и дифференциалов различных ПЗ.

Блоки обладают свойством дистрибутивности, что упрощает их использование относительно DFA. Блоки обладают ДС блоков . При изучении ДС блоков было выявлено, что разные дифференциалы входов образуют разное количество уникальных выходных дифференциалов. Данное ДС для уникальности обозначим как свойство неравномерности распределения (СНР). Далее рассматривается СНР блока.

СНР представлен на рисунке 2, где это левая и правая часть входного дифференциала соответственно, а значение в матрице кол-во уникальных выходных дифференциалов.

Рисунок 2. СНР блока.

Другим свойством блоков является неравномерность распределения повторений (СНП). СНП заключается в неравномерности повторений выходных дифференциалов.

На основе СНП был создан алгоритм восстановления значений (АВЗ) [2], который позволяет восстанавливать возможные значения на входе/выходе блока зная дифференциалы на входе и выходе.

Раздел 3. Описание DFA.

Метод DFA (дифференциальный анализ ошибки) был впервые представлен в 1996 году [3] для RSA. Позже теория DFA была развита для применения к симметричным алгоритмам [4] и получила широкое распространение. DFA предполагает внедрение ошибки в промежуточное значения (ПЗ) этапов вычисления открытого/закрытого текста. Для DFA требуется несколько процессов шифрования/дешифрования. Так же DFA требует знания открытого и закрытого текста или одного из них в зависимости от цели анализа. Данный метод может быть активным не инвазивным или полуинвазивным.

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

Рисунок 3. Этапы анализа Кузнечика с помощью DFA.

Раздел 4. Алгоритм применения DFA к кузнечику.

Алгоритм применения DFA прежде всего заключается в представлении процесса шифрования как указано на рисунке 3. Видно, что , где n = 1, 4, 7, 10 образуют группы. В данных группах ПЗ в которые внедряется ошибка приведут к схожему результату восстановления ключа. Чёрным выделено блок восстановления, к которому необходимо применять АВЗ.

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

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

Группа в ПЗ которой внедряется ошибка влияет на количество восстановленных подключей. В таблице 1 приведены средние значения количества дифференциалов на входе блока восстановления для двух этапов в зависимости от группы в которую внедрена ошибка и максимальное/минимальное количество восстановленных первых/вторых подключей. Следует сказать, что на рисунке 3 и в таблице 1 используется только по 3 группы, но их может быть больше. Слишком удалённая группа от блока восстановления восстановит все возможные ключи, т.е. сложность увеличится до сложности полного перебора.

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

Этап	гр. i кол. диф. на вх.	гр. i+1 кол. диф. на вх.	гр. i+2 кол. диф. на вх.	гр. i кол. подключей	гр. i+1 кол. подключей	гр. i+2 кол. подключей
Этап №1	1
Этап №2	1

Значения в таблице 1 представлены без вероятностного фактора фильтрации дифференциалов в АВЗ, что значительно увеличивает кол-во восстанавливаемых ключей.

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

Можно заключить, что шифр Кузнечик потенциально имеет слабость относительно DFA без учёта фильтрации дифференциалов при применении АВЗ.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

ГОСТ 34.12.-2015 “Кузнечик” [Электронный ресурс]. – URL: http://www.tc26.ru/standard/draft/GOSTR-bsh.pdf (дата обращения 21.08.2017).

Красовский А. В. Анализ криптографической стойкости шифра "Кузнечик" методом связанных ключей. [Электронный ресурс]. – URL: https://www.scienceforum.ru/2017/pdf/36877.pdf (дата обращения 13.01.2018).

Dan Boneh, Richard A. Demillo, Richard J. Lipton, On the Importance of Checking Cryptographic Protocols for Faults, Lecture Notes in Computer Science, Advances in Cryptology, proceedings of EUROCRYPT97, pp. 37–51, 1997.

Eli Biham, Adi Shamir. Differential Fault Analysis of Secret Key Cryptosystems. [Электронный ресурс]. – URL: https://pdfs.semanticscholar.org/440f/a56b0618578b34c7a4fb781fc40388bf8e18.pdf (дата обращения 14.01.2018).

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