Ключевые функции хэширования
В криптографических приложениях к ключевым функциям хэширования предъявляются следующие основные требования:
· невозможность фабрикации;
· невозможность модификации.
Первое требование означает высокую сложность подбора сообщения с правильным значением свертки. Второе — высокую сложность подбора для заданного сообщения с известным значением свертки другого сообщения с правильным значением свертки.
Иногда эти свойства объединяют в одно более сильное свойство — свойство вычислительной устойчивости. Это требование означает высокую сложность подбора для заданного множества сообщений {x1,…,xi} (быть может, пустого) с известными значениями сверток еще одного сообщения х, , с правильным значением свертки (возможен случай
)
Заметим, что здесь и всюду ниже слова “высокая сложность” означают такую вычислительную сложность задачи, при которой ее решение с использованием вычислительной техники за реальное время невозможно.
Ключевые функции применяются в ситуациях, когда стороны доверяют друг другу и могут иметь общий секретный ключ.
Обычные атаки на ключевые хэш-функции заключаются в имитации, то есть в передаче сфабрикованных сообщений в пустом канале, а также в подмене передаваемых сообщений с целью навязывания приемной стороне ложных сообщений.
В качестве примерарассмотрим широко распространенную хэш-функцию, построенную на основе одношаговой сжимающей функции вида
где Еk— алгоритм блочного шифрования.
Для вычисления значения h(M) сообщение М представляется в виде последовательности n -битовых блоков М1, М2,.., МN. Если при этом длина сообщения не кратна длине блока, то последний блок неким специальным образом дополняется до полного блока. Алгоритм вычисления свертки имеет следующий вид:
![]() ![]() ![]() | (2) |
Еще одной основой для построения ключевых хэш-функций могут служить бесключевые хэш-функции. При этом для вычисления значения свертки ключ приписывается к исходному сообщению.
Заметим, что если ключ просто дописывать в начало или в конец исходного сообщения, то это может приводить к потенциальным слабостям, позволяющим в некоторых случаях осуществлять модификацию сообщений.
В связи с этим более предпочтительными являются способы введения ключа, при которых ключ вставляется в сообщение не один, а, по крайней мере, два раза. Указываются два таких способа:
где у, у1 и у2 — дополнения ключа kдо размера, кратного длине блока n. Для определенных бесключевых хэш-функций h такой подход позволяет строить эффективно вычислимые и устойчивые к атакам ключевые хэш-функции. Недостатком такого метода является слишком большая длина n свертки. Дело в том, что для целей проверки целостности обычно выбирают длину свертки n в пределах , а для аутентификации необходимо условие
.
Ключевые хэш-функции используются только в системах с доверяющими друг другу пользователями.