В. Р. Гинзбург Перевод с английского
жүктеу/скачать 2,74 Mb. Pdf көрінісі
|
практическая криптография
Глава 6. Функции хэширования ности. Коллизией по отношению к функциям хэширования называют два разных значения m 1 и m 2 , для которых h ( m 1 ) = h ( m 2 ) . Разумеется, каж- дая функция хэширования обладает бесконечным числом подобных колли- зий. (Существует бесконечное число возможных входных значений и только конечное число возможных выходных значений.) Таким образом, функция хэширования никогда не будет бесконфликтной. Свойство сопротивляемости коллизиям означает лишь то, что, хотя коллизии и существуют, их невозмож- но обнаружить. Свойство сопротивляемости коллизиям делает функции хэширования пригодными для использования в схемах цифровых подписей. Тем не менее существует масса функций хэширования, обладающих сопротивляемостью к коллизиям и совершенно не подходящих для других областей применения, таких, как генерация ключей, односторонние функции и т.п. На практике разработчики криптографических систем нуждаются в функции хэширова- ния, которая представляет собой случайное отображение. Поэтому необходи- мо, чтобы функция хэширования была неотличима от случайного отображе- ния. Любое другое определение приводит к возникновению ситуации, в ко- торой разработчик больше не может обращаться с функцией хэширования как с идеальным “черным ящиком” и должен просчитывать, как ее свойства будут взаимодействовать с остальными частями системы. Определение 4 Идеальная функция хэширования — это случайное отоб- ражение всех возможных входных значений на множество возможных вы- ходных значений. Это определение, как и сформулированное ранее определение идеального блочного шифра (см. раздел 4.3), является неполным. С формальной точки зрения не существует такого понятия, как случайное отображение; мы можем говорить только о вероятностном распределении на множестве всех возмож- ных отображений. Тем не менее для наших целей такое определение вполне подойдет. Теперь можно дать определение атаке на функцию хэширования. Определение 5 Атака на функцию хэширования — это нетривиальный метод, позволяющий обнаружить различие между функцией хэширования и идеальной функцией хэширования. В этом определении идеальная функция хэширования, очевидно, должна иметь тот же размер выходных данных, что и функция хэширования, под- вергающаяся атаке. Как и при рассмотрении блочных шифров, требование “нетривиальный” касается всех типов универсальных атак. Наши замечания относительно тривиальных атак на блочные шифры справедливы и здесь. 6.2. Современные функции хэширования 107 Осталось определить лишь то, какой объем работы придется выполнить злоумышленнику. В отличие от блочного шифра, у функции хэширования нет ключа. Кроме того, для функции хэширования не существует универсальной атаки наподобие перебора всех вариантов ключа. Основное внимание здесь следует уделить размеру выходных данных. Одной из универсальных атак на функцию хэширования является атака, в основе которой лежит парадокс задачи о днях рождения. Как известно, такая атака направлена на обнару- жение коллизий. Для функции хэширования с n -битовыми выходными дан- ными возникновения коллизии следует ожидать примерно через 2 n/ 2 шагов. Между тем коллизии актуальны только для определенных областей примене- ния функций хэширования. В других случаях целью злоумышленника может стать поиск прообраза (для заданного x найти такое m , что h ( m ) = x ) ли- бо выявление некоторых структурных закономерностей в выходных данных функции хэширования. Универсальная атака на прообраз требует выполне- ния около 2 n шагов. Мы не собираемся подробно рассматривать то, какие ата- ки являются актуальными для конкретной области применения функции хэ- ширования и сколько времени может потратить различитель на осуществле- ние конкретного типа атаки. Чтобы различитель имел практический смысл, он должен быть более эффективным, чем универсальная атака, направленная на достижение аналогичных результатов. К сожалению, это не точное опре- деление, но мы не знаем, как сформулировать его точнее. Если кто-нибудь заявит об изобретении нового типа атаки, просто спросите себя, нельзя ли получить такой же или лучший результат с помощью универсальной атаки, не учитывающей специфику функции хэширования. Положительный ответ на этот вопрос будет означать, что новый различитель совершенно бесполе- зен. Если же ответ отрицателен, значит, новый различитель действительно имеет право на существование. Как и при рассмотрении блочных шифров, мы допускаем наличие сни- женного уровня безопасности, если это указано явно. Мы можем представить себе 512-битовую функцию хэширования, которая обеспечивает уровень без- опасности 128 бит. В этом случае различитель должен добиться успеха не более чем за 2 128 шагов. 6.2 Современные функции хэширования Рассмотрим первую практическую проблему. На свете слишком мало хо- роших функций хэширования. На данный момент наш выбор ограничен лишь семейством функций SHA да еще, пожалуй, функцией MD5. Существуют и другие опубликованные предложения, но ни одно из них не привлекло вни- мания критиков настолько, чтобы ему можно было доверять. Вообще говоря, |