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

Цель лекции: познакомиться с понятием "хеш-функция", а также с принципами работы таких функций.

Понятие хеш-функции

Хеш-функцией (hash function) называется математическая или иная функция, которая для строки произвольной длины вычисляет некоторое целое значение или некоторую другую строку фиксированной длины. Математически это можно записать так:

h=H(M),

где М – исходное сообщение, называемое иногда прообразом, а h – результат, называемый значением хеш-функции (а также хеш-кодом или дайджестом сообщения (от англ. message digest )).

Смысл хеш-функции состоит в определении характерного признака прообраза – значения хеш-функции. Это значение обычно имеет определенный фиксированный размер, например, 64 или 128 бит. Хеш-код может быть в дальнейшем проанализирован для решения какой-либо задачи. Так, например, хеширование может применяться для сравнения данных: если у двух массивов данных хеш-коды разные, массивы гарантированно различаются; если одинаковые — массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет из-за того, что количество значений хеш-функций всегда меньше, чем вариантов входных данных. Следовательно, существует множество входных сообщений, дающих одинаковые хеш-коды (такие ситуации называются коллизиями ). Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Хеш-функции широко применяются в современной криптографии.

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

Например, пусть исходное сообщение, переведенное в цифровой вид, было следующим (в шестнадцатеричном формате):

3E 54 A0 1F B4

Переведем сообщение в двоичный вид, запишем байты друг под другом и сложим биты в каждом столбике по модулю 2:

0011 1110
0101 0100
1010 0000
0001 1111
1101 0100
----------
0110 0101

Результат ( 0110 0101(2) или 65(16) ) и будет значением хеш-функции.

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

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

Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям:

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

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

hi=H(Mi,hi-1),

где hi-1 – результат, полученный при вычислении хеш-функции для предыдущего блока входных данных.

В результате выход хеш-функции hn является функцией от всех n блоков входного сообщения.

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

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

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

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

Указанный процесс получения и использования имитовставки описан в отечественном стандарте ГОСТ 28147-89. Стандарт предлагает использовать младшие 32 бита блока, полученного на выходе операции шифрования всего сообщения в режиме сцепления блоков шифра для контроля целостности передаваемого сообщения. Таким же образом для формирования имитовставки можно использовать любой блочный алгоритм симметричного шифрования.

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

Таким образом, если обычную схему шифрования сообщения М с помощью блочного шифра f на ключе К мы записывали как E=f(M,K), то схему получения хеш-кода h по описанному выше алгоритму можно представить как

hi=f(hi-1,M)

В качестве начального хеш-кода h0 берут некоторую константу. Шифрование производится в режиме простой замены. При использовании указанного способа размер блока совпадает с длиной ключа и размером хеш-значения будет длина блока.

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

hi=f(M,hi-1)

На самом деле возможны еще несколько схем использования блочного шифра для формирования хеш-функции. Пусть Мi – блок исходного сообщения, hi – значение хеш-функции на i-том этапе, f – блочный алгоритм шифрования, используемый в режиме простой замены, $$\oplus$$ – операция сложения по модулю 2. Тогда возможны, например, следующие схемы формирования хеш-функции:

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

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

Обзор алгоритмов формирования хеш-функций

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

Алгоритм MD5 появился в начале 90-х годов ХХ века в результате усовершенствования алгоритма формирования хеш-функции MD4. Символы в названии "MD" означают Message Digest – краткое изложение сообщения. Автор алгоритмов MD4 и MD5 – Р. Ривест (R.Rivest). В результате использования MD5 для произвольного сообщения формируется 128-битное хеш-значение. Входные данные обрабатываются блоками по 512 бит. В алгоритме используются элементарные логические операции (инверсия, конъюнкция, сложение по модулю 2, циклические сдвиги и др.), а также обыкновенное арифметическое сложение. Комплексное повторение этих элементарных функций алгоритма обеспечивает то, что результат после обработки хорошо перемешан. Поэтому маловероятно, чтобы два сообщения, выбранные случайно, имели одинаковый хеш-код. Алгоритм MD5 имеет следующее свойство: каждый бит полученного хеш-значения является функцией от каждого бита входа. Считается, что MD5 является наиболее сильной хеш-функцией для 128-битного хеш-значения.

