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

ТЕОРЕТИЧЕСКОЕ ПРИМЕНЕНИЕ DFA К ГОСТ P 34.12–2015 «КУЗНЕЧИК»

Красовский А.В. 1
1 ЮФУ ИТА ИКТИБ
Современная конфиденциальность гарантируется стойкостью криптографических алгоритмов. Данные алгоритмы используются во множестве разнообразных исполнений. Функции хэширования присутствуют в «block chain», ассиметричные алгоритмы шифрования в протоколах передачи данных системы «Bitcoin», симметричные алгоритмы шифрования внедрены в смарт карты и т.д. Анализ и поиск уязвимостей криптографических алгоритмов позволяет поддерживать высокий уровень конфиденциальности. В настоящий момент современным стандартом шифрования РФ является шифр Кузнечик [1]. Анализ Кузнечика – это актуальная проблема безопасности РФ. Одним из самых продуктивных способов анализа является DFA. Соответственно автор данной статьи считает крайне актуальным вопросом анализ шифра Кузнечик методом DFA в теории, что позволит выявить общие положения для применения практического анализа Кузнечика с помощью DFA.
DFA
Кузнечик
ГОСТ Р 34.12–2015
теоретический анализ
1. ГОСТ 34.12.-2015. Кузнечик [Электронный ресурс]. – URL: http://www.tc26.ru/standard/draft/GOSTR-bsh.pdf (дата обращения 21.08.2017).
2. Красовский А.В. Анализ криптографической стойкости шифра «Кузнечик» методом связанных ключей. [Электронный ресурс]. – URL: https://www.scienceforum.ru/2017/pdf/36877.pdf (дата обращения 13.01.2018).
3. 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.
4. Eli Biham, Adi Shamir. Differential Fault Analysis of Secret Key Cryptosystems. [Электронный ресурс]. – URL: https://pdfs.semanticscholar.org/440f/a56b0618578b34c7a4fb781fc40388bf8e18.pdf (дата обращения 14.01.2018).

В данной работе в разделе 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 без учёта фильтрации дифференциалов при применении АВЗ.


Библиографическая ссылка

Красовский А.В. ТЕОРЕТИЧЕСКОЕ ПРИМЕНЕНИЕ DFA К ГОСТ P 34.12–2015 «КУЗНЕЧИК» // Международный студенческий научный вестник. – 2018. – № 3-2.;
URL: http://eduherald.ru/ru/article/view?id=18236 (дата обращения: 14.06.2021).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074