Сетевое издание
Международный студенческий научный вестник
ISSN 2409-529X

THEORETICAL APPLICATION OF DFA TO GOST R 34.12–2015 «KUZNYECHIK»

Krasovsky A.V. 1
1 SFU ETA ICTIS
Modern confidentiality guaranteed by the strength of cryptographic algorithms. This algorithms used in many different implementations. Hash functions used in «block chain», asymmetric cipher algorithms used in data transfer protocol in «Bitcoin» system, symmetric cipher algorithms used in smart cards etс. Analysis of crypto algorithms vulnerability allows support high level of confidentiality. Today Kuznyechik [1] is modern cipher standard in Russia Federation. Analysis of Kuznyechik is actual security problem of Russia Federation. One of the most effective approach for analysis is DFA. Author of this paper consider that analysis of Kuznyechik by DFA is very topical theme for research and it allow find common rules for practical analysis of Kuznyechik with DFA.
DFA
Kuznyechik
GOST R 34.12–2015
theoretical analysis

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

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

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

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

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

kras1.tiff

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

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

kra10.wmf,

где kra11.wmf.

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

kra13.wmf.

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

kra14.wmf.

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

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

kra19.wmf

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

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

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

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

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

kras2.tiff

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

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

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

3. Описание DFA

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

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

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

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

kras3.tiff

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

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

Этап

гр. i кол. диф. на вх.

гр. i+1 кол. диф. на вх.

гр. i+2 кол. диф. на вх.

гр. i кол. подключей

гр. i+1 кол. подключей

гр. i+2 кол. подключей

Этап №1

1

100

kra31.wmf

kra32.wmf

kra33.wmf

kra34.wmf

Этап №2

1

100

kra36.wmf

kra37.wmf

kra38.wmf

kra39.wmf

 

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

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

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

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

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

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