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

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

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

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

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

Рис. 1. Блоки S и

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

,

где .

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

.

А выходом является значение

.

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

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

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

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

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

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

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

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

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

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

3. Описание DFA

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

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

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

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

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

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

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

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

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

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

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

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