В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 6. Функции хэширования Данное свойство, очевидно, никак не укладывается в концепцию случай- ного отображения, которым, как мы привыкли думать, является функция хэширования. Что еще более печально, это свойство автоматически выбра- ковывает все рассмотренные функции хэширования в соответствии с нашим определением безопасности. Все, что нужно различителю, — это построить несколько подходящих пар ( m, m 0 ) и проверить функцию хэширования на наличие упомянутого свойства. Данное свойство, конечно же, не может быть присуще идеальной функции хэширования, поэтому соответствующий раз- личитель можно классифицировать как атаку. Сама же атака потребует от злоумышленника вычисления всего нескольких значений функции хэширо- вания, а следовательно, является очень быстрой. Как данное свойство может повредить системе? Представим себе систему, в которой пользователь А отсылает сообщение пользователю Б и хочет аутен- тифицировать его, послав значение h ( X k m ) , где X — это некий секретный ключ, известный только пользователям А и Б, а m — сообщение. Если бы h была идеальной функцией хэширования, данную систему аутентификации можно было бы считать вполне надежной. К сожалению, благодаря свой- ству удлинения злоумышленник Е может присоединить к сообщению m свой собственный текст и обновить код аутентичности h в соответствии с новым сообщением. Система аутентификации, которая позволяет злоумышленнику изменять сообщение, конечно же, совершенно непригодна с точки зрения без- опасности. 6.3.2 Коллизия при частичном хэшировании сообщений Второй недостаток функций хэширования связан с наличием у большин- ства из них итеративной структуры. Поясним это на примере конкретного различителя. Первым шагом любого различителя является задание условий, при кото- рых будет проводиться поиск различия между функцией хэширования и иде- альной функцией хэширования. Иногда эти условия очень просты: дана функ- ция хэширования, требуется найти коллизию. Попытаемся немного услож- нить условия работы различителя. Предположим, у нас есть система, кото- рая проводит аутентификацию сообщения m с помощью значения h ( m k X ) , где X — ключ аутентификации. Злоумышленник может выбрать сообщение m , однако система позволяет аутентифицировать только одно сообщение 4 . При использовании идеальной функции хэширования с результатом раз- мера n уровень безопасности описанной выше системы будет равен n бит. 4 Большинство систем позволяют аутентифицировать только ограниченное количество сообщений; наш пример — это всего лишь предельный случай, когда количество сообщений равно единице. На практике многие системы отсылают вместе с сообщением его номер, что для данного типа атак равноценно возможности выбора только одного сообщения. 6.4. Исправление недостатков 113 Злоумышленнику удастся всего лишь выбрать сообщение m , аутентифициро- вать его в системе с помощью значения h ( m k X ) и затем попытаться найти X путем полного перебора вариантов. С итеративной функцией хэширования, однако, перед злоумышленником открываются более радужные перспективы. Он находит строки m и m 0 , которые при хэшировании функцией h приводят к коллизии. Используя атаку, в основе которой лежит парадокс задачи о днях рождения, это можно выполнить всего лишь примерно за 2 n/ 2 шагов. Затем злоумышленник аутентифицирует в системе сообщение m и заменяет его со- общением m 0 . Напомним, что значение h вычисляется итеративно, поэтому, если при хэшировании части второго сообщения возникнет коллизия, а все оставшиеся входные значения будут такими же, как и для первого сообщения, значение хэш-кода тоже не изменится. Поскольку хэширование сообщений m и m 0 дает одно и то же значение, h ( m k X ) = h ( m 0 k X ) для всех X . Мы привели пример типичного различителя. Он устанавливает собствен- ные “правила игры” (условия, при которых он пытается осуществить атаку) и затем атакует систему. Цель, как и прежде, состоит в том, чтобы найти раз- личие между функцией хэширования и идеальной функцией хэширования, но в данном случае это очень легко. Если атака завершится удачно, значит, перед нами итеративная функция хэширования, а если неудачно — идеальная функция хэширования. 6.4 Исправление недостатков Нам нужна функция хэширования, которая будет вести себя как случай- ное отображение. К сожалению, все известные функции хэширования дан- ному требованию не соответствуют. Неужели придется выполнять проверку на наличие проблемы удлинения сообщения во всех местах, где используется функция хэширования? А как насчет коллизий при частичном хэшировании сообщений? И есть ли у функций хэширования еще какие-нибудь слабые сто- роны, которые нужно проверять? Оставлять функцию хэширования такой, как она есть, со всеми недостат- ками — весьма неудачная идея. Поверьте нам: всегда найдется такой способ использования функции хэширования, который их раскроет. Даже если вы задокументируете все известные недостатки, их не будут проверять в реаль- ных системах. Более того, если бы вы могли контролировать процесс разра- ботки системы, то обязательно столкнулись бы с проблемой сложности. Пред- положим, функция хэширования имеет три слабых места, блочный шифр — два, схема цифровой подписи — четыре и т.д. Чтобы убедиться в этом, при- дется проверить сотни вариантов взаимодействия этих слабых мест, что прак- |