Лекция № 11

Следующий протокол показывает, каким образом можно использовать столкновения второго рода.

A,B абоненты, а так же арбитр(посредник-участвует во всех частях протокола, арбитр только в спорных моментах) T.

1. Абонент A готовит 2 версии контракта на продажу автомобиля(одну-выгодную для B и другую не выгодную для B)(M1, M2).

2. Абонент A вносит несколько незначительных изменений в каждый документ и вычисляет соответствующие ХЭШ функции(M1’ , M2’). Например, если подписание документа осуществляется при помощи 64 Битной ХЭШ функции, а документ состоит из 32 строк, то можно делая или не делая пробел в каждой из строк получить (2^32) версий каждого документа.

3. Абонент A сравнивает ХЭШ значение для каждого изменения в каждом из 2 документов, разыскивая пару, для которой значение ХЭШ функций будут одинаковыми(h(M1’)=h(M2’)). Если используются 64х разрядные ХЭШ функции, то такая пара, как правило, будет найдена.

4. Абонент A получает подписанную абонентом B выгодную для него версию контракта.

5. Спустя некоторое время абонент A подменяет выгодную версию, на не выгодную версию. Теперь он может убедить арбитра T, что абонент B подписывал для него не выгодную версию контракта.

Вывод: Слишком короткие ХЭШ значения больше подвержены коллизиям второго рода. Необходимо использовать однонаправленные ХЭШ функции с большим числом разрядов(MD5(128), SHA1(256) и т.д.).

Идея функции сжатия

Однонаправленные ХЭШ функции строятся на идее функции сжатия, такая однонаправленная функция выдает значения фиксированной длинны n для прообраза произвольной, как правило большей длинны m.

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

Блоки(Mi)(см.телефон).

hi=f(Mi, hi-1)

h0=IV – инициализационный вектор.

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

Замечание: Функция сжатия так же строится с использованием лавинного эффекта(например: если поменять 1 бит прообраз, то в ХЭШ значении в среднем поменяется 50%бит – это необходимо для того, чтобы нельзя было определить зависимость между прообразом и результатом ХЭШ функции).

Применение

1. В процессе парольной аутентификации. Пароли в системе чаще всего хранятся в виде соответствующих ХЭШ значений.

2. При проверке целостности данных. Рассчитанная вновь контрольная сумма(ХЭШ значение) сравнивается с рассчитанной изначально. Равенство этих двух сумм говорит о неизменности данных за этот промежуток времени.

3. При использовании электронных подписей.

Контрольная сумма(CHECKSUM), FINGERPRINT(отпечаток пальца). Часто используются MD, MD2, MD4, MD5, SHA 1,2,3, ГОСТ Р 3411.94.

Коды проверки подлинности сообщений(mac(Message Authentication Code))

Код проверки подлинности сообщения – зависящая от секретного ключа однонаправленная ХЭШ функция. Коды MAC обладают теми же свойствами, что и однонаправленные функции, кроме того, они зависят от секретного ключа. Только владелец идентичного ключа может проверить ХЭШ значения. Коды MAC полезны для обеспечения проверки подлинности без нарушения безопасности.

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

Простейшим способом преобразовать однонаправленную ХЭШ функцию в код проверки, является шифрование ХЭШ значения к симметричному алгоритму(hk(M)=Ek(h(M))). Любой MAC код может быть преобразован в однонаправленную ХЭШ функцию с помощью раскрытия ключа.