Алгоритм SHA (Secure Hash Algorithm – Безопасный хеш-алгоритм) был разработан национальным институтом стандартов и технологии (NIST) США и опубликован в качестве американского федерального информационного стандарта в 1993 году. SHA-1, как и MD5, основан на алгоритме MD4. SHA-1 формирует 160-битное хеш-значение на основе обработки исходного сообщения блоками по 512 бит. В алгоритме SHA-1 также используются простые логические и арифметические операции. Наиболее важным отличием SHA-1 от MD5 является то, что хеш-код SHA-1 на 32 бита длиннее, чем хеш-код MD5. Если предположить, что оба алгоритма одинаковы по сложности для криптоанализа, то SHA-1 является более стойким алгоритмом. Используя атаку методом грубой силы (лобовую атаку), труднее создать произвольное сообщение, имеющее данный хеш-код, а также труднее создать два сообщения, имеющие одинаковый хеш-код.

В 2001 году национальный институт стандартов и технологии США принял в качестве стандарта три хеш-функции с большей длиной хеш-кода, чем у SHA-1. Часто эти хеш-функции называют SHA-2 или SHA-256, SHA-384 и SHA-512 (в названии указывается длина создаваемого алгоритмами хеш-кода). Эти алгоритмы отличаются не только длиной создаваемого хеш-кода, но и используемыми внутренними функциями и длиной обрабатываемого блока (у SHA-256 длина блока – 512, а у SHA-384 и SHA-512 длина блока – 1024 бита). Постепенные усовершенствования алгоритма SHA ведут к увеличению его криптостойкости. Несмотря на отличия рассматриваемых алгоритмов друг от друга, все они являются дальнейшим развитием SHA-1 и MD4 и имеют похожую структуру.

В России принят ГОСТ Р34.11-94, который является отечественным стандартом для хеш-функций. Его структура довольно сильно отличается от структуры алгоритмов SHA-1,2 или MD5, в основе которых лежит алгоритм MD4. Длина хеш-кода, создаваемого алгоритмом ГОСТ Р 34.11-94, равна 256 битам. Алгоритм последовательно обрабатывает исходное сообщение блоками по 256 бит справа налево. Параметром алгоритма является стартовый вектор хеширования – произвольное фиксированное значение длиной также 256 бит. В алгоритме ГОСТ Р 34.11-94 используются операции перестановки, сдвига, арифметического сложения, сложения по модулю 2. В качестве вспомогательной функции в ГОСТ 34.11-94 используется алгоритм по ГОСТ 28147-89 в режиме простой замены.

Ключевые термины

Нash function – хеш-функция.

ГОСТ Р34.11-94 – российский стандарт на функцию хеширования.

Хеш-функция – математическая или иная функция, которая для строки произвольной длины вычисляет некоторое целое значение или некоторую другую строку фиксированной длины.

Хеш-код – результат работы хеш-функции, некоторый характерный "признак" входного массива данных.

Краткие итоги

Хеш-функция – математическая или иная функция, которая для строки произвольной длины (прообраза) вычисляет некоторое целое значение или некоторую другую строку фиксированной длины. Смысл хеш-функции состоит в определении характерного признака прообраза – значения хеш-функции. Это значение обычно имеет определенный фиксированный размер. Хеш-код может быть в дальнейшем проанализирован для решения какой-либо задачи.

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

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

Набор для практики

Вопросы для самопроверки

Упражнения для самопроверки

Пусть хеш-функция y=h(x1x2…xn) определяется как результат выполнения побитовой операции "сумма по модулю 2" для всех байтов сообщения, представленного в двоичном виде. Длина хеш-кода равна 8 битам. Для каждого из шести сообщений, записанных в левом столбце, найдите соответствующий результат вычисления хеш-функции из правого столбца. Все сообщения и значения хеш-функции представлены в шестнадцатеричном формате.