Сравнительный анализ старого и нового стандартов РФ на криптографическую функцию хэширования Текст научной статьи по специальности «Компьютерные и информационные науки»
Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Санчес Россель Хосе Агустин
В статье приведен сравнительный анализ старого (ГОСТ Р 34.11-94) и нового (ГОСТ Р 34.11-2012) стандартов Российской Федерации, описывающих алгоритмы и процедуры вычисления хэш-функции , которые используются в процессах создания и верификации цифровой подписи.
Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Санчес Россель Хосе Агустин
COMPARATIVE ANALYSIS OF THE OLD AND NEW STANDARDS RF ON CRYPTOGRAPHIC HASH FUNCTION
The article presents a comparative analysis of the old (GOST R 34.11-94 ) and the new ( GOST R 34.11-2012 ) standards of the Russian Federation, describing the algorithms and procedures for calculating the hash functions, which used in the process of creating and verifying digital signature.
Текст научной работы на тему «Сравнительный анализ старого и нового стандартов РФ на криптографическую функцию хэширования»
DOI: 10.18454/IRJ.2016.45.002 Санчес Россель Хосе Агустин Аспирант, Южный Федеральный Университет СРАВНИТЕЛЬНЫЙ АНАЛИЗ СТАРОГО И НОВОГО СТАНДАРТОВ РФ НА КРИПТОГРАФИЧЕСКУЮ
В статье приведен сравнительный анализ старого (ГОСТ Р 34.11-94) и нового (ГОСТ Р 34.11-2012) стандартов Российской Федерации, описывающих алгоритмы и процедуры вычисления хэш-функции, которые используются в процессах создания и верификации цифровой подписи.
Ключевые слова: криптография, шифрование, хэш-функция.
Sanchez Rossel Jose Agustin Postgraduate student, Southern Federal University COMPARATIVE ANALYSIS OF THE OLD AND NEW STANDARDS RF ON CRYPTOGRAPHIC
The article presents a comparative analysis of the old (GOST R 34.11-94 ) and the new ( GOST R 34.11-2012 ) standards of the Russian Federation, describing the algorithms and procedures for calculating the hash functions, which used in the process of creating and verifying digital signature.
Keywords: cryptography, encryption, hash function.
ГОСТ Р 34.11-2012 (функция «Стрибог») является новым российским криптографическим стандартом хэш-функции для любого набора двоичных символов, которые используются в компьютерных методах криптографии [1].
Стандарт разработан для замены ГОСТ Р 34.11-94 (далее «ГОСТ») [2], обработка блоков в котором происходит по алгоритму шифрования ГОСТ 28147-89 [3-5], содержим нелинейные преобразования на S-блоках. Алгоритм ГОСТ является итеративным.
В процессе шифровки происходит 32 раунда преобразований (рис. 1):
Рис. 1 — Раунд алгоритма ГОСТ 28147-89
Разработка стандарта потребовалась для создания хэш-функции, отвечающей необходимым потребностям стандарта ГОСТ 34.10-2012 [6] на электронную цифровую подпись (ЦП). Данная функция хэширования применяется при практической реализации систем ЦП на основе ассиметричного криптографического алгоритма (один ключ используется для зашифрования данных, а другой для дешифрования), которые позволяют обойти недостатки, свойственные симметричным системам: при их использовании не нужен секретный обмен ключами (открытые ключи передаются динамически), а так же исчезает квадратичная корреляция количества ключей от количества пользователей.
В новом стандарте размер блока входных данных вдвое меньше, чем в ГОСТ при той же длине хэша, однако «Стрибог» может работать и при длине хэша в два раза большей.
Базовый алгоритм шифрования реализует перестановку элементов множества VJ28 в зависимости от значений итерационных ключей К е Vl28, / = 1,2. Д0.
Алгоритм зашифрования реализует преобразование множества Vl28 в соответствии с равенством
ЕК1. лю (а) = Х[Кю]18Х[К9]. 13Х[К2]13Х[К1](а), (1)
Алгоритм расшифрования реализует преобразование множества У]28 в соответствии с равенством
Значения К е У512, 1 = 1,___13 вычисляются как:
К = ЬРБ(Кч ФС,ч),I = 2. 13. (3)
В качестве функции сжатия старый стандарт предусматривает использование симметричного блочного шифра ГОСТ 28147-89. Функция сжатия состоит из 4-х параллельных блоков шифрования по ГОСТ 28147-89, механизма генерации ключей для выполнения шифрования и выходного перемешивающего преобразования. В «Стрибог» функция сжатия основана на конструкции Миагучи-Пренеля (рис. 2).
Рис. 2 — Схема конструкции Миагучи-Пренеля, где:
т 1 — исходное сообщение, И 1 — значение хеш-функции, И 1-1 — значение предыдущей хеш-функции Значение хэш-кода сообщения МеУ* рассчитывается при помощи итерационной процедуры. На каждом шаге вычисления хэш-кода применяется функция сжатия:
бы ^ 51^ ^ 512 ^ г с '512'
значение которой определяется по формуле:
g (h, m): E(LPS (h 0 N),m) 0 h 0 m,
E(K,m) = X [K13] LPSX [K12]..LPSX [K2] LPSX [K] (m).
Еще одним значительным отличием нового стандарта от старого является то, что значение инициализационного вектора в ГОСТ не определенно, а в новом стандарте определенно и фиксировано.
В [7] приводится исследование старого и нового стандартов Российской Федерации.
Тестирование производилось на ЦП Intel Core i7-920 CPU @ 2.67 GHz и видеокарте NVIDIA GTX 580. Использовалась авторская гибридная 32-битная схема для «Стрибог» и простая последовательная для ГОСТ. Результаты исследования представлены в таблице 1.
Таблица 1 — Результаты производительности
ГОСТ Р 34.11-94 Стрибог-512
Реализация МБ/с Тактов/байт МБ/с Тактов/байт
«openssl-ccgost» «rhash» «kazymyrov» «Авторская» 18 49 64 143 52 40 38 94 67 27
L П, 8192 потока данных
«Авторская» 1697 — 608 —
В работе [8] были обнаружены некоторые слабые стороны алгоритма ГОСТ с теоретической точки зрения, в то время как из работы [9] можно сделать вывод, что на практике невозможно осуществить атаку на полнораундовую функцию «Стрибог».
Группа исследователей из университета «Конкордия» провели интегральный криптоанализ алгоритма ЛБ8, который является базовым для функции «Стрибог» [10]. Результатом исследования использования стало получение значении от 264 до 2120 входных или среднераундовых значений при разных условиях нахождения различителя.
1. Новый стандарт проще в реализации и оптимизации как алгебраически, так и для конкретной платформы.
2. Криптографическая стойкость нового российского алгоритмы получения хэш-функции выше, чем у старого стандарта ГОСТ.
3. Новая функция «Стрибог» обладает значительной криптостойкостью и на настоящий момент является недостижимой для полного теоретического взлома.
1. Информационная технология. Криптографическая защита информации. Функция хэширования. ГОСТ Р 34.11-2012. М.: Стандартинформ, 2012. — 38с.
2. Информационная технология. Криптографическая защита информации. Функция хэширования. ГОСТ Р 34.11-94. М.: Госстандарт России, 1994.- 23с.
3. ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования — М.: Госстандарт СССР, 1989.
4. Бабенко Л.К., Ищукова Е.А. Анализ алгоритма ГОСТ 28147-89: поиск слабых блоков // Известия ЮФУ. Технические науки. Тематический выпуск «Информационная безопасность». — Таганрог: Изд-во ТТИ ЮФУ. — 2014. -№ 2(151) — С. 148-157.
5. Бабенко Л.К., Ищукова Е.А. Использование слабых блоков замены для линейного криптоанализа блочных шифров // Известия ЮФУ. Технические науки. Тематический выпуск «Информационная безопасность». — Таганрог: Изд-во ТТИ ЮФУ. — 2014. — № 2(151). — С. 136-147.
6. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи. ГОСТ Р 34.10-2012. М.: Стандарттинформ, 2012. — 38 с.
7. Лебедев П.А. «Параллельные вычисления и задачи управления». Материалы конференции // Москва, http://paco2012.ipu.ru/procdngs/F108.pdf // 2012 г. с. 266-272
8. F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, and J. Szmidt. Cryptanalysis of the GOST hash function. In D. Wagner, editor, Advances in Cryptology CRYPTO 2008, volume 5157 of LNCS, pages 162-178.
9. R. R. 2. 2. h. Riham AlTawy and Amr M. Youssef. Integral Distinguishers for Reduced-round Stribog. Cryptology ePrint Archive.
10. Jian Guo and Jeremy Jean and Gaëtan Leurent and Thomas Peyrin and Lei Wang.The Usage of Counter Revisited: Second-Preimage Attack on New Russian Standardized Hash Funct. Cryptology ePrint Archive, Report 2014/675, 2014. http://eprint.iacr.org/2014/675.
1. Informatsionnaya tekhnologiya. Kriptograficheskaya zashchita informatsii. Funktsiya kheshirovaniya. GOST R 34.112012. M.: Standartinform, 2012. — 38s.
2. Informatsionnaya tekhnologiya. Kriptograficheskaya zashchita informatsii. Funktsiya kheshirovaniya. GOST R 34.1194. M.: Gosstandart Rossii, 1994.- 23s.
3. GOST 28147-89 Sistemy obrabotki informatsii. Zashchita kriptograficheskaya. Algoritm kriptograficheskogo preobrazovaniya — M.: Gosstandart SSSR, 1989.
4. Babenko L.K., Ishchukova E.A. Analiz algoritma GOST 28147-89: poisk slabykh blokov // Izvestiya YuFU. Tekhnicheskie nauki. Tematicheskiy vypusk «Informatsionnaya bezopasnost'». — Taganrog: Izd-vo TTI YuFU. — 2014. — № 2(151) — S. 148-157.
5. Babenko L.K., Ishchukova E.A. Ispol'zovanie slabykh blokov zameny dlya lineynogo kriptoanaliza blochnykh shifrov // Izvestiya YuFU. Tekhnicheskie nauki. Tematicheskiy vypusk «Informatsionnaya bezopasnost'». — Taganrog: Izd-vo TTI YuFU. — 2014. — № 2(151). — S. 136-147.
6. Kriptograficheskaya zashchita informatsii. Protsessy formirovaniya i proverki elektronnoy tsifrovoy podpisi. GOST R 34.10-2012. M.: Standarttinform, 2012. — 38 s.
7. Lebedev P.A. «Parallel'nye vychisleniya i zadachi upravleniya». Materialy konferentsii // Moskva, http://paco2012.ipu.ru/procdngs/F108.pdf // 2012 g. s. 266-272
8. F. Mendel, N. Pramstaller, C. Rechberger, M. Kontak, and J. Szmidt. Cryptanalysis of the GOST hash function. In D. Wagner, editor, Advances in Cryptology CRYPTO 2008, volume 5157 of LNCS, pages 162-178.
9. R. R. 2. 2. h. Riham AlTawy and Amr M. Youssef. Integral Distinguishes for Reduced-round Stribog. Cryptology ePrint Archive.
Импортозамещенное шифрование глазами программиста. Хешируем по ГОСТ 34.11—2012
Стандарт ГОСТ 34.11—2012 пришел на смену ГОСТ 34.11—94, который к настоящему времени уже считается потенциально уязвимым (хотя до 2018 года ГОСТ 1994 года выпуска все же применять не возбраняется). Отечественные стандарты хеширования обязательны к применению в продуктах, которые будут крутиться в ответственных и критических сферах и для которых обязательно прохождение сертификации в уполномоченных органах (ФСТЭК, ФСБ и подобных). ГОСТ 34.11—2012 был разработан Центром защиты информации и специальной связи ФСБ России с участием открытого акционерного общества «Информационные технологии и коммуникационные системы» (ИнфоТеКС). В основу стандарта 2012 года была положена функция хеширования под названием «Стрибог» (если что, такое имя носил бог ветра в древнеславянской мифологии).
Славянский бог ветра Стрибог (сайт myfhology.info)
Другие статьи в выпуске: 
Xakep #210. Краткий экскурс в Ethereum
Тестовый пример из ГОСТ 34.11—2012
Хеш-функция «Стрибог» может иметь две реализации с результирующим значением длиной 256 или 512 бит. На вход функции подается сообщение, для которого необходимо вычислить хеш-сумму. Если длина сообщения больше 512 бит (или 64 байт), то оно делится на блоки по 512 бит, а оставшийся кусочек дополняется нулями с одной единичкой до 512 бит (или до 64 байт). Если длина сообщения меньше 512 бит, то оно сразу дополняется нулями с единичкой до полных 512 бит.
Немного теории
Основу хеш-функции «Стрибог» составляет функция сжатия (g-функция), построенная на блочном шифре, построенном с помощью конструкции Миягучи — Пренеля, признанной одной из наиболее стойких.
Блочный шифр в режиме Миягучи — Пренеля. Здесь m — очередной блок исходного сообщения, h — значение предыдущей функции сжатия
В целом хеширование производится в три этапа. Первый этап — инициализация всех нужных параметров, второй этап представляет собой так называемую итерационную конструкцию Меркла — Дамгорда с процедурой МД-усиления, третий этап — завершающее преобразование: функция сжатия применяется к сумме всех блоков сообщения и дополнительно хешируется длина сообщения и его контрольная сумма.
Общая схема вычисления хеш-суммы по ГОСТ 34.11—2012
WARNING
Итак, после краткого и небольшого погружения в теорию начинаем кодить.
Базовые функции стандарта
Поскольку при вычислении хеша мы имеем дело с 64-байтовыми блоками (в стандарте они представлены 512-разрядными двоичными векторами), для начала определим этот самый двоичный вектор:
Сложение двух двоичных векторов по модулю 2
Здесь все предельно просто. Каждый байт первого вектора ксорится с соответствующим байтом второго вектора, и результат пишется в третий (выходной) вектор:
Побитовое исключающее ИЛИ над 512-битными блоками
В тексте ГОСТа название данной операции звучит как сложение в кольце вычетов по модулю 2 в степени n. Такая фраза кого угодно может вогнать в уныние, но на самом деле ничего сложного и страшного в ней нет. Два исходных 64-байтовых вектора представляются как два больших числа, далее они складываются, и переполнение, если оно появляется, отбрасывается:
Нелинейное биективное преобразование (преобразование S)
При биективном отображении каждому элементу одного множества соответствует ровно один элемент другого множества (более подробно про биекцию можешь почитать в Википедии). То есть это просто банальная подстановка байтов в исходном векторе по определенному правилу. В данном случае правило задается массивом из 256 значений:
Здесь для экономии места показаны не все значения, определенные в стандарте, а только три первых и два последних. Когда будешь писать код, не забудь про остальные.
Итак, если в исходном векторе у нас встречается какой-либо байт со значением, например, 23 (в десятичном выражении), то вместо него мы пишем байт из массива Pi, имеющий порядковый номер 23, и так далее. В общем, код функции преобразования S получается такой:
Преобразование S
Перестановка байтов (преобразование P)
Преобразование P — простая перестановка байтов в исходном массиве в соответствии с правилом, определяемым массивом Tau размером в 64 байта:
Здесь, так же как и в предыдущем случае, для экономии места показаны не все значения массива Tau.
Перестановка выполняется следующим образом: сначала идет нулевой элемент исходного вектора, далее — восьмой, потом — шестнадцатый и так далее до последнего элемента. Код функции напишем так:
Линейное преобразование (преобразование L)
Это преобразование носит название «умножение справа на матрицу A над полем Галуа GF(2)» и по сравнению с первыми двумя будет немного посложнее (по крайней мере, вкурить всю суть от и до с первого прочтения стандарта удается далеко не всем). Итак, есть матрица линейного преобразования A, состоящая из 64 восьмибайтовых чисел (здесь приведена не в полном объеме):
Исходный вектор делится на порции размером по 8 байт, каждая из этих порций интерпретируется в виде 64-разрядного двоичного представления. Далее берется очередная порция, каждому биту из этой порции ставится в соответствие строка из матрицы A. Если очередной бит равен нулю, то соответствующая ему строка из матрицы A вычеркивается; если очередной бит равен единице, то соответствующая ему строка из матрицы A остается. После всего этого оставшиеся строки из матрицы линейного преобразования ксорятся, и получившееся число записывается в виде очередной восьмибайтовой порции в результирующий вектор. Код выглядит следующим образом:
Схема линейного преобразования L
Пишем все остальное
Имея в наличии все необходимые базовые преобразования, определенные стандартом, можно приступить непосредственно к реализации алгоритма «Стрибог» в целом.
Для начала определим структуру, в которую будем складывать все исходные, промежуточные и конечные результаты вычислений:
Далее напишем преобразование E, которое является частью функции сжатия. В этом преобразовании задействовано двенадцать так называемых итерационных констант (C1 — C12), на основе которых вычисляются раундовые ключи K. Для вычисления этих раундовых ключей определим функцию GOSTHashGetKey , которая представляет собой сочетание преобразований S, P и L, а также побайтного сложения по модулю 2:
Для этой функции необходимо описать итерационные константы, которых, как мы уже говорили, двенадцать штук (для краткости здесь эти константы показаны не в полном объеме):
Если ты попытаешься сравнить приведенные выше константы с текстом стандарта, то увидишь, что эти самые константы записаны «задом наперед». Дело в том, что все байтовые массивы (в том числе и строки тестовых примеров) в тексте стандарта описаны таким образом, что нулевой их элемент находится в конце массива, а не в начале, как мы привыкли, поэтому строки перед использованием надо «переворачивать».
Далее пишем саму функцию преобразования E:
И, используя эти функции, пишем самую главную функцию алгоритма «Стрибог» — функцию сжатия g:
Схема функции сжатия g
В самом начале мы говорили, что хеширование выполняется блоками по 64 байта, а последний блок, если он меньше 64 байт, дополняется нулями с одной единичкой. Для этой операции вполне подойдет функция GOSTHashPadding :
Теперь открываем руководящий документ на шестой странице и внимательно разбираемся с этапами вычисления столь нужной нам хеш-функции.
Первый этап (инициализация)
Как ясно из названия, этот этап необходим для первоначального задания значений всех переменных:
Второй этап
На этом этапе мы хешируем отдельные блоки размером в 512 бит (или 64 байта) до тех пор, пока они не кончатся. Этап состоит из функции сжатия и двух операций исключающего ИЛИ (с их помощью формируется контрольная сумма):
Третий этап
На третьем этапе мы хешируем остаток, который не попал в очередной 64-байтный блок из-за того, что его размер меньше. Далее формируем контрольную сумму всего сообщения с учетом его длины и вычисляем окончательный результат. Выглядит это все так:
Разобравшись со всеми этапами, сложим все в единое целое. Весь процесс будет описан в трех функциях:
- GOSTHashInit (она у нас уже есть);
- GOSTHashUpdate (туда мы поместим все итерации второго этапа);
- GOSTHashFinal (там мы завершим весь процесс третьим этапом).
Функция GOSTHashUpdate
Объявим эту функцию таким образом:
Как уже неоднократно говорилось, хеширование производится блоками по 64 байта, поэтому в начале функции напишем следующее:
Поскольку при чтении файла мы его будем читать по кусочкам, длина которых задается при использовании функции fread, то при слишком длинном файле мы можем потерять остаток файла и, соответственно, неправильно посчитать хеш-сумму. Чтобы этого избежать, необходимо в нашу функцию GOSTHashUpdate добавить следующий код:
Функция GOSTHashFinal
Здесь все просто:
Считаем хеш-сумму файла
Вот мы и подошли к завершающему этапу написания кода, позволяющего посчитать хеш-сумму по алгоритму «Стрибог». Осталось считать нужный файл в заранее отведенный участок памяти и поочередно вызвать функции GOSTHashUpdate и GOSTHashFinal :
После завершения в зависимости от нужной нам длины хеш-суммы берем значение CTX->hash полностью (длина хеша 512 бит) либо берем от CTX->hash последние 32 байта.
Не забудь про исходники
Весь код: классическую реализацию алгоритма (в полном соответствии с ГОСТом), усовершенствованную реализацию (с предварительным расчетом значений преобразований S и L), а также код предварительного расчета значений преобразований S и L — ты найдешь в приложении к этому номеру.
Заключение
Наверняка у тебя промелькнула мысль о ресурсоемкости данного алгоритма и возможных способах увеличения быстродействия. Очевидные приемы типа применения выравнивания при описании всех используемых структур, переменных и участков памяти, скорее всего, ощутимого эффекта не дадут, но в этом алгоритме есть возможность заранее посчитать некоторые значения и использовать при написании кода в дальнейшем именно их.
Если внимательно почитать стандарт (особенно страницы 3 и 4), то выяснится, что преобразования S и L можно выполнить заранее и сформировать восемь массивов по 256 восьмибайтовых чисел, в которых будут содержаться все возможные значения этих двух преобразований. Помимо этого, при вычислении хеш-суммы с использованием заранее рассчитанных значений можно сразу сделать и нужные перестановки в соответствии с преобразованием P. В общем, весь нужный код (вычисление хеша классическим алгоритмом, предварительный расчет значений преобразований S и L и вычисление хеша с помощью заранее просчитанных значений) найдешь в приложении к этой статье. Бери, разбирайся, пользуйся.
Криптографические хеш-функции
В настоящее время предложены и практически используются различные специальные алгоритмы для вычисления хеш-функции. Наиболее известными алгоритмами являются MD5 , SHA-1 , SHA -2 и другие версии SHA , а также отечественный алгоритм , изложенный в ГОСТ Р 34.11-94.
Алгоритм MD5 появился в начале 90-х годов ХХ века в результате усовершенствования алгоритма формирования хеш-функции MD4 . Символы в названии » MD » означают Message Digest – краткое изложение сообщения. Автор алгоритмов MD4 и MD5 – Р. Ривест (R.Rivest). В результате использования MD5 для произвольного сообщения формируется 128-битное хеш- значение . Входные данные обрабатываются блоками по 512 бит . В алгоритме используются элементарные логические операции ( инверсия , конъюнкция , сложение по модулю 2, циклические сдвиги и др.), а также обыкновенное арифметическое сложение . Комплексное повторение этих элементарных функций алгоритма обеспечивает то, что результат после обработки хорошо перемешан. Поэтому маловероятно, чтобы два сообщения, выбранные случайно, имели одинаковый хеш-код. Алгоритм MD5 имеет следующее свойство: каждый бит полученного хеш-значения является функцией от каждого бита входа. Считается, что MD5 является наиболее сильной хеш-функцией для 128-битного хеш-значения.
Алгоритм SHA ( Secure Hash Algorithm – Безопасный хеш- алгоритм ) был разработан национальным институтом стандартов и технологии ( NIST ) США и опубликован в качестве американского федерального информационного стандарта в 1993 году. SHA-1 , как и MD5 , основан на алгоритме MD4 . SHA-1 формирует 160-битное хеш- значение на основе обработки исходного сообщения блоками по 512 бит . В алгоритме SHA-1 также используются простые логические и арифметические операции . Наиболее важным отличием SHA-1 от MD5 является то, что хеш-код SHA-1 на 32 бита длиннее, чем хеш-код MD5 . Если предположить, что оба алгоритма одинаковы по сложности для криптоанализа, то SHA-1 является более стойким алгоритмом. Используя атаку методом грубой силы (лобовую атаку), труднее создать произвольное сообщение, имеющее данный хеш-код, а также труднее создать два сообщения, имеющие одинаковый хеш-код.
В 2001 году национальный институт стандартов и технологии США принял в качестве стандарта три хеш-функции с большей длиной хеш-кода, чем у SHA-1 . Часто эти хеш-функции называют SHA -2 или SHA-256 , SHA -384 и SHA-512 (в названии указывается длина создаваемого алгоритмами хеш-кода). Эти алгоритмы отличаются не только длиной создаваемого хеш-кода, но и используемыми внутренними функциями и длиной обрабатываемого блока (у SHA-256 длина блока – 512, а у SHA -384 и SHA-512 длина блока – 1024 бита). Постепенные усовершенствования алгоритма SHA ведут к увеличению его криптостойкости. Несмотря на отличия рассматриваемых алгоритмов друг от друга, все они являются дальнейшим развитием SHA-1 и MD4 и имеют похожую структуру.
В России принят ГОСТ Р34.11-94, который является отечественным стандартом для хеш-функций. Его структура довольно сильно отличается от структуры алгоритмов SHA-1 ,2 или MD5 , в основе которых лежит алгоритм MD4 . Длина хеш-кода, создаваемого алгоритмом ГОСТ Р 34.11-94, равна 256 битам. Алгоритм последовательно обрабатывает исходное сообщение блоками по 256 бит справа налево. Параметром алгоритма является стартовый вектор хеширования – произвольное фиксированное значение длиной также 256 бит . В алгоритме ГОСТ Р 34.11-94 используются операции перестановки, сдвига, арифметического сложения, сложения по модулю 2. В качестве вспомогательной функции в ГОСТ 34.11-94 используется алгоритм по ГОСТ 28147-89 в режиме простой замены.
Ключевые термины
Нash function – хеш- функция .
ГОСТ Р34.11-94 – российский стандарт на функцию хеширования.
Хеш-функция – математическая или иная функция , которая для строки произвольной длины вычисляет некоторое целое значение или некоторую другую строку фиксированной длины.
Хеш-код – результат работы хеш-функции, некоторый характерный «признак» входного массива данных.
Краткие итоги
Хеш- функция – математическая или иная функция , которая для строки произвольной длины (прообраза) вычисляет некоторое целое значение или некоторую другую строку фиксированной длины. Смысл хеш-функции состоит в определении характерного признака прообраза – значения хеш-функции. Это значение обычно имеет определенный фиксированный размер. Хеш-код может быть в дальнейшем проанализирован для решения какой-либо задачи.
Хеш-функции широко применяются в современной криптографии. В криптографии хеш- функция считается хорошей, если трудно создать два прообраза с одинаковым значением хеш-функции, а также, если у выхода функции нет явной зависимости от входа.
В качестве хеш-функции можно использовать блочный алгоритм симметричного шифрования в определенных режимах. Кроме того, в настоящее время предложены и практически используются различные специальные алгоритмы для вычисления хеш-функции. Наиболее известными алгоритмами являются MD5 , SHA-1 , SHA -2 и другие версии SHA , а также отечественный алгоритм , изложенный в ГОСТ Р 34.11-94.
Набор для практики
Вопросы для самопроверки
- Что в криптографии называется хеш-функцией?
- Для каких целей используются хеш-функции?
- Перечислите основные требования, предъявляемые к хеш-функциям.
- Назовите примеры криптографических хеш-функций.
- Каков российский стандарт на алгоритм формирования криптографической хеш-функции?
- Каким образом можно использовать блочный алгоритм шифрования для формирования хеш-функции?
Упражнения для самопроверки
Пусть хеш-функция y=h(x1x2…xn) определяется как результат выполнения побитовой операции «сумма по модулю 2» для всех байтов сообщения, представленного в двоичном виде. Длина хеш-кода равна 8 битам. Для каждого из шести сообщений, записанных в левом столбце, найдите соответствующий результат вычисления хеш-функции из правого столбца. Все сообщения и значения хеш-функции представлены в шестнадцатеричном формате.
Шифруем по-русски, или отечественные криптоалгоритмы
В данной статье простыми словами описаны криптоалгоритмы, являющиеся актуальными на данный момент российскими стандартами защиты информации, и подобраны ссылки на материалы, которые при желании помогут разобраться с ними глубже. А также, в конце статьи приведены работы с результатами криптоанализа одного из важнейших элементов данных алгоритмов.
Из новостей
За ближайший год не раз появлялись новости о предложениях расширять области использования отечественной криптографии. Чтобы представить сроки реализации предложений, стоит упомянуть ряд новостей.
До конца 2020 года планируется «закончить создание национального удостоверяющего центра — структуры, которая будет выдавать сайтам в Рунете отечественные цифровые сертификаты», пишет Медуза. Также, по данным этого издательства отечественные цифровые сертификаты будут использовать криптоалгоритмы Магма и Кузнечик. Кроме того, отечественные алгоритмы шифрования по требованию Центробанка станут обязательными к использованию в платежных системах уже с 2024 года, пишет РБК.
Добавим к этому новость от газеты Коммерсантъ, в которой Магма и Кузнечик упоминаются в контексте тестируемых алгоритмов для использования в виртуальных сим-картах eSim.
Упомянутые выше и другие основные алгоритмы, используемые в отечественной криптографии стандартизованы и описаны в ГОСТах.
Направления ГОСТов
Отечественная криптография базируется на четырех основных объектах, которые мы рассмотрим далее.
Цифровая подпись
ГОСТ 34.10-2018 описывает алгоритмы формирования и проверки электронной цифровой подписи с помощью операций в группе точек эллиптической кривой и функции хеширования. Длины секретного ключа 256 бит и 512 бит.
У пользователя есть сообщение, ключ подписи и ключ для проверки подписи. Ключ проверки подписи является открытым, для того, чтобы любой получатель смог расшифровать и убедиться в достоверности подписи. То есть если получателю удается расшифровать сообщение с помощью открытого ключа проверки подписи, принадлежащего определенному отправителю, то он может быть уверен, что сообщение подписывалось ключом подписи именно этого отправителя.
В алгоритмах формирования и проверки электронной цифровой подписи важным шагом является вычисление точки на эллиптической кривой, поэтому, прежде чем переходить к самим алгоритмам, приведем используемые понятия.
Эллиптической кривой над конечным простым полем , где , называется множество точек , , удовлетворяющих уравнению (в форме Вейерштрасса) , где , .
Альтернативный способ задать эллиптическую кривую
Отметим, что эллиптическую кривую можно задать уравнением не только в форме Вейерштрасса. Относительно новым способом задания эллиптической кривой является уравнение в форме Эдвардса .
Суммой точек , эллиптической кривой называется точка , координаты которой определяются, как , , где .
Точка эллиптической кривой , может быть определена через сумму точек .
Разбор теории, необходимой для криптографии на эллиптических кривых, можно найти тут.
Алгоритмы формирования и проверки электронной цифровой подписи.
Подпись создается по следующему алгоритму.
входные данные: сообщение и закрытый ключ подписи .
— к сообщению применяется хеш-функция(Стрибог) и вычисляется хеш-код сообщения , отметим, что хеш-код — это строка бит.
— определяется число , где — целое число, которое соответствует двоичному представлению хеш-кода . Причем если , то принимается за 1.
— это порядок порядок циклической подгруппы группы точек эллиптической кривой, который является одним из параметров цифровой подписи. Также среди параметров есть — это базовая точка подгруппы.
— на основе случайно сгенерированного целого числа , это число называют секретным ключом. Затем вычисляется точка на эллиптической кривой . Точка имеет координаты .
— из координаты точки на эллиптической кривой и преобразования хеша вычисляется электронная подпись , где . Если либо , либо равняется 0, то нужно вернуться к предыдущему шагу.
выходные данные: цифровая подпись которую добавляют к сообщению.
Теперь перейдем к алгоритму проверки подписи.
входные данные: сообщение c цифровой подписью и ключ проверки подписи
— полученная цифровая подпись проходит первичную проверку, если проверка не пройдена, то есть не выполнены неравенства , то подпись неверна.
— вычисляется хеш-код сообщения , опять же с помощью алгоритма Стрибог.
— определяется число , где целое число, которое соответсвует двоичному представлению хеш-кода . Причем если , то принимается за 1. Затем определяется .
— вычисляется точка эллиптической кривой , из которой получается .
— если , то подпись верна
выходные данные: подпись вена/неверна
Хеш-функция
ГОСТ 34.11-2018 посвящен функции хеширования. В данном документе содержится описание алгоритма вычисления хеш-функции, известной из предыдущих версий стандарта, как Стрибог.
Стрибог принимает на вход сообщение произвольной длины, которое впоследствии разбивается на блоки размером 512 бит(с дополнением блоков при необходимости). После чего входные данные преобразуются в хеш-код фиксированной длинны 256 или 512 бит.
Подробное описание алгоритма вместе с разбором используемых в нем преобразований можно найти в статье @NeverWalkAloner.
Шифры
ГОСТ 34.12-2018 охватывает блочные шифры. Именно в этом ГОСТе описаны алгоритмы шифрования Кузнечик и Магма — алгоритмы блочного шифрования с длинами шифруемых блоков 128 бит и 64 бита соответсвенно и длиной ключа шифрования 256 бит у обоих.
Шифрование блока открытого теста Кузнечиком происходит в 10 раундов, для каждого раунда из исходного ключа шифрования генерируется пара раундовых ключей, в каждом раунде проходят стадии подстановки и перестановки (перестановка вызывает особый интерес для криптоанализа алгоритма).
Приведем упрощенную схему работы Кузнечика при зашифровании.
Расшифрование Кузнечиком реализуется путем использования обратных операций подстановки и перестановки в инвертированном порядке, также, в обратном порядке следуют и раундовые ключи.
@sevastyan01 в своей статье подробно описал алгоритм Кузнечик.
Зашифрование блока Магмой проходит в 32 раунда, для каждого раунда из исходного ключа шифрования генерируется раундовый ключ, причем алгоритм генерации ключей отличается от генерации ключей в Кузнечике.
Расшифрование производится аналогичной зашифрованную последовательностью раундов, но с инвертированным порядком следования раундовых ключей.
Режимы работы шифров
ГОСТ 34.13-2018 содержит описание следующих режимов работы блочных шифров.
Режим простой замены
При зашифровании сообщение делится на блоки равной заданной длины. В случае, когда размер сообщения не кратен размеру блока, последний блок дополняется до нужной длины. Каждый блок независимо от остальных шифруется функцией, выполняющей блочное шифрования с использованием ключа.
Расшифрование происходит аналогичным образом. Причем если при зашифровании было применено дополнение, то при расшифровании применяется обратная операция.
Режим гаммирования
В данном режиме работы при шифровании каждый блок открытого текста складывается с блоком гаммы путем операции побитового сложения по модулю 2, XOR. Под гаммой понимается зашифрованная с использованием ключа последовательность, которую вырабатывает определенный алгоритм, который принимает на вход вектор инициализации.
Схематично изобразим данный режим при зашифровании и расшифровании, они происходят аналогично друг другу.
Если общая длина гаммы не кратна длине блока, то последний блок гаммы усекается до размера блока. Блоки гаммы отличны друг от друга и имеют псевдослучайных характер.
Режимы гаммирования с обратной связью: по выходу, по шифротексту
Два режима помещены в один пункт, так как они похожи между собой. В данных режимах при зашифровании выходные данные процедуры шифрования, либо сам шифротекст в случае обратной связи по шифротексту, подаются на вход следующей процедуре шифрования и так далее.
Отличие режимов можно увидеть на схеме.
При расшифровании схема преобразуется следующим образом. Шифротекст встает на место открытого текста, процедура шифрования сменяется процедурой расшифрования, а выходом алгоритма является расшифрованный текст. В дальнейших схемах будем это учитывать.
Режим простой замены с зацеплением
Особенностью данного режима работы является то, что каждый блок открытого текста, за исключением первого, складывается с предыдущим результатом шифрования.
Режим выработки имитовставки
При работе в данном режиме создается зависящий от всего текста блок, который предназначен для проверки наличия в шифротексте искажений.
Каждый из стандартов действителен с 1 июня 2019 года в соответствии с приказом Федерального агентства по техническому регулированию и метрологии. Актуальные ГОСТы наследуют разработки, прописанные в предыдущих версиях.
Реализации алгоритмов ГОСТов
@ru_crypt в своей статье собрал множество вариантов реализации ГОСТовских алгоритмов на любой вкус.
Интерес к таблице подстановок
Рассмотрим ГОСТ 34.10-2018. В алгоритмах формирования и проверки цифровой подписи на начальных шагах используется хеш-функция Стрибог, которая определена в ГОСТ 34.11-2018.
Заглянем теперь в ГОСТ 34.12-2018. В данном документе в качестве параметра алгоритма Кузнечик для нелинейного биективного преобразования приводится таблица подстановок
. Эта же таблица приведена в ГОСТ 34.11-2018, то есть используется и при хешировании.
Таблица задает единственное нелинейное преобразование в алгоритме шифрования, которое значительно усложняет взлом шифра. То есть функция подстановки особенно важна для устойчивости шифра к взломам.
Разработчики Кузнечика и Стрибога утверждают, что сгенерировали таблицу случайным образом. Однако в ряде работ был проведен криптоанализ таблицы подстановок и выявлено несколько способов ее генерации, причем не случайным образом.
Статьи с алгоритмами генерации таблицы :
В конце каждой из статей приведены алгоритмы генерации таблицы подстановок, которые можно запустить в оригинальном виде с помощью SageMath.
Заключение
В данной статье мы познакомились с основными криптоалгоритмами, которые приняты в качестве стандартов ГОСТ и получили базовое представление об их работе. А также, привели примеры работ по криптоанализу Кузнечика и Стрибога.