Хеш-функции

В данной статье описаны принципы построения хеш-функций. Описана конструкция Меркла - Дамгарда и ее развитие в схемах Рабина, Девиса-Мейера, Миагучи-Пренеля, выделены их различия. Приведены результаты криптоанализа SHA-2, SHA-3, Whirlpool, позволяющие сделать вывод о дальнейшем развитии хеш-функций.

Ключевые слова: хеш-функции, cхема Меркла ­- Дамгарда, SHA-2, SHA-3, Whirlpool

Содержание

1. Введение

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

Требования к криптографически стойким хэш-функциям:

  • Для заданного значения хэш-функции X должно быть невозможно вычислить блок данных M, для которого H(M) = X.
  • Стойкость к коллизиям первого рода: для заданного сообщения M должно быть невозможно подобрать другое сообщение N, для которого H(M) = H(N).
  • Стойкость к коллизиям второго рода: должно быть невозможно подобрать пару сообщений (M, M prime ), имеющих одинаковый хэш.
  • Для криптографических хэш-функций также важно, чтобы при малейшем изменении аргумента значение функции сильно изменялось (лавинный эффект).

Математически хэш функцию можно записать в виде: H(M) = X, где M – исходное сообщение, X – значение хэш-функции.

Функции хеширования могут применяться в качестве криптографических генераторов псевдослучайных чисел для создания нескольких ключей на основе одного секретного ключа. Криптографические хеш-функции используют для защиты информации от несанкционированного доступа. Примером таких функций являются MD5, SHA-1 и SHA-2. Также хеш-функции применяют в базах данных для хранения паролей и организации хеш-таблиц.

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

2. Структура хеш-функций

2.1 Итеративная последовательная схема

Схема Меркла-Дамгарда является основанием для многих функций криптографического хэширования. Cжимающая функция f преобразует k блоков, размер каждого состоит из n бит. В качестве начального значения переменной H sub 0 используется вектор инициализации IV. Каждый следующий блок данных объединяется с выходным значением сжимающей функции на предыдущей итерации. Если длина блока H sub m < n, блок дополняется длиной сообщения и «0» битами. Значением хеш-функции являются выходные n бит последней итерации. Схема приведена на Рис. 1.

Алгоритм хеширования намного легче реализовать по сравнению с функциями, которые напрямую работают со значениями переменной длины. Итеративная структура позволяет начинать вычисление хеша сообщения, как только у нас появится часть этого cообщения. Благодаря этому в приложениях, работающих с поточными данными, можно хешировать сообщение не сохраняя данные в буфере. Несмотря на популярность схемы Меркеля-Дамгарда, ряд работ показал недостатки данной конструкции, связанные с множественными коллизиями [2], дополнением сообщения до нужной длины, нахождением второго прообраза [3].

2.2 Функция сжатия

Односторонняя функция сжатия
функция для преобразования двух входных блоков фиксированной длины в выходной блок фиксированной длины.

В настоящее время популярны два подхода для создания хэш-функций. В первом подходе создается "специальная" функция сжатия: она разработана только для этой цели. Во втором подходе блочный шифр с симметричными ключами служит функцией сжатия.

3. Примеры хеш-функций

3.1 "Специальные" хеш-функции

3.1.1 SHA-2

В 1993 году национальный Институт Стандартов и Технологии (NIST - National Institute of Standards and Technology) разработал алгоритм безопасного хеширования SHA-0. В 1995 г. он был пересмотрен и опубликован под названием FIP 180-1 (SHA-1). С публикацией в 2001 году FIPS PUB 180-2, NIST добавил дополнительные хэш-функции в семейство SHA:SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 и SHA-512/224. Алгоритмы известны под общим названием SHA-2.

