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

Содержание

Криптографические 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труктура Меркля-Дамгарда. Cжимающая функция f преобразует m блоков, размер каждого состоит из n бит. Входами функции сжатия являются входной блок сообщения и выход предыдущего блока. Выход представляет собой значение всех функций сжатия до этого момента. Иными словами хэш блока M sub i равен H sub i = f(M sub i, H sub {i-1}). Хэш-значением всего сообщения является выход последнего блока. Если длина блока H sub m < n, H sub m дополняется длиной сообщения и 0. Значением хэш-функции являются выходные n бит последней итерации.

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

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

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

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

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

MD5

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

Согласно алгоритму MD5, исходное сообщение разбивается на блоки по 512 бит. Последний блок дополняется до нужной длины и к нему добавляется длина исходного сообщения в битах. Функция MD5 использует 128-битовое промежуточное состояние, которое разбивается на четыре 32-битовых слова. Функция сжатия h prime состоит из четырех раундов, в каждом из которых выполняется комбинация операций сложения, XOR, AND, OR и операций циклического сдвига бит в 32-битных словами. После четырех раундов функции h prime, входное промежуточное состояние и результат складываются для получения выходного значения функции 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 реализует хэш-функцию, построенную на идее функции сжатия. Входами функции сжатия являются блок сообщения длиной 512 бит и выход предыдущего блока сообщения. Выход представляет собой значение всех хэш-блоков до этого момента. Иными словами хэш блока M sub i равен $$H sub i$ = f(M sub i, H sub {i-1}). Хэш-значением всего сообщения является выход последнего блока.

SHA-1 является безопасным алгоритмом, поскольку в вычислительном отношении невозможно найти сообщение, которое соответствует данному дайджесу сообщения, или найти два разных сообщения, которые производят один и тот же дайджест. Любое изменение сообщения, с очень высокой вероятностью, приведет к изменению дайджеста сообщения.

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

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

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

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

Сxема Рабина

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

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

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

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

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

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

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

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

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

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

Удлинение сообщения

Один из самых серьезных недостатков всех рассмотренных функций хэширования - удлинение сообщения. Пусть некоторое сообщение m разбивается на блоки m sub {1} .. m sub {k} и хэшируется, в результате чего получается значение H. Теперь возьмем сообщение m prime, которое разбивается на блоки m sub {1} .. m sub {k}, m sub {k + 1}. Поскольку первые k блоков сообщения m prime равны первым k блокам сообщения m, значение H(m) соответствует промежуточному результату, полученному при вычислении H(m prime ) после обработки первых k блоков сообщения m prime. Тогда H(m prime ) = H prime (H(m), m sub {k+1} ). Используя MD5 или любую функцию семейства SHA, необходимо конструировать сообщение m prime таким образом, чтобы в его состав включались биты дополнения и поле длины сообщения.

Проблема удлинения сообщения возникла из-за того, что в конце вычисления результата функции хэширования не выполняется никакой специальной обработки данных. Значение h(m) дает злоумышленнику информацию относительно промежуточного состояния, полученного после сжатия первых k блоков сообщения m prime.

Исправление недостатков

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

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

Литература

  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....

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