18.1 Основы
Однонаправленная функция ЩМ) применяется к сообщению произвольной длины М и возвращает значение фиксированной длины h.
h = ЩМ), где h имеет длину т
Многие функции позволяют вычислять значение фиксированной длины по входным данным произвольной длины, но у однонаправленных хэш-функций есть дополнительные свойства, делающие их однонаправленными [1065]:
Зная М, легко вычислить h.
Зная Я, трудно определить М, для которого H(M)=h.
Зная М, трудно определить другое сообщение, М', для которого ЩМ)= ЩМ').
Если бы Мэллори умел делать трудные вещи, он смог бы разрушить безопасность любого протокола, и с-пользующего однонаправленную хэш-функцию. Смысл однонаправленных хэш-функций и состоит в обеспечении для М уникального идентификатора ("отпечатка пальца"). Если Алиса подписала М с помощью алгоритма цифровой подписи на базе ЩМ), а Боб может создать М', другое сообщение, отличное от М, для которого ЩМ)= ЩМ'), то Боб сможет утверждать, что Алиса подписала М'.
В некоторых приложениях однонаправленности недостаточно, необходимо выполнение другого требования, называемого устойчивостью к столкновениям.
Должно быть трудно найти два случайных сообщения, М и М', для которых ЩМ)= ЩМ').
Помните вскрытие методом дня рождения из раздела 7.4? Оно основано не на поиске другого сообщения М', для которого ЩМ)= ЩМ'), а на поиске двух случайных сообщений ,МиМ', для которых ЩМ)= ЩМ').
Следующий протокол, впервые описанный Гидеоном Ювалом (Gideon Yuval) [1635], показывает, как, если предыдущее требование не выполняется, Алиса может использовать вскрытие методом дня рождения для обм а-на Боба.
(1) Алиса готовит две версии контракта: одну, выгодную для Боба, и другую, приводящую его к банкротству
(2) Алиса вносит несколько незначительных изменений в каждый документ и вычисляет хэш-функции . (Этими изменениями могут быть действия, подобные следующим : замена ПРОБЕЛА комбинацией ПРОБЕЛ-ЗАБОЙ-ПРОБЕЛ, вставка одного-двух пробелов перед возвратом каретки, и т.д. Делая или не делая по одному изменению в каждой из 32 строк, Алиса может легко получить 2 32 различных документов.)
(3) Алиса сравнивает хэш-значения для каждого изменения в каждом из двух документов , разыскивая пару, для которой эти значения совпадают. (Если выходом хэш-функции является всего лишь 64-разрядное зн а-чение, Алиса, как правило, сможет найти совпадающую пару сравнив 2 32 версий каждого документа.) Она восстанавливает два документа, дающих одинаковое хэш-значение .
(4) Алиса получает подписанную Бобом выгодную для него версию контракта, используя протокол, в котором он подписывает только хэш-значение.
(5) Спустя некоторое время Алиса подменяет контракт, подписанный Бобом, другим, который он не подпис ы-вал. Теперь она может убедить арбитра в том, что Боб подписал другой контракт .
Это заметная проблема. (Одним из советов является внесение косметических исправлений в подписываемый документ.)
При возможности успешного вскрытия методом дня рождения, могут применяться и другие способы вскр ы-тия. Например, противник может посылать системе автоматического контроля (может быть спутниковой) случайные строки сообщений со случайными строками подписей . В конце концов подпись под одним из этих случайных сообщений окажется правильной. Враг не сможет узнать, к чему приведет эта команда, но, если его единственной целью является вмешательство в работу спутника, он своего добьется .