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

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

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

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

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

Иногда эти свойства объединяют в одно более сильное свойство - свойство вычислительной устойчивости. Это требование означает высокую сложность подбора для заданного множества сообщений {x₁,..,x_t}(быть может, пустого) с известными значениями сверток еще одного сообщения х, х ¹х_i, i = 1,...,t, с правильным значением свертки (возможен случай h(x) = h(x,), i Î{1,...,t}).

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

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

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

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

f_k(x, H) = E_k(x Å H),

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

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

H₀ = 0,

Н_i =E_k(М_i Å H_i-1), i = 1,...,N,

h(M) = H_N.

Данный алгоритм фактически совпадает с режимом шифрования со сцеплением блоков CBC с той лишь разницей, что в качестве результата берется не весь шифртекст Н₁,Н₂,..,Н_N, а только его последний блок. Такой режим в ГОСТе 28147-89 называется режимом выработки имитовставки.

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

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

H = h(k, y, M, k) или H = h(k, y₁,h(k, у₂, M)),

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

Существуют также ключевые хэш-функции, не использующие какую-либо основу типа блочного шифрования или вычисления бесключевой хэш-функции, а разработанные независимо с учетом эффективной реализации на современных ЭВМ. Например ключевая хэш-функция, используемая в алгоритме МАА {Message Authenticator Algorithm), утвержденном стандартом ISO 8731-2.