Криптографические xэш - функции

Хэширование

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

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

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

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

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

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

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

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

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

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

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

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

Односторонняя функция сжатия

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

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

Хэш-функции, сделанные на "пустом месте"

MD5

Серия алгоритмов по построению дайджеста сообщения, была разработанна профессором Рональдом Л. Ривестом из Массачусетского технологического института. MD5 был выпущен в 1991 году для замены предыдущего алгоритма, MD4.

Согласно алгоритму MD5, исходное сообщение разбивается на блоки по 512 бит. Последний блок дополняется до нужной длины и к нему добавляется длина исходного сообщения в битах. Функция MD5 использует 128-битовое промежуточное состояние, которое разбивается на четыре 32-битовых слова. Функция сжатия состоит из четырех раундов, в каждом из которых выполняется комбинация операций сложения, XOR, AND, OR и операций циклического сдвига бит в 32-битных словами. После четырех раундов функции , входное промежуточное состояние и результат складываются для получения выходного значения функции $h prime$

Описанный алгоритм весьма эффективен в системах с 32-разрядной архитектурой. Однако, используя парадокс задачи о днях рождения, можно найти реальную коллизию для функции MD5 примерно за $$2 sup 64$ оцениваний функции хэширования, что совершенно не подходит для современных систем. В 2011 году MD5 был признан небезопасным, и было предложено использовать другие алгоритмы хэширования, такие как Whirlpool, и SHA-1.

SHA-1

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

SHA-1  это 160-битовая функция хэширования, основанная на алгоритме MD4. Функция SHA-1 использует 160-битовое промежуточное состояние, которое разбивается на пять 32-битовых слов. Как и MD5, она состоит из четырех раундов, представляющих собой комбинацию элементарных операций над 32- битовыми словами. Вместо того чтобы обрабатывать каждый блок сообщения по четыре раза, SHA-1 использует линейную рекуррентную функцию, чтобы "растянуть" 16 слов блока сообщения до нужных ей 80 слов. В SHA-1 наличие линейной рекуррентной функции гарантирует, что каждый бит сообщения используется функцией перемешивания по меньшей мере десяток раз. Для генерации коллизий достаточно выполнить лишь шагов, что значительно ниже уровня безопасности современных блочных шифров с размерами ключей от 128 до 256 бит.

Сравнение MD5 и SHA-1:

SHA-1 содержит больше шагов (80 вместо 64) и выполняется на 160-битном буфере по сравнению со 128-битным буфером MD5. Таким образом, SHA-1 должен выполняться приблизительно на 25% медленнее, чем MD5 на той же аппаратуре. Оба алгоритма просты и в описании, и в реализации, не требуют больших программ или подстановочных таблиц. Сравнение этих версий приведено в таблице:

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

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

Сxема Рабина

Сxема Рабина базируется на схеме Меркеля-Дамгарда. Функция сжатия заменяется любым алгоритмом шифрования. Блок сообщения используется как ключ; предварительно созданный дайджест используется как исходный текст. Зашифрованный текст - новый дайджест сообщения. Размер дайджеста совпадает с размером блочного шифра данных в основной криптографической системе.

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

В отличии от схемы Рабина использует прямую связь для защиты от атаки "сведения в середину".

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

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

Коллизия хэш-функций

Коллизия хэш-функций

Коллизией хэш-функций называется два различных входных блока данных и таких, что .

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

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

1. Scott, C. A Critical Look at Cryptographic Hash Function Literature / Contini Scott, Steinfeld Ron, Pieprzyk Josef, Matusiewicz Krystian. — New Jersey, USA : World Scientific Publishing, 2008. — 22 p. — http://events.iaik.t....
2. Marc, S. Chosen-prefix collisions for MD5 and applications / Stevens Marc, K. Lenstra Arjen, de Weger Benne // International Journal of Applied Cryptography . — 2012. — pp. 322—359. — https://documents.ep....
3. D., E. 3. RFC 3174, US Secure Hash Algorithm 1 (SHA1) / Eastlake 3rd D., Jones P. — 2001. — 22 p. — https://tools.ietf.o....