Алгоритм проверки подлинности сообщения (Message Authenticator Algorithm, MAA)

Этот алгоритм является стандартом ISO [760]. Он выдает 32-битовое хэш-значение и был спроектирован для мэйнфреймов с быстрыми инструкциями умножения [428].

v = v <<< 1

e = v Å w

x = ((((e + y) mod 2³²) Ú A Ù C) * (x Å M_i)) mod 2³²-1

y = ((((e + x) mod 2³²) Ú B Ù D) * (y Å M_i)) mod 2³²-1

Эти действия повторяются для каждого блока сообщения, M_i, и результирующее хэш-значение получается с помощью XOR xи y.Переменные vи e зависят от ключа. A, B, C и D являются константами.

Возможно, этот алгоритм широко используется, но я не верю, что он достаточно безопасен. Он был разработан давным давно и не слишком сложен.

Двунаправленный MAC

Этот MAC выдает хэш-значение, которое в два раза длиннее блока алгоритма [978). Сначала для сообщения вычисляется CBC-MAC. Затем вычисляется CBC-MAC сообщения с обратным порядком блоков. Двунаправленный MAC просто является объединением этих двух значений. К сожалению эта схема небезопасна [1097].

Методы Джунемана

Этот MAC также называют квадратичным конгруэнтным кодом обнаружения манипуляции (quadratic congruential manipulation detection code, QCMDC) [792, 789]. Сначала разделим сообщение на m-битовые блоки. Затем:

H₀= I_H, , где I_H - секретный ключ

H_i= (H_i-1 + M_i)²mod p, где p - простое число, меньшее 2^m-1, а + обозначает целочисленное сложение.

Джунеман (Jueneman) предлагает n= 16 и p= 2³¹-1. В [792] он также предлагает, чтобы H₁ использовался в качестве дополнительного ключа_, а действительное сообщение начиналось бы с H₂.

Из-за множества вскрытий типа дня рождения, выполненных в сотрудничестве с Доном Копперсмитом, Джунеман предложил вычислять QCMDC четыре раза, используя результат одной итерации в качестве IV для следующей итерации, а затем результаты объединяются в 128-битовое хэш-значение [793]. В дальнейшем эта идея была усилена за счет параллельного выполнения четырех итераций с поперечными связями между ними [790, 791]. Эта схема была взломана Копперсмитом [376].

В другом варианте [432, 434] операция сложения заменена XOR, и используются блоки сообщения, намного меньшие p. Кроме того, был задан H₀, что превратило алгоритм в однонаправленную хэш-функцию без ключа. После того, как эта схема была вскрыта [612], она была усилена для использования в качестве части проекта European Open Shop Information-TeleTrust [1221], процитирована в CCITT X.509 [304] и принята ISO в 10118 [764, 765]. К сожалению Копперсмит взломал и эту схему [376]. В ряде исследований изучалась возможность использовать отличные от 2 основания экспоненты [603], но ни одно не оказалось перспективным.

RIPE-MAC

RIPE-MAC был изобретен Бартом Пренелом [1262] и использован в проекте RIPE [1305] (см. раздел 18.8). Он основан на ISO 9797 [763] и использует DES в качестве функции блочного шифрования. Существует два варианта RIPE-MAC: один, который использует обычный DES, называется RIPE-MAC1, а другой, использующий для еще большей безопасности тройной DES, называется RIPE-MAC3. RIPE-MAGI использует одно шифрование DES на 64-битовый блок сообщения, а RIPE-MAC3 - три.

Алгоритм состоит из трех частей. Во первых, сообщение увеличивается так, чтобы его длина была кратна 64 битам. Затем, увеличенное сообщение разбивается на 64-битовые блоки. Для хэширования этих блоков в один блок используется функция сжатия, зависящая от секретного ключа. На этом этапе используется либо DES, либо тройной DES. Наконец, выход этой функции сжатия подвергается еще одному DES-шифрованию с другим ключом, полученным из ключа, используемого при сжатии. Подробности можно найти в [1305].

IBC-хэш

IBC-хэш - это еще один MAC, используемый в проекте RIPE [1305] (см. раздел 18.8). Он интересен потому, что его безопасность доказана, вероятность успешного вскрытия может быть оценена количественно. К сожалению каждое сообщение должно хэшироваться новым ключом. Выбранный уровень безопасности ограничивает максимальный размер хэшируемого сообщения, чего не делает ни одна другая из рассмотренных в этой главе функция. С учетом этих соображений в отчете RIPE рекомендуется, чтобы IBC-хэш использовалась бы только для длинных, редко посылаемых сообщений. Ядром функции является

h_i= ((M_i mod p)+ v)mod 2ⁿ

Секретный ключ представляет собой пару p и v, где p- n-битовое простое число, а v- случайное число, меньшее 2ⁿ. Значения M_i получаются с помощью строго определенной процедуры дополнения. Вероятности вскрыть как однонаправленность, так и устойчивость к столкновениям, могут быть оценены количественно, и пользователи, меняя параметры, могут выбрать нужный уровень безопасности.