Основой для SHA-2 является структура Меркла — Дамгарда. Входное сообщение разбивается на блоки длины L. Для SHA-224 и SHA-256 L = 512 бит, для SHA-384,-512,-512/256, -512/224 L = 1024 бит. На каждом раунде в функцию сжатия поступают входной блок сообщения и выход предыдущего блока. Хэш блока M sub i равен H sub i = f(M sub i, H sub {i-1}). Хэш-значением всего сообщения является выход последнего блока. Для SHA-224 и SHA-256 0 <=i <=60, для SHA-384,-512,-512/256, -512/224 0 <=i <= 80.

Ниже приведена схема одной иттерации для SHA-2:

Сравнение SHA-1 и SHA-2 приведено в таблице

Алгоритм Длина сообщения (в битах) Длина блока (в битах) Длина слова (в битах) Длина дайджеста сообщения (в битах) Безопасность (в битах)
SHA-1 < 2 sup 64 512 32 160 80
SHA-256 < 2 sup 64 512 32 256 128
SHA-384 < 2 sup 128 1024 64 384 192
SHA-512 < 2 sup 128 1024 64 512 256

В марте 2008 года индийские исследователи Сомитра Кумар Санадия и Палаш Саркар опубликовали найденные ими коллизии для 22 итераций SHA-256 и SHA-512. В сентябре 2008 года они представили метод конструирования коллизий для 21 итерации SHA-2. Было принято решение отказаться от SHA-2,и 2 октября 2012 года NIST утвердил в качестве стандарта SHA-3 алгоритм Keccak.

3.1.2 SHA-3

Алгоритм хеширования, разработанный группой авторов во главе с Йоаном Дайменом. 2 октября 2012 года Keccak стал победителем конкурса NIST. 5 августа 2015 года алгоритм утверждён и опубликован в качестве стандарта FIPS 202. Алгоритм SHA-3 построен по принципу криптографической губки.

На начальной стадии задаётся исходное состояние из нулевого вектора размером до 1600 бит. Затем производится операция xor фрагмента исходного сообщения P sub 0 с фрагментом исходного состояния размером r, оставшаяся часть состояния остаётся незатронутой. Результат обрабатывается функцией f, и так повторяется до исчерпания блоков исходного сообщения. Функция f выполняет перемешивание внутреннего состояния алгоритма. Состояние представляется в виде массива 5×5, элементами которого являются 64-битные слова, инициализированные нулевыми битами. Функция f выполняет 24 раунда, выход функции f - хэш произвольной длины.

Keccak – стойкая хеш-функция. Сложность атаки на все 24 раунда в 2010 году составила 2 sup 1590 и была улучшена в 2011 до 2 sup 1579.

3.2 Хэш-функции, основанные на блочных шифрах

В качестве функции сжатия можно использовать блочный шифр с симметричными ключами, например трехкратный DES или AES. Рассмотрим несколько схем для построения сжимающей функции

3.2.1 Сxема Рабина

Сxема Рабина базируется на схеме Меркеля-Дамгарда. Функция сжатия заменяется любым алгоритмом шифрования. Входами функции сжатия являются блок сообщения и выход предыдущего блока. Выход представляет собой дайджест сообщения. Иными словами дайджест сообщения M sub i равен H sub i = E(M sub i, H sub {i-1}). Хэш-значением всего сообщения является выход последнего блока. Размер дайджеста совпадает с размером блочного шифра данных в основной криптографической системе.

3.2.2 Схема Девиса-Мейера (Davies-Mayer)

В схеме Девиса-Мейера, в отличии от схемы Рабина блок H sub i и зашифрованый текст складываются с помощью XOR и создается новый блок H sub {i+1}.

3.2.3 Схема Миагучи-Пренеля (Miyaguchi–Preneel)

Чтобы сделать алгоритм более устойчивым к атаке, исходный текст M sub i, блок H sub i и зашифрованный текст складываются с помощью XOR и создают новый блок H sub {i+1}. Эта схема используется в Whirlpool для создания хэш-функции.

3.2.4 Криптогафическая хэш-функция Whirlpool

