В данной работе в разделе 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
Количество восстановленных подключей в зависимости от группы
|
Этап |
гр. i кол. диф. на вх. |
гр. i+1 кол. диф. на вх. |
гр. i+2 кол. диф. на вх. |
гр. i кол. подключей |
гр. i+1 кол. подключей |
гр. i+2 кол. подключей |
|
Этап №1 |
1 |
100 |
|
|
|
|
|
Этап №2 |
1 |
100 |
|
|
|
|
В первую очередь выполняется первый этап алгоритма применения DFA. Оба этапа производятся для одного и того же набора подключей. Ошибка изменяется случайный бит в запланированном ПЗ или группе. Алгоритм первого этапа следующий: шифруется текст P и получается закрытый текст C, шифруется текст P и в какой либо ПЗ внедряется ошибка и получается C′, дифференциал 
восстанавливается до выхода блока восстановления, дифференциал в каком либо ПЗ восстанавливается до входа блока восстановления, для блока восстановления применяется АВЗ, возможные значения проходят через L блок и восстанавливается возможные десятые подключи.
Второй этап аналогичен первому, только последний S и L блок отбрасываются так как в ПЗ3 возможно вычислить список возможных значений на основе закрытого текста и списка возможных десятых подключей. После восстановления возможных девятых подключей следует для всех пар 10 и 9 подключей вычислить остальные и отфильтровывать их.
Группа в ПЗ которой внедряется ошибка влияет на количество восстановленных подключей. В таблице приведены средние значения количества дифференциалов на входе блока восстановления для двух этапов в зависимости от группы в которую внедрена ошибка и максимальное/минимальное количество восстановленных первых/вторых подключей. Следует сказать, что на рис. 3 и в таблице используется только по 3 группы, но их может быть больше. Слишком удалённая группа от блока восстановления восстановит все возможные ключи, т.е. сложность увеличится до сложности полного перебора.
Значения в таблице представлены без вероятностного фактора фильтрации дифференциалов в АВЗ, что значительно увеличивает кол-во восстанавливаемых ключей.
В данной работе был описан способ применения метода DFA к шифру Кузнечик, представлено описание алгоритма применения DFA в общем виде. В работе описанные дифференциальные свойства блоков шифра и описан сам шифр. Так же приведена таблица сложностей восстановления ключа в зависимости от групп внедрения ошибки.
Можно заключить, что шифр Кузнечик потенциально имеет слабость относительно DFA без учёта фильтрации дифференциалов при применении АВЗ.