Оценка характеристик перемешивания хэш-функций семейства MD | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/33

Оценка характеристик перемешивания хэш-функций семейства MD

Матрично-графовый подход (МГП), нашедший успешное применение к оценке свойств итеративных блочных шифров и генераторов ключевого расписания, впервые представлен как инструмент оценивания перемешивающих свойств алгоритмов хэширования. Особенность применения МГП к хэш-функциям связана с неочевидностью построения перемешивающих матриц, характеризующих зависимость битов сгенерированного хэш-значения от битов исходного сообщения. Для хэш-функций MD4, MD5, SHA-1, SHA-256 построены перемешивающие матрицы порядка 512 + n, где n - длина блока, с которым оперирует односторонняя функция сжатия алгоритма хэширования при обработке 512-битового блока входного сообщения (n = 128 для MD4 и MD5, n = 160 для SHA-1 и n = 256 для SHA-256). К исследованным характеристикам перемешивания относятся локальные экспоненты перемешивающих матриц, то есть для каждой матрицы M определено наименьшее натуральное число 7, такое, что при любом натуральном т ^ 7 положительны все столбцы матрицы MT с номерами 513, 514,..., 512 + n. Значения локальных экспонентов являются нижними оценками числа итераций, после которых каждый бит сгенерированного хэш-значения может существенно зависеть от всех битов исходного сообщения. Полученные значения (7 = 21 для MD4, MD5, SHA-256 и 7 = 23 для SHA-1) косвенно свидетельствуют о схожих криптографических качествах рассмотренных алгоритмов хэширования, несмотря на варианты их усиления за счёт увеличения длины блока и усложнения функции сжатия.