Whirlpool: криптографическая хеш-функция, разработанная Винсентом Риджменом и Пауло Баретто. Впервые опубликована в ноябре 2000 года. Осуществляет хэширование входного сообщения с длиной до 2256 бит. Ообрена европейской организацией NESSIE (New European Schemes for Signature, Integrity and Encryption - Новые европейские схемы подписей, целостности и шифрования).

С момента создания в 2000 году Whirlpool дважды подвергалась модификации. Первая версия, WHIRLPOOL-0, была представлена в качестве кандидата в проекте NESSIE в 2000 году.

Модификация WHIRLPOOL-0, названная WHIRLPOOL-T, в 2003 году была добавлена в перечень рекомендованных к использованию криптографических функций NESSIE. Изменения касались блока подстановки S-Box: в первой версии структура S-Box не была описана, и он генерировался совершенно произвольно. В новой версии S-Box приобрёл чёткую структуру. В 2004 году был обнаружен дефект в диффузных матрицах WHIRLPOOL-T [7] После его исправления была принята конечная версия Whirlpool.

В 2009 году был опубликован новый способ атаки на хеш-функции - The Rebound Attack [8].Удалось сгенерировать коллизию для 4.5 раундoв Whirlpool со сложностью 2120. Однако, данная атака не сильно повлияла на криптостойкость Whirlpool, сложность вычислений оказалась достаточно высока. На сегодняшний день хеш-функция Whirlpool устойчива ко всем видам криптоанализа. Для построения Whirlpool используется структура Меркла - Дамгарда и односторонняя функция сжатия Миагучи-Пренеля.

4. Заключение

Коллизии существуют для большинства хеш-функций, но для криптографически стойких хеш-функций частота их возникновения минимальна. Если для некоторой хеш-функции находится способ получения коллизий существенно более быстрый, чем полный перебор, то эта хеш-функция перестаёт считаться криптостойкой и использоваться для передачи и хранения секретной информации. В заключение отметим, большинство хеш-функций основывается на итеративных блочных шифрах, взлом шифра ведет к взлому хеш-алгоритма. Появление в 2014 году атак на алгоритм Keecak позволяет сделать вывод о том, что в скором времени появятся новые, усовершенствованные криптографические алгоритмы.

5. Список литературы

  1. Schneier Bruce, Ferguson Niels, «Practical cryptography» - Inc, Wiley Publishing, p 432 ,2003.
  2. Antoine Joux, «Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions», In M. Franklin, Advances in Cryptology - CRYPTO 2004, Vol. 3152 of Lecture Notes in Computer Science, pp. 306–316, Springer, 2004.
  3. Ueli Maurer, Renato Renner, Clemens Holenstein, «Indiff erentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology», In M. Naor , Theory of Cryptography, First Theory of Cryptography Conference, Vol. 2951 of Lecture Notes in Computer Science, pp. 21-39, Springer, 2004.
  4. Somitra Kumar Sanadhya, Palash Sarkar, «Deterministic Constructions of 21-Step Collisions for the SHA-2 Hash Family», Information Security, 11th International Conference, ISC 2008, Taipei, Taiwan
  5. Ming Duan, Xuejia Lai, «Improved Zero-Sum Distinguisher for Full Round Keccak-f Permutation», editors, Chinese Science Bulletin, Vol. 57, Issue 6, pp. 694-697, SP Science China Press, 2012.
  6. Itai Dinur, Pawe Morawiecki, Josef Pieprzyk, Marian Srebrny, and Micha Straus, «Practical Complexity Cube Attacks on Round-Reduced Keccak Sponge Function», Cryptology ePrint Archive, 2014.
  7. Taizo Shirai, Kyoji Shibutani, «On the diffusion matrix employed in the Whirlpool hashing function» - NESSIE public report, 2003
  8. Florian Mendel, Christian Rechberger, Martin Schlaffer, Soren S. Thomsen, «The Rebound Attack: Cryptanalysis of Reduced Whirlpool and Grostl», Unpublished Manuscript

КатегорияКриптография