Хэш-функция ГОСТ

Эта хэш-функция появилась в России и определена в стандарте ГОСТ Р 34.11.94 [657]. В ней используется блочный алгоритм ГОСТ (см. раздел 14.1), хотя теоретически может использоваться любой блочный алгоритм с 64-битовым блоком и 256-битовым ключом. Функция выдает 256-битовое хэш-значение.

Функция сжатия, Я, = f(M„H_lA) (оба операнда - 256-битовые величины) определяется следующим образом:

(1) При помощи линейного смешивания М„ Я,_ч и некоторых констант генерируется четыре ключа шифрова­ния ГОСТ.

(2) Каждый ключ используется для шифрования отличных 64 битов Я,_ч в режиме ЕСВ. Полученные 256 би­тов сохраняются во временной переменной S.

(3) Я, является сложной, хотя и линейной функцией S, М,- и H_t.\.

Хэш-значение последнего блока сообщения не является его окончательным хэш-значением. На деле исполь­зуется три переменные сцепления: Н_п - это хэш-значение последнего блока, Z - это XOR всех блоков сообщения, a L - длина сообщения. С использованием этих переменных и дополненного последнего блока М', окончательное хэш-значение равно:

Я = f(Z © M',f(L,f(M', #„)))

Документация немного запутана (и на русском языке), но я думаю, что понял все правильно. Во всяком слу­чае эта хэш-функция определена как часть российского Стандарта цифровой подписи (см. раздел 20.3).

Другие схемы

Ральф Меркл предложил схему, использующую DES, но она медленна - обрабатывает только семь битов со­общения за итерацию, и каждая итерация состоит из двух шифрований DES [1065, 1069]. Другая схема [1642, 1645] небезопасна [1267], когда-то она предлагалась в качестве стандарта ISO.

18.12 Использование алгоритмов с открытым ключом

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

Вот пример, использующий RSA. Если М - это хэшируемое сообщение, п - произведение двух простых чисел р и д, а е - другое большое число, взаимно простое с (р - 1)(д - 1), то хэш-функция, ЩМ), будет равна

ЩМ) =Afmod n

Еще проще использовать одно сильное простое число в качестве модуля р. Тогда:

ЩМ) =Af mod p

Вскрытие этой проблемы возможно не легче, чем поиск дискретного логарифма е. Проблема этого алгорит­ма состоит в том, что он намного медленнее, чем другие обсуждаемые алгоритмы. По этой причине я не сове­тую его.

18.13 Выбор однонаправленной хэш-функции

Лучшими кажутся SHA, MD5 и схемы, основанные на блочных шифрах. Другие на самом деле не были и с-следованы в достаточной степени. Я голосую за SHA. У нее более длинное хэш-значение, чем у MD5, она быст­рее, чем многие схемы с блочными шифрами, и разработана NSA. Я верю в криптоаналитические возможности NSA, даже если они не публикуют свои результаты.

В 16-й для сравнения приведены временные соотношения для некоторых хэш-функций. They are meant for comparison purposes only.

Табл. 18-2. Скорости шифрования некоторых хэш-функций Hai486SX/33 МГц

Алгоритм	Длина хэш-значения Ско	рость шифров
Одновременная схема Davies-Meyer (с IDEA)
Davies-Meyer (с DES)
Хэш-функция ГОСТ		И
HAVAL (3 прохода)	переменная
HAVAL (4 прохода)	переменная
HAVAL (5 прохода)	переменная
MD2
MD4
MD5
N-хэш (12 этапов)
N-хэш (15 этапов)
RIPE-MD
SHA
Snerra (4 прохода)
Snerra (8 проходов)

18.14 Коды проверки подлинности сообщения

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

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

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