Evaluation of mixing characteristics for merkle - damgard hash functions.pdf Введение В основе принципа перемешивания, важного для многих криптографических алгоритмов, лежит существенная нелинейная зависимость выходных данных от элементов входа. Для оценки множества существенных переменных композиции преобразований векторного пространства применяется матрично-графовый подход, теоретические основы которого изложены в [1]. Глубина итерации преобразования, при которой каждый бит выходного значения может зависеть от всех битов входа, оценивается снизу значением экспонента примитивного перемешивающего орграфа. В течение последних лет МГП нашёл успешное применение для исследования свойств итеративных блочных шифров и генераторов ключевого расписания [2-4], для которых перемешивающие матрицы, характеризующие зависимость координатных функций выхода от переменных входа, строятся достаточно просто, в отличие от аналогичных матриц для алгоритмов хэширования. В работе представлен способ применения МГП для оценки характеристик перемешивания хэш-функций, реализующих структуру Меркла - Дамгарда (алгоритмы MD4, MD5, SHA-1, SHA-2). 1. Конструкция MD Конструкция Меркла - Дамгарда, представленная в 1979 г. в диссертации Ральфа Меркла, лежит в основе большинства хэш-функций, разработанных в период с 1990 по 2008 г. Суть конструкции заключается в итеративном процессе последовательных преобразований, когда на вход каждой итерации поступает блок исходного текста и выход предыдущей итерации. Меркл и Дамгард независимо друг от друга показали, что если функция сжатия устойчива к коллизиям, то и хэш-функция будет также устойчива. В докладе рассматриваются известные хэш-функции из семейства MD с длиной блока текста 512 бит. Дадим краткое описание алгоритмов [5, 6]. Обозначим через V множество всех двоичных векторов длины r, 0 - операция XOR-сложения двоичных векторов, Ш - операция сложения по модулю 232. Пусть X - исходное сообщение, разбитое на t ^ 1 блоков x1, ...,xt, x G V512, i = 1,2, ...,t, последний блок дополняется битовой строкой 1||0 ... 0 до получения блока размером 448 бит, к которому затем добавляют длину исходного (недополненного) сообщения X, представленную в виде 64-битовой строки. Хэш-функции семейства MD построены на основе односторонней функции сжатия , Нг-1) = H, i = 1,...,t, H G V^, H0 - фиксированное начальное заполнение, n = 128 для MD4 и MD5, n = 160 для SHA-1 и n = 256 для SHA-256. Роль функции сжатия может осуществлять любой блочный шифр Ex , p(X, H) = Ex (H) 0 H. Преобразования EX алгоритмов MD4, MD5, SHA-1, SHA-2 построены на основе регистров сдвига с 32-битовыми ячейками. Регистры имеют схожие принципы функционирования. Блок открытого текста длиной 512 бит записывается в первый регистр сдвига длины 16 над V32 (изображён слева на рис. 1-3), выход с каждого такта подаётся на вход второго регистра над V32 (изображён справа на рис. 1-3), начальным заполнением которого является значение H0. Последнее состояние, в которое перейдёт второй регистр после выполнения всех тактов, определяет искомое хэш-значение Ht. Для усложнения на каждом такте с номером j происходит суммирование с заранее заданными константами Cj и применяются функции f обратных связей нелинейных регистров, которые меняются в зависимости от такта. Алгоритм MD4 (рис. 1, без пунктирной стрелки) реализует 48 тактов, MD5 (рис. 1, c пунктирной стрелкой) - 64 такта. В спецификации RFC 1321 для каждого такта с номером j определены циклические сдвиги влево Sj, константы Cj и функции f. Алгоритмы MD4 и MD5 не считаются надёжными, для них найдены способы нахождения коллизий с приемлемой вычислительной сложностью. Рис. 1. Регистровое преобразование алгоритмов MD4 и MD5 Алгоритм SHA-1 реализует 80 тактов и считается усиленной версией MD5. Несмотря на известные успешные атаки, SHA-1 продолжает использоваться в почтовых программах, приложениях и сетевых протоколах передачи данных. В схеме на рис. 2 числа в кругах обозначают циклические сдвиги влево на соответствующее число бит, константы Cj и функции f определены в спецификации RFC 3174. Рис. 2. Регистровое преобразование алгоритма SHA-1 К семейству SHA-2 относятся идентичные алгоритмы (SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 и SHA-512/224), которые усиливают SHA-1 и считаются достаточно надёжными, но работают в несколько раз медленнее своих предшественников. На рис. 3 представлена схема SHA-256, алгоритм реализует 64 такта, константы Cj и преобразования Maj, Ch, S0, Si, a0, a1 описаны в стандарте FIPS PUB 180-4. Рис. 3. Регистровое преобразование алгоритма SHA-256 2. Оценка перемешивающих свойств с использованием МГП Особенность применения МГП к оценке перемешивающих свойств алгоритмов хэширования связана с неочевидностью построения перемешивающих матриц, характеризующих зависимость битов сгенерированного хэш-значения от битов исходного сообщения. Опишем способ построения перемешивающих матриц для регистровых преобразований хэш-функций MD4, MD5, SHA-1, SHA-256. Используем следующие обозначения: - M(ip1) -перемешивающая матрица размера 512 х 512 преобразования первого регистра сдвига (слева на рис. 1-3); - M(^2) -перемешивающая матрица размера n х n преобразования второго регистра сдвига (справа на рис. 1-3); - J - перемешивающая матрица размера 32 х n, определяющая зависимость состояния регистра от выходного значения регистра на каждом такте; - OmXr - матрица из m нулевых строк и r нулевых столбцов. В соответствии со схемами из п. 1, перемешивающие матрицы M регистровых преобразований MD4 и MD5 имеют порядок 640, SHA-1 - 672, SHA-256 -768. Блоковый вид перемешивающих матриц M представлен на рис. 4. M (

Ключевые слова

алгоритмы хэширования, структура Меркла - Дамгарда, матрично-графовый подход, перемешивающие свойства, hash functions, Merkle - Damgard structure, matrix-graph approach, mixing properties

Авторы

ФИООрганизацияДополнительноE-mail
Коренева Алиса МихайловнаООО «Код Безопасности»ведущий системный аналитикalisa.koreneva@gmail.com
Всего: 1

Ссылки

Fomichev V. M., Avezova Ya. E., Koreneva A. M., and Kyazhin S. N. Primitivity and local primitivity of digraphs and nonnegative matrices // J. Appl. Industr. Math. 2018. V. 12. No. 3. P. 453-469.
Fomichev V.M., Koreneva A. M., Miftahutdinova A. R., and Zadorozhniy D. I. Evaluation of the maximum productivity for block encryption algorithms // VII Симп. «Современные тенденции в криптографии» CTCrypt 2018. https://ctcrypt.ru/files/files/2018/17_ Koreneva.pdf
Fomichev V. M. and Koreneva A. M. Mixing properties of modified additive generators // J. Appl. Industr. Math. 2017. V. 11. No. 2. P. 215-226.
Коренева А. М., Мартышин В. Н. Экспериментальное исследование экспонентов раундо-вых перемешивающих матриц обобщённых сетей Фейстеля // Прикладная дискретная математика. Приложение. 2016. №9. C. 48-51.
Авезова Я. Э. Современные подходы к построению хеш-функций на примере финалистов конкурса SHA-3 // Вопросы кибербезопасности. 2015. №3(11). C. 60-67.
Черемушкин А. В. Криптографические протоколы. Основные свойства и уязвимости: учеб. пособие для студ. учреждений высш. проф. образования. М.: Издательский центр «Академия», 2009. 272 с.
 Оценка характеристик перемешивания хэш-функций семейства MD | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/33

Оценка характеристик перемешивания хэш-функций семейства MD | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/33