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

Содержание

Криптографические 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 - хэш произвольной длины.

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

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

В качестве функции сжатия можно использовать блочный шифр с симметричными ключами, например трехкратный 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....

Christina Boura, Anne Canteaut, Christophe De Cannière, «Higher Order Diff erential Properties of Keccak and Luff a», In Antoine Joux, editor, Fast Software Encryption, Vol. 6733 of Lecture Notes in Computer Science, 2011, pp. 252- 269, Springer, 2011.

Ming Duan, XueJia? Lai, «Improved Zero-Sum Distinguisher for Full Round Keccak-f Permutation», In Ming Duan, XueJia? Lai, editors, Chinese Science Bulletin, Vol. 57, Issue 6, pp. 694-697, SP Science China Press, 2012.

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