I Ключ Шифрование

Шифрование I Ключ]

Ключ Шифрование

Рис. 18-14. MDC-4.

Эти схемы были проанализированы в [925, 1262]. Они безопасны с учетом сегодняшних возможностей вычислительной техники, но их надежность не так велика, как хотелось разработчикам . Их устойчивость к дифференциальному криптоанализу при DES в качестве блочного алгоритма была рассмотрена в [1262].

MDC-2 и MDC-4 запатентованы [223].

Хэш-функция AR

Хэш-функция AR б1ла разработана Algorithmic Research, Ltd. и затем распространена ISO только для информации [767]. Ее базовая структура является вариантом используемого блочного шифра (DES в упомянутой статье) в режиме CBC. Выполняется XOR последних двух блоков шифротекста, константы и текущего блока сообщения, результат шифруется алгоритмом . Хэш-значением являются последние вычисленные два блока шифротекста. Сообщение обрабатывается дважды, двумя различными ключами, поэтому скорость хэширования равна 1/2. Первым ключом служит 0x0000000000000000, вторым - 0x2a41522f4446502a, а значение константы c равно 0x0123456789abcdef. Результат сжимается до одного 128-битового хэш-значения. Подробности приведены в [750].

H, = Ek(M, © H,-1 © H,-2 © c) © M,

Функция выглядит привлекательной, но не является безопасной . После некоторой значительной предобработки становится возможным легко находить сообщения с одинаковым хэш-значением [416].

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

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

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

(1) При помощи линейного смешивания M,, H,-.1 и некоторых констант генерируется четыре ключа шифров а-

ния ГОСТ.

(2) Каждый ключ используется для шифрования отличных 64 битов H,-.1 в режиме ECB. Полученные 256 битов сохраняются во временной переменной S.

(3) является сложной, хотя и линейной функцией S, и H,-.1.

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

H = f(Z © M,f(L,f(M, Hn)))

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

Другие схемы

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

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

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

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

Я(M) = Me mod n

Еще проще использовать одно сильное простое число в качестве модуля p. Тогда: Я(M) = Me mod ,p

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

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

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

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

Табл. 18-2.

Скорости шифрования некоторых хэш-функций на i486SX/33 МГц

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

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

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

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

CBC-MAC

Простейший способ создать зависящую от ключа однонаправленную хэш-функцию - шифрование сообщения блочным алгоритмом в режимах CBC или CFB. Хэш-значением является последний шифрованный блок , зашифрованный в режимах CBC или CFB. Метод CBC определен в ANSI X9.9 [54], ANSI X9.19 [56], ISO 8731-1 [759], ISO 9797 [763] и австралийском стандарте [1496]. Дифференциальный криптоанализ может вскрыть эту схему, если в качестве блочного алгоритма используется DES с уменьшенным числом этапов или FEAL [1197].

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

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

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

v = v <<< 1

e = v © w

x = ((((e + y) mod 232) V A л C) * (x © M,-)) mod 232-1 y = ((((e + x) mod 232) V B л D) * (y © M,)) mod 232-1

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

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

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

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

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

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

H0 = /н, , где /н - секретный ключ

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

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

Из-за множества вскрытий типа дня рождения, выполненных в сотрудничестве с Доном Копперсмитом , Джунеман предложил вычислять QCMDC четыре раза, используя результат одной итерации в качестве IV для