Однонаправленные хэш-функции

Основы

Однонаправленная функция H(M) применяется к сообщению произвольной длины M и возвращает значение фиксированной длины h.

h= H(M), где h имеет длину m

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

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

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

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

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

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

Должно быть трудно найти два случайных сообщения, Mи M', для которых H(M)= H(M').

Помните вскрытие методом дня рождения из раздела 7.4? Оно основано не на поиске другого сообщения M', для которого H(M)= H(M'), а на поиске двух случайных сообщений, Mи M', для которых H(M)= H(M').

Следующий протокол, впервые описанный Гидеоном Ювалом (Gideon Yuval) [1635], показывает, как, если предыдущее требование не выполняется, Алиса может использовать вскрытие методом дня рождения для обмана Боба.

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

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

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

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

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

Это заметная проблема. (Одним из советов является внесение косметических исправлений в подписываемый документ.)

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