7.1. Функции хэширования и целостность данных

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

В криптографии хэш-функции применяются для решения следующих задач:

–построения систем контроля целостности данных при их передаче или хранении,

–аутентификации источника данных.

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

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

Имитовставки, формируемые с помощью ключевых хэш-функций, не должны позволять противнику создавать под­дельные (сфабрикованные) сообщения (fabrication) при ата­ках типа имитация (impersonation) и модифицировать переда­ваемые сообщения (modification) при атаках типа "подмена" (substitution).

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

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

Хэш-функцией называется всякая функция h: Х —> Y, легко вычислимая и такая, что для любого сообщения М значение h(M) = Н (свертка) имеет фиксированную битовую длину.

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

Как правило, хэш-функции строят на основе так называемых одношаговых сжимающих функций у = f(x₁, х₂) двух ременных, где х_i и у – двоичные векторы длины т и п соответственно, причем п – длина свертки. Для получения значения h(M) сообщение М сначала разбивается на блоки длины т (при этом если длина сообщения не кратна т, то последний блок неким специальным образом дополняется до полного), а затем к полученным блокам m₁, М₂,.., М_N применяют следующую последовательную процедуру вычисления свертки:

Н₀ = v, Н_i = f(М_i ,H_i-1), i=1,...,N, h(M)=H_N. (7.1)

Здесь v – некоторый фиксированный начальный вектор, Если функция f зависит от ключа, то этот вектор можно по­ложить равным нулевому вектору. Если же функция f не зависит от ключа, то для исключения возможности перебора коротких сообщений (при попытках обращения хэш-функции) этот вектор можно составить из фрагментов, указывающих дату, время, номер сообщения и т. п.

При таком подходе свойства хэш-функции h полностью определяются свойствами одношаговой сжимающей функ­ции f.

Особо выделяют два важных типа криптографических хэш-функции – ключевые и бесключевые. Первые применя­ются в системах с симметричными ключами. Ключевые хэш-функции называют кодами аутентификации сообщений (КАС) (message authentication code (MAC)). Они дают возмож­ность без дополнительных средств гарантировать как пра­вильность источника данных, так и целостность данных в системах с доверяющими друг другу пользователями.

Бесключевые хэш-функции называются кодами обнару­жения ошибок (modification detection code (MDC) или manipulation detection code, message integrity code (МIС)). Они дают возможность с помощью дополнительных средств (на­пример, шифрования, использования защищенного канала или цифровой подписи) гарантировать целостность данных. Эти хэш-функции могут применяться в системах как с дове­ряющими, так и не доверяющими друг другу пользователями. Рассмотрим их более подробно.