Ключевые функции хэширования

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

· невозможность фабрикации;

· невозможность модификации.

Первое требование означает высокую сложность подбора сообщения с правильным значением свертки. Второе — высокую сложность подбора для заданного сообщения с известным значением свертки другого сообщения с правильным значением свертки.

Иногда эти свойства объединяют в одно более сильное свойство — свойство вычислительной устойчивости. Это требование означает высокую сложность подбора для заданного множества сообщений {x₁,…,x_i} (быть может, пустого) с известными значениями сверток еще одного сообщения х, , с правильным значением свертки (возможен случай )

Заметим, что здесь и всюду ниже слова “высокая сложность” означают такую вычислительную сложность задачи, при которой ее решение с использованием вычислительной техники за реальное время невозможно.

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

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

В качестве примера рассмотрим широко распространенную хэш-функцию, построенную на основе одношаговой сжимающей функции вида

где Е_k — алгоритм блочного шифрования.

Для вычисления значения h(M) сообщение М представляется в виде последовательности n -битовых блоков М₁, М₂,.., М_N. Если при этом длина сообщения не кратна длине блока, то последний блок неким специальным образом дополняется до полного блока. Алгоритм вычисления свертки имеет следующий вид:

(2)

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

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

В связи с этим более предпочтительными являются способы введения ключа, при которых ключ вставляется в сообщение не один, а, по крайней мере, два раза. Указываются два таких способа:

где у, у₁ и у₂ — дополнения ключа k до размера, кратного длине блока n. Для определенных бесключевых хэш-функций h такой подход позволяет строить эффективно вычислимые и устойчивые к атакам ключевые хэш-функции. Недостатком такого метода является слишком большая длина n свертки. Дело в том, что для целей проверки целостности обычно выбирают длину свертки n в пределах , а для аутентификации необходимо условие .

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