Однонаправленные ХЕШ. Свойства и применение

Согласно Шнайдеру Б. однонаправленная функция Н (М) применяется к сообщению произвольной длины М и возвращает значение фиксированной длины h, то есть h = Н (М), где h имеет длину т.

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

Зная М, легко вычислить h.

Зная Н, трудно определить М, для которого H(M)=h.

Зная М, трудно определить другое сообщение М’, для которого Н (М) = Н(М').

То есть смысл однонаправленных хэш-функций и состоит в обеспечении для М уникального идентификатора ("отпечатка пальца"). Если Алиса подписала М с помощью алгоритма цифровой подписи на базе Н (М), а Боб может создать М', другое сообщение, отличное от М, для которого Н (М) = Н(М'), то Боб сможет утверждать, что Алиса подписала М'.

В ряде приложений однонаправленности недостаточно, необходимо выполнение другого требования, называемого устойчивостью к коллизиям. Его можно сформулировать так: трудно найти два случайных сообщения М и М', для которых Н (М) = Н(М').

Проанализируем протокол, впервые описанный Гидеоном Ювалом, который показывает, как, если предыдущее требование не выполняется, Алиса может использовать вскрытие методом дня рождения для обмана Боба. Он основан не на поиске другого сообщения М, для которого Н (М) = Н(М'), а на поиске двух случайных сообщений, М и М', для которых Н (М) = Н(М') (метод «дней рождений» смотри в Шнайдере раздел7.4).

1. Алиса готовит две версии контракта: одну, выгодную для Боба, и другую, приводящую его к банкротству

2. Алиса вносит несколько незначительных изменений в каждый документ и вычисляет хэш-функции.(замена ПРОБЕЛА комбинацией ПР О-БЕЛ-ЗАБОЙ-ПРОБЕЛ, вставка одного-двух пробелов перед возвратом каретки, и т.д. Делая или не делая по одному изменению в каждой из 32 строк, Алиса может легко получить 2 ³² различных документов.)

3. Алиса сравнивает хэш-значения для каждого изменения в каждом из двух документов, разыскивая пару, для которой эти значения совпадают. (Если хэш является всего лишь 64-разрядное значение, Алиса, сможет найти совпадающую пару сравнив 2³² версий каждого документа.) Она восстанавливает два документа, дающих одинаковое хэш-значение.

4. Алиса получает подписанную Бобом выгодную для него версию контракта, используя протокол, в котором он подписывает только хэш-значение.

5. Спустя некоторое время Алиса подменяет контракт, подписанный Бобом, другим, который он не подписывал. Теперь она может убедить арбитра в том, что Боб подписал другой контракт.

Это серьезная проблема. Совет: обязательное внесение мелких изменений в подписываемый документ.

Длины значений однонаправленных хэш-функций

64-битовые хэш-функции слишком малы, чтобы противостоять вскрытию методом «дней рождений». Более практичны однонаправленные хэш-функции, выдающие 128-битовые хэш-значения. При этом, чтобы найти два документа с одинаковыми хэш-значениями, для вскрытия методом «дней рождений» придется хэшировать 2⁶⁴ слу­чайных документов, что, впрочем, недостаточно, если нужна длительная безопасность. Поэтому ряд стандартов безопасного хэширования (Secure Hash Standard, SHS), использует 160-битовое хэш-значение. Это еще сильнее усложняет вскрытие методом «дней рождений», для которого понадобится 2⁸⁰ хэширований.

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

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

2. Хэш значение конкатенируерся с сообщением.

3. Для конкатенации вычисляется новое хэш-значения.

4. Создается хэш-значение большей длины, состоящее из объединения хэш-значения этапа (1) и хэш-значения этапа (3).

5. Этапы (1)-(4) повторяются нужное количество раз для обеспечения требуемой длины хэш-значения.

Структура и алгоритмы MD-функций

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

h _i, =f(М_i, h _i -1)

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

Хэшируемый вход должен содержать бинарное представление длины всего сообщения. Таким образом преодолевается потенциальная проблема, вызванная тем, что сообщения различной длины могут давать одно и то же хэш-значение. Иногда такой метод называется MD-усилением(MD - Message Digest).

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

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

Прямая безопасность. Безопасность MD4 не основывается на каких-либо допущениях, например, предположении о трудности разложения на множители.

Скорость. MD4 подходит для высокоскоростных программных реализаций. Она основана на простом набо­ре битовых манипуляций с 32-битовыми операндами.

Простота и компактность. MD4 проста, насколько это возможно, и не содержит больших структур данных или сложных программных модулей.

Удачная архитектура. MD4 оптимизирована для микропроцессорной архитектуры (особенно для микропро­цессоров Intel), для более крупных и быстрых компьютеров можно выполнить любые необходимые изменения.

MD5 - это улучшенная версия MD4. Хотя она сложнее MD4, их схемы похожи, и результатом MD5 также является 128-битовое хэш-значение.

MD2 - это другая 128-битовая однонаправленная хэш-функция, разработанная Роном Ривестом. Она вместе с MD5 используется для цифровой подписи в протоколах РЕМ. Безопасность MD2 опирается на случайную перестановку байтов. Эта перестановка фиксирована и зависит от цифр числа pi. Идентификаторы So, S1, S2,, S255 являются перестановкой.

Алгоритм безопасного хэширования (Secure Hash Algorithm, SHA), необходимый для обеспечения безопасности Алгоритма цифровой подписи (Digital Signature Algorithm, DSA). Для любого входного сообщения длиной меньше 2⁶⁴ битов SHA выдает 160-битовый результат, называемый кратким содержанием сообщения.