Это старая версия (1.168) КриптографическиеХэшФункции.

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

Если длина блока H sub m < n, H sub m дополняется длиной сообщения и 0. Значением хэш-функции являются выходные n бит последней итерации.

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

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

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

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

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

MD5

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

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

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

SHA

В 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, SHA-512, SHA-512/256 и SHA-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, SHA-512, SHA-512/256 и SHA-512/224 0 <=i <=60. Ниже приведена схема одной иттерации для SHA-2:

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

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

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

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

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

Сxема Рабина

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

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

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

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

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

Недостатки функций хэшифрования:

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

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

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

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

Литература

  1. Bruce, S. Practical cryptography / Schneier Bruce, Ferguson Niels. — Inc, Wiley Publishing , 2003.
  2. 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....
  3. 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....
  4. D., E. 3. RFC 3174, US Secure Hash Algorithm 1 (SHA1) / Eastlake 3rd D., Jones P. — 2001. — 22 p. — https://tools.ietf.o....

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