Эта хэш-функция появилась в России и определена в стандарте ГОСТ Р 34.11.94 [657]. В ней используется блочный алгоритм ГОСТ (см. раздел 14.1), хотя теоретически может использоваться любой блочный алгоритм с 64-битовым блоком и 256-битовым ключом. Функция выдает 256-битовое хэш-значение.
Функция сжатия, Я, = f(M„HlA) (оба операнда - 256-битовые величины) определяется следующим образом:
(1) При помощи линейного смешивания М„ Я,ч и некоторых констант генерируется четыре ключа шифрования ГОСТ.
(2) Каждый ключ используется для шифрования отличных 64 битов Я,ч в режиме ЕСВ. Полученные 256 битов сохраняются во временной переменной S.
(3) Я, является сложной, хотя и линейной функцией S, М,- и Ht..
Хэш-значение последнего блока сообщения не является его окончательным хэш-значением . На деле используется три переменные сцепления: Нп - это хэш-значение последнего блока, 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 может быть преобразован в однонаправленную хэш-функцию с помощью раскрытия ключа.