Безопасность MD5

Рон Ривест привел следующие улучшения MD5 в сравнении с MD4 [1322]:

1. Добавился четвертый этап.

2. Теперь в каждом действии используется уникальная прибавляемая константа.

3. Функция G на этапе 2 с ((XaY)v(XaZ)v(YaZ)) была изменена на (XaZ)v(Ya(­Z)), чтобы сделать G менее симметричной.

4. Теперь каждое действие добавляется к результату предыдущего этапа. Это обеспечивает более быст­рый лавинный эффект.

5. Изменился порядок, в котором использовались подблоки сообщения на этапах 2 и 3, чтобы сделать шаблоны менее похожими.

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

Том Берсон (Tom Berson) попытался применить дифференциальный криптоанализ к одному этапу MD5 [144], но его вскрытие не оказалось эффективным ни для одного из четырех этапов. Более успешное вскрытие ден Боера и Босселаерса, использующее функцию сжатия, привело к обнаружению столкновений в MD5 [203, 1331, 1336]. Само по себе это вскрытие невозможно для вскрытия MD5 в практических приложениях, оно не влияет и на использование MD5 в алгоритмах шифрования, подобных Luby-Rackoff (см. раздел 14.11). Успех этого вскрытия означает только, что одна из основных целей проектирования MD5- создать устойчивую к столкновениям функцию сжатия - не была достигнута. Хотя справедливо, что "кажется, что у функции сжатия есть слабое место, но это практически не влияет на безопасность хэш-функции " [1336], я отношусь к использо­ванию MD5 очень осторожно.

18.6 MD2

MD2 - это другая 128-битовая однонаправленная хэш-функция, разработанная Роном Ривестом [801, 1335]. Она, вместе с MD5, используется в протоколах РЕМ (см. раздел 24.10). Безопасность MD2 опирается на слу­чайную перестановку байтов. Эта перестановка фиксирована и зависит от разрядов я. S₀, S_u S₂,..., 6*255 и яв­ляются перестановкой. Чтобы выполнить хэширование сообщения М:

(1) Дополните сообщение i байтами, значение i должно быть таким, чтобы длина полученного сообщения бы­ла кратна 16 байтам.

(2) Добавьте к сообщению 16 байтов контрольной суммы.

(3) Проинициализируйте 48-байтовый блок: Х₀, Х_и Х₂,..., Х₄₁. Заполните первые 16 байтов X нулями, во вторые 16 байтов X скопируйте первые 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X.

(4) Вот как выглядит функция сжатия:

г = о

Fory = 0 to 17 For к = 0 to 47 t = X_t XOR S_t

x_k = t

t = (t + j) mod 256

(5) Скопируйте во вторые 16 байтов Х вторые 16 байтов сообщения, а третьи 16 байтов X должны быть равны XOR первых и вторых 16 байтов X. Выполните этап (4). Повторяйте этапы (5) и (4) по очереди для каж­дых 16 байтов сообщения.

(6) Выходом являются первые 16 байтов X.

Хотя в MD2 пока не было найдено слабых мест (см. [1262]), она работает медленнее большинства других предлагаемых хэш-функций.

18.7 Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA)

NIST, вместе с NSA, для Стандарта цифровой подписи (Digital Signature Standard, см. Раздел 20.2) разрабо­тал Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA) [1154 (Digital Signature Standard]. (Сам стандарт называется Стандарт безопасного хэширования (Secure Hash Standard, SHS), a SHA - это алгоритм, используемый в стандарте.) В соответствии с Federal Register [539]:

Предлагается Федеральный стандарт обработки информации (Federal Information Processing Standard, FIPS) для Стандарта безопасного хэширования (Secure Hash Standard, SHS). Этот предложение определяет Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA) для использования вместе со Стандартом цифровой подписи (Digital Signature Standard)....

Кроме того, для приложений, в которых не требуется цифровая подпись, SHA должен использоваться во всех Федеральных приложениях, в которых понадобится алгоритм безопасного хэширования.

И

Этот Стандарт определяет Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA), необходимый для обеспе­чения безопасности Алгоритма цифровой подписи (Digital Signature Algorithm, DSA). Для любого входного сообщения дли­ной меньше 2^м битов SHA выдает 160-битовый результат, называемый кратким содержанием сообщения. Далее, краткое со­держание сообщения становится входом DSA, который вычисляет подпись для сообщения. Подписывание краткого содержа­ния вместо всего сообщения часто повышает эффективность процесса, так как краткое содержание сообщения намного меньше, чем само сообщение. То же краткое содержание сообщения должно быть получено тем, кто проверяет подпись, если принятая им версия сообщения используется в качестве входа SHA. SHA называется безопасным, так как он разработан так, чтобы было вычислительно невозможно найти сообщение, соответствующее данному краткому содержанию сообщения или найти два различных сообщения с одинаковым кратким содержанием сообщения. Любые изменения, произошедшие при пе­редаче сообщения, с очень высокой вероятностью приведут к изменению краткого содержания сообщения, и подпись не пройдет проверку. Принципы, лежащие в основе SHA, аналогичны использованным профессором Рональдом Л. Ривестом из MIT при проектировании алгоритма краткого содержания сообщения MD4 [1319]. SHA разработан по образцу упомянутого алгоритма.