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

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

· однонаправленность,

· устойчивость к коллизиям,

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

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

Пусть Е_k — алгоритм блочного шифрования, n — размер блока, l — размер ключа и G — некоторое отображение, ставящее в соответствие вектору длины n вектор длины l. Рассмотрим следующие одношаговые сжимающие функции, построенные на основе алгоритма Е_k:

а) (Дэвис — Мейер);

б) (Матиас — Мейер — Осеас);

в) (Миагучи — Принель).

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

в которой переставляет произвольные полублоки а, b, с, d п о правилу . Такой подход, использующий схему (б), реализован в конструкции одношаговой функции MDC-2.

Другие примеры бесключевых хэш-функций дают известные алгоритмы MD-4, MD-5 и SHA. Они оперируют с блоками длины я, совпадающей с длиной результирующего значения свертки, причем n = 128 для алгоритма MD-4 и n = 160 для MD-5 и SHA. Указанные алгоритмы спроектированы специально с учетом эффективной реализации на 32- разрядных ЭВМ.

При их использовании исходное сообщение М разбивается на блоки длиной m = 512 бит. Последний блок формируется путем дописывания к концу сообщения комбинации 10...0 до получения блока размера 448 бит, к которому затем добавляется комбинация из 64 бит, представляющая битовую длину сообщения. Затем вычисляется значение свертки согласно процедуре (1) с использованием одношаговой сжимающей функции, заданной формулой , где х — блок сообщения длины m = 512 бит, Н - блок из n бит, а Е_x — некоторое преобразование множества блоков. Значение начального вектора определяется в описании преобразования Е_x.

Бесключевые хэш-функции используются в любых системах.

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

Бесключевые хэш—функции чаще применяются для алгоритмов блочного шифрования.