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

Содержание

Криптографические 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 бит последней итерации.

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

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

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

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

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

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 приведено в таблице

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

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 - хэш произвольной длины.

Сравнение 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....

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