Основы. Функции хэширования

Основы. Функции хэширования

03.03.2018

Функции хэширования #

Основные определения, свойства и прочее…

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

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

Криптографической функцией хэширования (хэш-функцией) H называется отображение множества всех возможных сообщений (представленных в двоичном виде) во множество двоичных векторов конечной фиксированной длины n (множество хэш-значений или хэш-кодов). Не следует путать понятие криптографической хэш-функции с понятием хэш-функции, часто используемом в программировании. Хэш-функция, используемая в программировании, должна иметь определенные статистические свойства (распределение значений хэш-кодов должно быть близко к случайному равновероятному распределению); криптографическая хэш-функция должна удовлетворять определенным криптографическим требованиям (см. ниже).

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

  1. По заданному значению хэш-кода h должно быть невозможно за приемлемое время (с вероятностью, являющейся пренебрежительно малой) найти такое сообщение M, что H(M) = h. Данная задача называется задачей нахождения (построения) прообраза хэш-функции.
  2. По заданному сообщению M должно быть невозможно за приемлемое время (с вероятностью, являющейся пренебрежительно малой) найти такое сообщение M’, отличное от M, что H(M) = H(M’). Данная задача называется задачей нахождения (построения) второго прообраза хэш-функции.
  3. Должно быть невозможно за приемлемое время (с вероятностью, являющейся пренебрежительно малой) найти такие два различных сообщения M и M’, что H(M) = H(M’). Данная задача называется задачей нахождения (построения) коллизии хэш-функции.

Важным криптографическим примитивом, который, как правило, строится на основе хэш-функции, является ключевая функция хэширования (message authentication code, MAC). Ключевая функция хэширования также действует на множестве всех возможных сообщений, а ее значения лежат во множестве двоичных векторов конечной фиксированной длины n, однако в процессе вычисления хэш-кода используется некоторый секретный параметр – ключ K (как правило, представляющий собой также двоичный вектор конечной длины). К ключевым функциям хэширования также предъявляется требование о быстроте и эффективности вычисления хэш-кода. Основные криптографические требования к ключевым функциям хэширования можно сформулировать следующим образом:

  1. Без информации о секретном ключе K для любого сообщения M должно быть невозможно за приемлемое время (с вероятностью, не являющейся пренебрежительно малой) найти значение ключевого хэш-кода H(K,M).
  2. Не располагая информацией о секретном ключе K, но имея набор пар сообщение – значение его ключевого хэш-кода, т.е. набор (Mi, H(K,Mi)), где сообщения Mi могут быть выбраны любым специальным образом, должно быть невозможно за приемлемое время (с вероятностью, не являющейся пренебрежительно малой) найти значение ключа K или вычислить значение ключевого хэш-кода H(K,M) для любого M, отличного от всех Mi.

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

Аутентификация (целостность) сообщений #

Наверное, простейшим способом обеспечения аутентификации (целостности) сообщений является следующий. К сообщению M добавляется значение ключевого хэш-кода H(K,M). Чтобы подделать сообщение (M, H(K,M)) необходимо знание секретного ключа K. Проверить аутентичность сообщения может любой пользователь, располагающий знанием ключа K.

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

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

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

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

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

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


Невозможность отказа от авторства (использование хэш-функций при вычислении электронной цифровой подписи) #

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

  1. Длина цифровой подписи является фиксированной и не зависит от длины исходного сообщения.
  2. Как правило, скорость хэширования значительно превосходит скорость вычисления цифровой подписи, поэтому предварительное вычисление хэш-функции от всего сообщения, а затем вычисление цифровой подписи от значения хэш-кода существенно ускоряет процесс вычисления ЭЦП от длинных сообщений.
  3. Использование хэш-функции нивелирует особенности исходного сообщения, которые могут использоваться при построении методов криптографического анализа ЭЦП.

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


Идентификация с использованием паролей #

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


Другие сферы использования хэш-функций #

На основе функций хэширования иногда строятся следующие криптографические примитивы:

  1. Блочные шифры (например, Shacal-2).
  2. Поточные шифры.
  3. Генераторы псевдослучайных чисел.

Итеративная конструкция Меркля-Дамгорда #

По итеративному принципу построено абсолютное большинство хэш-функций, используемых в настоящее время на практике (например, хэш-функции MD5, SHA-1, семейство хэш-функций SHA-2, отечественный стандарт на хэш-функцию ГОСТ Р 34.11-94, ГОСТ 34.11-2018(Стрибог)).

В 1989 году Р. Меркль (Ralph C. Merkle) и И. Дамгорд (Ivan Damgaard) независимо предложили итеративный принцип построения криптографических функций хэширования. Данный принцип позволяет свести задачу построения хэш-функции на множестве сообщений различной длины к задаче построения отображения, действующего на множестве фиксированной конечной длины.

Опишем итеративную конструкцию Меркля-Дамгорда в общем виде. Пусть M – некоторое сообщение, подлежащее хэшированию.

Сообщение M определенным образом дополняется и разбивается на блоки одинаковой фиксированной длины m, т.е. получаем сообщение m1||…||mt. Затем последовательно вычисляются значения некоторой функции g, называемой функцией сжатия (compression function): h(i) = g(h(i-1),mi), i=1,…,t, где h(0) – некоторое фиксированное значение, называемое инициализационным вектором (initialization vector, initial value, IV). Значением итерационной функции хэширования является значение h(t).

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

HMAC #

Конструкция HMAC позволяет построить ключевую функцию хэширования на основе любой бесключевой хэш-функции. Данную конструкцию предложили в 1996 году М. Белларе (Mihir Bellare), Р. Канетти (Ran Canetti), Х. Кравчук (Hugo Krawczyk).

Ключевую хэш-функцию, построенную на основе бесключевой хэш-функции H с использованием конструкции HMAC, принято обозначать HMAC-H (например, HMAC-MD5).

Пусть K – секретный ключ, M – сообщение, подлежащее хэшированию, тогда HMAC-H (K,M) = H((K+opad)||H((K+ipad)||M)), где + – покоординатное сложение векторов по модулю 2 (операция XOR), opad, ipad – некоторые фиксированные константы.

Стойкость конструкции HMAC-H основана на криптографических свойствах хэш-функции H и длине используемого ключа. Конструкция HMAC стандартизирована организациями ANSI, IETF, ISO и NIST. Конструкция HMAC получила столь широкое применение, что само название «HMAC» стало по существу синонимом термина «ключевая хэш-функция».


Вспомогательная литература #

  1. B. Preneel, Analysis and Design of Cryptographic Hash Functions, Technical report, Katholieke Universiteit Leuven, Belgium, 2003.
  2. А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, «Основы криптографии», Гелиос АРВ, М., 2001.
  3. I. Damgaard, A Design Principle for Hash Functions, CRYPTO-89, 1989, pp. 416-427.
  4. R. Merkle, One Way Hash Functions and DES, CRYPTO-89, 1989, pp. 428-446.
  5. HMAC: Keyed-Hashing for Message Authentication, RFC 2104, February 1997.
  6. ANSI X9.71, Keyed Hash Message Authentication Code.
  7. NIST, FIPS PUB 198, The Keyed-Hash Message Authentication Code (HMAC), March 2002.
  8. J. Kim, A. Biryukov, B. Preneel, S. Hong, On the Security of HMAC and NMAC Based on HAVAL, MD4, MD5, SHA-0 and SHA-1, Cryptology ePrint Archive, Report 2006/187, http://eprint.iacr.org/2006/187.pdf ​